0095 亲和数链
* * * *
拉格朗日计划
* * * *
亲和数链

一个数自身以外的因数称为它的真因数。例如28的的真因数有1、2、4、7、14,这些真因数的和恰为28,这样的数称为完全数。

不难验证220的真因数之和是284,而284的真因数之和又是220,两者构成了一个长度为2、首尾相等的链,我们称之为亲和数对。

存在更长的类似数链。例如,从12496开始不断求真因数之和可得长度为5、首尾相等的链: $$12496 \rightarrow 14288 \rightarrow 15472 \rightarrow 14536 \rightarrow 14264 \rightarrow 12496 \rightarrow \ldots$$ 我们称这样的数链为亲和数链。找出最长的、所有元素都不超过一百万的亲和数链,并给出其中最小的数。

本题难度:



解答

用筛法生成所有的真因数之和,逐个检查并缓存记录链长可得结果是$14316$,该链中有28项。

target=1000001
d=[1]*target
d[0]=d[1]=0
for n in range(2,target):
    for i in range(n+n,target,n):
        d[i]+=n
c=[0 if i>=target else -1 for i in d]
c[0]=c[1]=0
m=0
z=0
for n in range(2,target):
    if c[n] < 0:
        p=[]
        j=n
        while c[j] < 0 and j not in p:
            p.append(j)
            j=d[j]
        if c[j]>=0:
            for q in p:
                c[q]=0
        else:
            k=p.index(j)
            for q in p[:k]:
                c[q]=0
            for q in c[k:]:
                c[q]=len(p)-k
            if len(p)-k>m:
                m=len(p)-k
                z=min(p[k:])
            elif len(p)-k==m:
                z=min(p[k:]+[z])

print z