刪除第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）個剩餘元素

回答

相關問題