平方数链

从任意一个数开始，不断取其各位数字的平方和，直到出现重复，就得到了一条数链，例如： \begin{align*} & 44 \rightarrow 32 \rightarrow 13 \rightarrow 10 \rightarrow \textbf{1} \rightarrow \textbf{1}\\ & 85 \rightarrow \textbf{89} \rightarrow 145 \rightarrow 42 \rightarrow 20 \rightarrow 4 \rightarrow 16 \rightarrow 37 \rightarrow 58 \rightarrow \textbf{89} \end{align*} 如上例所示，只要数链中出现1或89就会进入循环。事实上从任意一个数开始，最终都必定会进入1循环或89循环。小于一千万的数中有多少个最终会进入89循环？

本题难度:

解答

用$G(n)$表示n中各位数字的平方和，若n不超过一千万，则显然G(n)不超过$81\times 7$，从而$G(G(n))$不超过250，因此缓存250以下的n的结果，再遍历其它数即得结果是$8581146$。

d=[0]*250
d[1]=1
d[4]=d[16]=d[37]=d[58]=d[89]=d[145]=d[42]=d[20]=4

t=8
for i in range(2,250):
    if d[i]==0:
        p=[]
        j=i
        while j!=1 and j!=4 and d[j]==0:
            p.append(j)
            j=sum(int(k)**2 for k in str(j))
        for q in p:
            d[q]=d[j] if d[j]!=0 else j 
        if j==4 or d[j]==4:
            t+=len(p)

for i in range(250,10000000):
    j=i
    while j>249:
        j=sum(int(k)**2 for k in str(j))
    if d[j]==4:
        t+=1

print t