作者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/cn.aspx?n=bbs/puzzle/M.1419881900.A.3A5.html