删除自然数第 k 次传递中剩余的每个 (k+1) 个元素

Question

在自然数系列中，我们必须在第 1 遍中删除每个第 2 个元素。然后在其余元素中，删除第二遍中的每 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, ...

所以，在无限通过之后，它将成为

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

这个系列也被称为弗拉维乌斯-约瑟夫斯筛。

为此的解决方案是找到该系列中的第 6 个元素：

• do 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+(Ndiv 1(。"div"是整数除法，即丢弃余数的除法。

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

在系列 S[2]

上，第 N 个整数是通过访问 S[1] 中的第 N+(Ndiv 2(个元素获得的。

1 3 7 9 13 15 19 21 ...

在系列 S[3]

上，第 N 个整数是通过访问 S[2] 中的第 N+(Ndiv 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))

但请注意，当系列> N 时，floor(N/系列(等于零，因此您可以始终将其称为 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 但从零开始的索引(。