095. 亲和数链(Amicable chains)

一个数字的真因子是除数字本身以外的其它因子。例如,28的真因子是1、2、4、7和14。由于这些因子的总和等于28,所以我们称28为完美数。

有趣的是,220的真因子之和为284,284的真因子之和为220,形成了一条两个数构成的链。因此,我们将220和284称为亲和数对。也许不太知名的是更长的链条, 例如从12496开始,可以形成五个数字的链:

$$ 12496 → 14288 → 15472 → 14536 → 14264 (→ 12496 → ...) $$
由于该链最终可以返回其起点,因此称之为亲和数链。请找出最长的亲和数链中最小的成员,且数链中的元素都不超过一百万。

分析:在之前的题目中我们已经接触过真因子之和、完美数以及亲和数对的概念,其中完美数可以看作是长度为一的亲和数链,而亲和数对则可以看作是长度为二的亲和数链,其实他们都属于一个叫做社交数的更为一般化的概念,链条的长度对应社交数的阶,阶为一则为完美数,阶为二则为亲和数对。

首先我们需要计算出一至一百万的所有数字的真因子之和,由于数据规模较大,继续沿用二十一题中的方法效率会比较低,这里我们对熟知的埃拉托斯特尼筛法进行一些改造,让它可以用来计算数字的真因子之和。它的思路和传统的筛法是类似的,首先创建一个列表,列表的长度为一百万,所有元素初始化为零。接着从数字二开始,因为所有偶数都有一个因子二,因此所有偶数位置都加上二。依次类推,在三的倍数的位置都加上三等等。如此循环下来,就可以计算出每个数的真因子之和,效率比单独计算每个数的真因子再求和要高效很多。为了之后引用的方便,我们这个列表转化成对应的字典。

在所有数字的真因子都求出来以后,我们可以编写一个函数来寻找某个数字\(start\)对应的亲和数链。首先我们可以找到数字\(start\)的真因子之和\(n\),如果\(n\)等于一(说明它是一个素数),或者\(n\)大于一百万,或者\(n\)在数组\(arr\)中出现过了,我们都认为对于\(start\)这个数字,在题目规定的条件下不存在亲和数链,所以返回\(None\)。如果没有被上面这些条件否定,我们就把数字\(n\)添加到\(arr\)中并把\(start\)替换为\(n\),如果计算出的新的\(n\)等于数组\(arr\)的第一个元素,则意味着我们找到了一个亲和数链,我们可以将其返回。

最后我们对一万至一百万以内的数字使用\(amicable\_chain\)函数,之所以使用这个区间,是因为我们发现一万以下只有完美数和亲和数对,所以链条长度只为一和二,不可能是最长的。实际上,这个问题也可以转化成一个图论问题,即在有向图寻找一个环的问题,但是经过尝试,用时比我这里的算法要长很多,不能在一分钟内得到答案,我就不展示相应的代码了。

# time cost = 16.2 s ± 343 ms

import numpy as np

def div_sum_dict(N=10**6):
    arr = np.zeros(N,dtype=int)
    k = 1
    for i in range(N//2):
        arr[i+k::k] += k
        k += 1
    res = {i+1:arr[i] for i in range(N)}
    return res

divsum = div_sum_dict()

def amicable_chain(start):
    arr = [start]
    while True:
        n = divsum.get(start)
        if n == arr[0]:
            return arr
        elif n == 1 or n > 10**6 or n in arr:
            return None
        else:
            arr.append(n)
            start = n

def main():
    res = [amicable_chain(i) for i in range(10000,10**6)]
    return min(max([x for x in res if x!=None],key=len))