Solving Josephus permutation

Question

Suppose if 100 people standing in a circle in an order 1 to 100. No. 1 has a sword. He kills the next person (i.e. No. 2) and gives the sword to the next (i.e. No. 3). All people do the same until only 1 survives. Which number survives at the last?

There are 100 people starting from 1 to 100.

I tried with

persons <- c(1:100)
for (i in 1:100) {
  qu <- persons[seq_along(persons) %% 2 > 0]
  if (q2 == 2) {
    print(q2[2])
  }
}

and also with this

q=0
 while(q==0){ persons=persons[seq_along(persons) %% 2 > 0]
 if(length(persons)==2){ print(persons[2])
 q=1}}

But this gives an answer as 65 which is wrong and doesn't solve the purpose.

Any solution how this could be done?

Answer 1

In this solution, assume the person with the sword is the first person in the vector. That person kills the next person and moves to the end of the line.

If there is one person, then that person is the survivor.

kill <- function(people = seq_len(100)) {
  if (length(people) == 1) return(people)

  kill(
    c(tail(people, -2), people[1]))
}


kill()
#> [1] 73

Edit:

For large n, use the following solution

kill_fast <- function(n) 2 * (n - 2 ^ (floor(log2(n)))) + 1

kill_fast(100)
#> [1] 73

kill_fast(100000)
#> [1] 68929