Delete each (k + 1) -th remaining element in the k-th pass of natural numbers

Question

In a series of natural numbers, we must remove every second element in the 1st pass. Then, in the remaining elements, delete every third element in the second pass. Then, on the Kth pass, delete each (k + 1) th element from the remaining elements.

The series will look as follows

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 the first pass (after removing every second element)

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

After the second passage (after the removal of every third element)

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

After the third pass (after removing every 4th element)

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

So, after going through infinity, he will become

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

This series is also called the Flavius ​​Joseph sieve.

The solution for this is to find the 6th element in a row:

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

Although it works, I don’t understand how the solution works?

Program C for this,

 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); } 

Link explaining this http://oeis.org/A000960

Answer 1

This does not answer your question, but here is the output of a more intuitive algorithm for calculating arbitrary elements of a stream, which is just as fast.

Let me name the initial row containing all the integers S [0], and then the S [1] row after the first pass, S [2] row after the second pass, etc.

In the series S [0], the N-integer (initial indices from zero) is N + 1.

 1 2 3 4 5 6 7 8 9 10 ... 

In the series S [1], an N-integer is obtained by accessing the (2N) th element from S [0]. Note 2N = N + (N div 1). 'div' is a whole division, that is, a division where the remainder is discarded.

 1 3 5 7 9 11 13 15 17 ... 

In the series S [2], an N-integer is obtained by accessing the element of the N + (N div 2) th element from S [1].

 1 3 7 9 13 15 19 21 ... 

In the series S [3], an N-integer is obtained by accessing the element of the N + (N div 3) th element from S [2], etc.

 1 3 7 13 15 19 ... 

Thus, you get the following recursive procedure:

 get_number(int series, int N): if (series == 0): return N + 1 else: return get_number(series - 1, N + floor(N / series)) 

But note that when a series> N, the gender (N / series) is identical to zero, so you can always call it like get_number (N, N).

For instance,

 get_number(5, 5) = get_number(4, 6) = get_number(3, 7) = get_number(2, 9) = get_number(1, 13) = get_number(0, 26) = 27. 

This shows how you can get “27” as the 6th (5, but zero indexed) from the stream.