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)。