Linear Variation of Josephus Puzzle

So here is the Josephus problem on wiki. The problem that I have is a linear variation of this, but I will restate the whole problem for clarity.

( Numbers = Natural Numbers )

There is a process that is eliminating numbers in the following manner:

i=2
while 1:
    remove numbers that are *placed* at positions divisible by i
    i+=1

You are also given a number K, you have to confirm if this number K will survive the elimination.

E.g. ( assuming index starts at 0 )

1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16 ...
0,1,2,3,4,5,6,7开发者_开发技巧,8, 9,10,11,12,13,14,15 ...  (indices)

After step 1 ( elimination at i=2 )
2,4,6,8,10,12,14,16 ... 
0,1,2,3, 4, 5, 6, 7 ... (indices)

After step 2 (elimination at i=3 )
2,4,6,10,12,16 ... ( 8 and 14 got removed cause they were at index 3 and 6 resp. )
0,1,2, 3, 4, 5 ... (indices)

As we can see 2,4,6 are safe after this step, since the process will be choosing higher and higher values for elimination.

So once again, given a K how do you determine if K will be safe ?

The question doesn't make it clear exactly what happens to the number at position 0. In the example, at step 1, the number 1 (at position 0) is eliminated. But then at step 2 the number 2 (at position 0) survives.

I'm going to assume for the purposes of this answer that the example is in error and the number at position 0 always survives. So the example should look like this:

Initial position

 Number    1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 ...
 Position  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 ... 

After step 1:

 Number    1  2  4  6  8 10 12 14 16 18 20 22 24 26 28 30 32 ...
 Position  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 ...

After step 2:

 Number    1  2  4  8 10 14 16 20 22 26 28 32 34 38 40 44 46 ...
 Position  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 ...

This leads to the sequence 1, 2, 4, 8, 14, 20, 28, 40, ... which is not found in OEIS (but see addendum below).

Here's how you might determine if a particular number K survives, without computing the whole sequence:

Let J₁ = K − 1 (the initial position of K).

• K is eliminated at step 1 if J₁>0 and 2|J₁, but if not, its new index is J₂ = J₁ − ⌊J₁/2⌋
• K is eliminated at step 2 if J₂>0 and 3|J₂, but if not, its new index is J₃ = J₂ − ⌊J₂/3⌋
• and so on, until either K is eliminated, or until Ji < i+1, when we know that K survives.

ADDENDUM

I was a bit hasty when I concluded that this sequence isn't in OEIS. For suppose we had numbered the positions starting at 1 instead of 0. Then we'd get the sequence 1, 3, 7, 13, 19, 27, 39, ... which is OEIS sequence A000960, "Flavius Josephus's sieve". Still no closed-form solution, though.

One solution is to keep track of the index of K within the list at every iteration.

At every step, we first check if the index of K is divisible by. If it is, we return false. Otherwise, we simply subtract the number of elements before K that are divisible by i from the index of K (i.e. K is shifted that many times to the left).

We continue doing this until only one element is left.