作者tml (流刑人形)
看板puzzle
標題[中譯] ProjectEuler 494 Collatz prefix famili
時間Tue Dec 30 03:38:08 2014
494. Collatz prefix families
https://projecteuler.net/problem=494
Collatz數列定義如下：
a_(i+1) = a_i / 2，若a_i為偶數。
3a_i + 1，若a_i為奇數。
「Collatz猜想」宣稱無論由哪一個正整數開始，此一數列必將收斂至迴圈1, 4, 2, 1...
我們定義Collatz的前置數列p(n)為由a_1 = n開始，在2的次方出現前的Collatz子數列。
（在此，我們把1 = 2^0也視為2的次方。）例如：
p(13) = {13, 40, 20, 10, 5}
p(8) = {}
若有數不符合此猜想，則會有無限長的前置數列。
令S_m為所有長度為m的前置數列的集合。若此集合內的兩元素{a_1, a_2, ...,a_m}以及
{b_1, b_2, ..., b_m}符合下列關係，則我們稱它們屬於同一族：
「對所有1≦i,j≦m，a_i < a_j若且唯若b_i < b_j。」
舉例來說，在S_4裡{6, 3, 10, 5}和{454, 227, 682, 341}屬於同一族，但
{113, 340, 170, 85}則不在此一族內。
令f(m)為S_m集合內的相異族數。
已知f(5) = 5、f(10) = 55以及f(20) = 6771。
請求出f(90)。
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 206.196.186.173
※ 文章網址: http://webptt.com/m.aspx?n=bbs/puzzle/M.1419881900.A.3A5.html