删除第k个自然数中的第（k + 1）个剩余元素

在自然数列中，我们必须删除第1遍中的每个第2个元素。然后在剩下的元素中，删除第二遍中的每个第三个元素。然后在第K次通过时，从剩余的元素中移除每个（k + 1）个元素。删除第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, ...

一号通后（除每2元后），

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

第二遍后，（去掉每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元素：

做6^2 = 36
再往5的倍数给予35
然后向下到多4 = 32
然后下降到3 = 30
然后倍数下降到2 = 28
然后倍数下降到1 = 27
等第六幸运数字是27

虽然它的工作原理，我不理解的解决方案是如何工作的？

这个交流计划是，

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

来源

2012-05-11 viji

您可能会在http://math.stackexchange.com上询问这个问题 – Shahbaz

我做到了。 http://math.stackexchange.com/questions/143876/remove-every-k1-th-remaining-element-in-kth-pass-of-natural-numbers – viji

这不回答你的问题，但这里有一个更直观的算法的推导计算的任意内容流速一样快。

让我们称含有的所有整数S [0]的初始系列，然后S [1]所述系列中的第一道次之后，S [2]所述系列的第二通等之后。

在系列S [0]，第N的整数（从零开始索引）是N + 1。

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

在系列S [1]时，通过访问第（2N）中获得的第N个整数S [0]中的第n个元素。注2N = N +（N div 1）。 'div'是整数除法，即余数被丢弃的除法。

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

在系列S [2]，第N整数通过访问N +获得（N DIV 2）个从S元素[1]。

1 3 7 9 13 15 19 21 ...

在系列S [3]，第N整数通过访问N +获得（N DIV 3）个选自S元素[2]，等等。

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，地板（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，但索引）。

来源

2012-05-11 13:58:04

删除第k个自然数中的第（k + 1）个剩余元素

回答

相关问题