algorithm - 在自然数的第 k 遍中删除每 (k+1) 个剩余元素

Question

在自然数系列中，我们必须在第一遍中删除每个第二个元素。然后在剩余的元素中，在第二遍中删除每第 3 个元素。然后在第 K 遍，从剩余元素中删除每第 (k+1) 个元素。

这个系列会是这样的

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, ...

第一遍后(每删除第二个元素后)，

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

在第 2 遍之后，(在删除每第 3 个元素之后)，

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

第 3 遍后，(每删除第 4 个元素后)，

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

所以，经过infinity pass后，会变成

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

这个系列也称为 Flavius-Josephus 筛。

解决方案，找到系列中的第 6 个元素:

• 做 6^2 = 36
• 下降到 5 的倍数，给出 35
• 然后下降到 4 的倍数 = 32
• 然后下降到 3 = 30 的倍数
• 然后下降到 2 = 28 的倍数
• 然后下降到 1 的倍数 = 27
• 所以第 6 个幸运数字是 27。

虽然它有效，但我不明白该解决方案是如何工作的？

一个 C 程序是，

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

解释这个的链接http://oeis.org/A000960

Answer 1

这并没有回答你的问题，但这里推导了一种更直观的算法，用于计算流中任意元素的速度。

我们将包含所有整数的初始序列称为 S[0]，然后将 S[1] 称为第一遍后的序列，将 S[2] 称为第二遍后的序列，依此类推。

在系列 S[0] 上，第 N 个整数(从零开始的索引)是 N + 1。

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

在系列 S[1] 上，第 N 个整数是通过访问 S[0] 中的第 (2N) 个元素获得的。注意 2N = N+(N div 1)。 'div'是整数除法，即舍去余数的除法。

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

在系列 S[2] 中，第 N 个整数是通过访问 S[1] 中的第 N+(N div 2) 个元素获得的。

1 3 7 9 13 15 19 21 ...

在系列S[3]中，第N个整数是通过访问S[2]中的第N+(N div 3)个元素获得的，依此类推。

1 3 7 13 15 19 ...

因此你得到以下递归过程:

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

但请注意，当 series > N 时，floor(N/series) 完全为零，因此您始终可以将其称为 get_number(N, N)。

例如，

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.

这显示了如何从流中获取“27”作为第 6 个(5 但从零开始的索引)。