# Remove every (k+1) th remaining element in kth pass of natural numbers

In the natural numbers series, we've to remove every 2nd element in the 1st pass. Then in the remaining elements, remove every 3rd element in the second pass. Then at Kth pass, remove every (k+1)th element from the remaining elements.

The series will go like this

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, ...


After 1st pass(after removing every 2nd element),

1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, ...


After 2nd pass,(after removing every 3rd element),

1, 3, 7, 9, 13, 15, 19, 21, 25, 27, ...


After 3rd pass,(after removing every 4th element),

1, 3, 7, 13, 15, 19, 25, 27, ...


So, after infinity pass, it will become

1, 3, 7, 13, 19, 27, 39, 49, 63, 79, ...


This series is also called Flavius-Josephus sieve.

The solution for this, to find the 6th element in the series:

• do 6^2 = 36
• go down to a multiple of 5 giving 35
• then down to a multiple of 4 = 32
• then down to a multiple of 3 = 30
• then down to a multiple of 2 = 28
• then down to a multiple of 1 = 27
• and so the 6th lucky number is 27.

Though it works, I'm not understanding how the solution works ?

A C program for this is,

int calc(int n)
{
if (n == 1) return 1;
return calc_rec(n*n, n-1);
}

int calc_rec(int nu, int level)
{
int tmp;
if (level == 1) return (nu-1);
tmp = nu % level;
return calc_rec(nu - (tmp ? tmp : level), level-1);
}


-

First of all the algorithm you describe holds for all positions not just for the $6^{th}$ (don't know whether you meant that, but I had to convince myself of it).

Let's introduce some notation. The position of them number $n$ after the $k^{th}$ step is denoted by $[n]_k$, where I restrict myself only to those $n$ which survive to the final sequence. To make the indexing less confusing I choose the $1^{st}$ step to do nothing. Then the $k^{th}$ step indeed removes every $k^{th}$ number. Then $[n]_1=n$ and for big $k$ we have $[n]_k=[n]_{k+1}$, i.e. the positions stabilises. The final position may be written as $[n]_\infty$. E.g. $[27]_6=[27]_\infty=6$.

How do we get from $[n]_k$ to $[n]_{k+1}$ in general? The formula is $$[n]_{k+1}=[n]_k-\lfloor\frac{[n]_k}{k+1}\rfloor.$$

Let us convince ourselves of this formula: $[27]_1=27$ and

$$[27]_2=27-\lfloor\frac{27}{2}\rfloor=14$$

The idea is that we throw away a certain amount of smaller numbers, namely every $(k+1)^{st}$ which amounts to precisely $\lfloor\frac{[n]_k}{k+1}\rfloor$ numbers.

So how do we reverse this process? In our example we are given $[n]_\infty=[n]_6=6$ and want to find $n=27$.

Going one step back means that we want to find $x=[n]_5$ such that

$$x-\lfloor\frac x6\rfloor=6$$

or equivalently

$$\lfloor\frac x6\rfloor=x-6$$

If we multiply this by $6$ (here is where the squaring comes into play) we end up with

$$6\lfloor\frac x6\rfloor=6x-6^2$$

The left hand side is then nearly $x$ and nearly in that sense that it is slightly smaller such that the equation has an integer solution. I write this as

$$x-?=6x-6^2,$$

where the question mark indicates "slightly maller". Moving everything around gives us

$$5x=6^2-?.$$

Now recall that the question mark is the smallest number such that we have an integer solution, i.e we go down from $6^2$ to a number which is divisible by $5$, namley 35.

If we repeat this step we will get a very similar result which gives

$$4[n]_4=35-?,$$

so we go down to the next smaller number which is divisible by 4 and so on. We end up with

$$1[n]_1=28-?=27.$$

This reasoning works perfectly well for all starting points.

-