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

Question

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

The link explaining this http://oeis.org/A000960

You might benefit asking this on http://math.stackexchange.com — Shahbaz, May 11 '12 at 12:54
I did it. http://math.stackexchange.com/questions/143876/remove-every-k1-th-remaining-element-in-kth-pass-of-natural-numbers — viji, May 11 '12 at 13:14

score 2 · Answer 1 · answered May 11 '12 at 13:58

This doesn't answer you question, but here is the derivation of a more intuitive algorithm for calculating arbitrary elements of the stream that is as fast.

Let's call the initial series containing all integers S[0], and then S[1] the series after the first pass, S[2] the series after the second pass and so on.

On series S[0], the Nth integer (starting indices from zero) is N + 1.

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

On series S[1], the Nth integer is obtained by accessing the (2N)th element from S[0]. Note 2N = N+(N div 1). 'div' is integer division, i.e. division where remainder is discarded.

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

On series S[2], the Nth integer is obtained by accessing the N+(N div 2)th element from S[1].

1 3 7 9 13 15 19 21 ...

On series S[3], the Nth integer is obtained by accessing the N+(N div 3)th element from S[2], and so on.

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 series > N, floor(N / series) is identically zero so you can call this always as get_number(N, N).

For example,

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-based indexing) from the stream.

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

1 Answers1