Let $J(n)$ be the number of the surviving soldier when there are $n$ soldiers in the ring. Of course, $J(1) = 1$ .

• If $n$ is even, after one round, soldiers 2,4,6,...,n will have been killed, so the $\tfrac12n$ soldiers 1,3,5,...,n-1 are left, with the sword back with soldier 1. A soldier in position $x$ after the first round was in position $2x-1$ before the first round. Thus $J(n) \; = \; 2J(\tfrac12n) - 1 \hspace{2cm} n \;\mathrm{even}$
• If $n$ is odd, after one round, soldiers 2,4,6,..,n-1,1 will have been killed, so the $\tfrac12(n-1)$ soldiers $3,5,7,...,n$ are left, with the sword with soldier 3. A soldier in position $x$ after the first round was in position $2x+1$ before the first round. Thus $J(n) \; = \; 2J(\tfrac12(n-1)) + 1 \hspace{2cm} n \;\mathrm{odd}$

Now that we have these recurrence relations, we can prove the following by induction:

If $n = 2^a + k$ where $a,k \in \mathbb{N} \cup \{0\}$ and $0 \le k < 2^a$ , then $J(n) = 2k+1$ .

Proof : If $n=1$ then $a=k=0$ , so $2k+1=1=J(1)$ . Suppose inductively that $N > 1$ and the the above formula works for all numbers smaller than $N$ .

• If $N = 2n$ is even, we can write $n = 2^a + k$ where $0 \le k < 2^a$ , so that $J(n) = 2k+1$ . But then $J(N) = 2J(n) - 1 = 4k+1$ . On the other hand $N = 2^{a+1} +2k$ and $0 \le 2k < 2^{a+1}$ , and we note that $J(N)$ is indeed equal to $2(2k) + 1$ .
• If $N = 2n+1$ is odd, we can write $n = 2^a + k$ where $0 \le k < 2^a$ , so that $J(n) = 2k+1$ . But then $J(N) = 2J(n) + 1 = 4k+3$ . On the other hand $N=2^{a+1} + (2k+1)$ and $0 \le 2k < 2^{a+1}$ , so that $2k+1 < 2^{a+1}$ as well, and we note that $J(N)$ is indeed equal to $2(2k+1) + 1$ .

Since $100 = 2^6 + 36$ , the answer is $\boxed{73}$ .

$\begin{aligned} \\ 100 &= 2^a + k \quad a \text{ is the highest power} \\ 100 &= 64 + 36 \\ 100 &= 2^6 + 36 \end{aligned}$

The $(2k + 1)$ th person will survive $\implies 2(36) + 1 \implies \boxed{73}$

The problem is known as Josephus problem. Watch this excellent video by Numberphile here

The problem is well discussed in "Concrete Mathematics by Graham, Knuth and Patashnik"

The simplest solution is:

First step: Binary representation of 100.  That is 100=1100100

Solution: Cyclic left shift one bit 1001001=73

Let $S_i$ be the set of survivors after the sword has made $i$ circuits.

First circuit: the even numbers are killed, leaving all the odds for the second circuit. $S_{1} = \{n : n \equiv 1 \mod 2\}$

Second circuit: every $n$ congruent to $1 \mod 4$ kills the number two higher. $S_{2} = \{n : n \equiv 1 \mod 4\}$

Third circuit: every $n$ kills the number $4$ higher. $S_{3} = \{n : n \equiv 1 \mod 8\}$ . Note, however, that $S_3$ has an odd number of elements, so our #1 guy is doomed

Fourth circuit: every $n$ starting with $9$ kills the number $8$ higher. $S_{4} = \{n : n \equiv 9 \mod 16\}$ We're down to $6$ numbers left.

Fifth circuit: we keep the first, third, and fifth elements of previous set. $S_{5} = \{n : n \equiv 9 \mod 32\} = \{9,41,73\}$

Sixth circuit: $9$ kills $41$ and hands sword to $73$ . $S_{6} = \{n : n \equiv 9 \mod 64\} = \{9,73\}$

Seventh circuit: $73$ kills $9$ and is the sole survivor.

The solution requires getting the nearest smaller number that is the power of 2, in this case 64 and subtract it with the given number.100-64=36. Now we apply the formula; 2n+1 = 2*36 + 1 = 72 + 1 = 73. Hence answer = 73

Use Euclid's division lemma

First remove 2n

Then remove 4n +3

Then keep cutting until u reach the ans 73

This programme should be able to give us the solution for any number of soldiers, Am I wrong??

def sword(soldiers):

    list = []
    for x in range(soldiers):
        list.append(x+1)
    i = 1
    while len(list) > 1:
        prev = int(list[-1])
        del list[i::2]
        next = int(list[-1])

        #In case the cycle ended with the last soldier dead, the first soldier won't be killed, otherwise, it will.
        if next == prev:
            i = 0
        else:
            i = 1 
     print(list)

In every chanceor round alternate guy been killed so it makes an Arithmetic progression

In the first round

1+2( n-1) This shows where the sword goes, in the last sword goes to 99 and he killed 100 and give sword to 1

round 2

1+4(n-1) This shows where the sword goes, the last sword goes to no.97 and he killed 99 and gave sword to 1

3 rd round

1+8( n-1) This shows where the sword goes, in last the sword goes to no. 97 and killed 1 and gave sword to 9 Now the sword goes to 9+16( n-1) if we put n= 5 we get the ans. 73