冰雹前缀

冰雹序列是按如下方式定义的序列 $$a_{n+1}=\begin{cases}a_n/2 & a_n \text{为偶数}, \\ 3a_n+1 & a_n \text{为奇数}.\end{cases}$$ 冰雹猜想是指对任意初值$a_1$，该序列最终都会进入$1\mapsto 4\mapsto 2\mapsto 1$的循环。

定义$p(n)$为从$a_1=n$开始的冰雹序列中不包含$2$的幂（注意$1=2^0$也是$2$的幂）的前缀子列。例如$p(13)=13,40,20,10,5$，$p(8)$为空列。

令$S(m)$为所有长度为$m$的此类前缀子列组成的集合，若$a=\{a_1,\ldots,a_m\},b=\{b_1,\ldots,b_m\}\in S_m$，且$a_i < a_j$当且仅当$b_i < b_j$，则称$a,b$等价。例如$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)$。

本题难度:

解答

分别用$+$和$-$表示$\times 3+1$和$\div 2$这两种操作，显然$+$不会连续出现。

对充分大的数而言，这两种操作分别使值增加和减少，因此可以用+号为位置来标志等价类，且$f$的值似乎总体上呈现出与斐波那契相同的递推特性（见此文）。

在题设的范围内只有$9, 19, 37, 51, 155, 159$所生成的序列中出现$+-$操作与值的增加减少以及$f$的递推出现背离。递推计算并用字典记录涉及异常值的序列可得最终结果$2880067194446832666$。

n=90
fib=[0,1]
for i in range(2,n+1):
    fib.append(fib[-1]+fib[-2])

seedsList={15:{9}, 16:{19}, 17:{37}, 20:{51}, 50:{159}, 81:{155}}
seeds={9}
res=0
for i in range(16,n-3):
    lastSeeds=seeds
    seeds=seedsList.get(i,set())
    for s in lastSeeds:
        if s%6==4:
            seeds.add((s-1)//3)
        if s%3>0:
            seeds.add(2*s)
        else:
            res+=1
    print i, "out of", n-3, "completed, current sum:", res

print fib[n]+res+sum([1, 2, 3, 1, 4, 3, 1, 2, 4, 1, 3, 3, 1, 2, 3, 1, 4, 4][s%18] for s in seeds)