Project Euler 95:Amicable chains 亲和数链

The proper divisors of a number are all the divisors excluding the number itself. For example, the proper divisors of 28 are 1, 2, 4, 7, and 14. As the sum of these divisors is equal to 28, we call it a perfect number.

Interestingly the sum of the proper divisors of 220 is 284 and the sum of the proper divisors of 284 is 220, forming a chain of two numbers. For this reason, 220 and 284 are called an amicable pair.

Perhaps less well known are longer chains. For example, starting with 12496, we form a chain of five numbers:

12496 → 14288 → 15472 → 14536 → 14264 (→ 12496 → …)

Since this chain returns to its starting point, it is called an amicable chain.

Find the smallest member of the longest amicable chain with no element exceeding one million.

亲和数链

一个数除了本身之外的因数称为真因数。例如，28的真因数是1、2、4、7和14。这些真因数的和恰好为28，因此我们称28是完全数。

有趣的是，220的真因数之和是284，同时284的真因数之和是220，构成了一个长度为2的链，我们也称之为亲和数对。

有一些更长的序列并不太为人所知。例如，从12496出发，可以构成一个长度为5的链：

12496 → 14288 → 15472 → 14536 → 14264 (→ 12496 → …)

由于这条链最后又回到了起点，我们称之为亲和数链。

找出所有元素都不超过一百万的亲和数链中最长的那条，并给出其中最小的那个数。

解题

暴力应该可以的，直觉是简单的。如果对每个数求出其真因子的和，然后再求真因子和的真因子和，这样的时间复杂度很好，表示没有跑出来结果。然后发现这里的计算真因子的和的过程中重复的数很多的。所以可以先求出真因子的数的和，这样就是一个数组，下面的问题就是在数组中求第一个最长链的开始的值，这里开始没有理解对，以为是求最长链中许多数中的最小值那个，但是发现最长链的最小值就是其第一个值。还有上面也说了是求的第一个最长链，所以主要小于100万的最长链长度是28 有好多个的。

那么如何求亲和数链？

注意：

1.不是每个数有亲和数链的，如这个链接说的也是比较有意思的

问题还是如何找到链？

很显然的是我们发现从a 开始的链会从 a结束，这个是有顺序要求的

可以发现，是亲和数链的时候不会出现环，这个很显然，但是也是解题的关键

所以发现环了就要结束

然后再判断结束时候的值和原始开始的值是否相等，相同求其长度。

JAVA

package Level3;

import java.util.TreeSet;

public class PE094{
    public static void run2(){
        int MAX = 1000000;
        int[] next = new int[MAX];
        // 真因数的和 
        for(int i=2;i<MAX;i++)
            next[i] = 1;
        
        for(int i=2;i<MAX/2+1;i++)
            for(int j=2*i;j<MAX;j+=i){
                next[j] +=i;
            }
        int longest = -1;
        int subMIN = Integer.MAX_VALUE;
        int MIN = Integer.MAX_VALUE;
        int j =2;
        TreeSet<Integer> set = new TreeSet<Integer>();
        for(int i=2+8;i<MAX;i++){
            set.clear();
            j = i;
            // 记录最小值 
            subMIN = j;
            set.add(j);
            while(true){
                j = next[j];
                if(j>=MAX) break;
                // 记录最小值
                subMIN = subMIN>j?j:subMIN;
                // 出现循环 结束 
                if(set.contains(j)==true)
                    break;
                set.add(j);
            }
            if( j==i ){
                // 这个的不好，在相同的长度时候 进行了更新 
//                longest = Math.max(set.size(), longest);
                // 记录长度最小的那个 这里在相同的长度时候只记录最小的 
                if(set.size() >longest){
                longest = set.size();
                MIN = subMIN;
                System.out.println(longest +"   "+MIN + "  "+ j);
                }
            }
        }
        System.out.println(longest +"   "+MIN);
    }
    public static void main(String[] args) {
        long t0 = System.currentTimeMillis();
        run2();
        long t1 = System.currentTimeMillis();
        long t = t1 - t0;
        System.out.println("running time="+t/1000+"s"+t%1000+"ms");

    }
}

结果

  28  28
  220  220
  12496  12496
  14316  14316
  14316
running time=2s415ms

第一个数是链的长度，链的最小值，链的第一个数

其实是比较多的，题目求的是第一个最长链，直接看题目容易误解。

在上面求真因数的和中，和筛选法求素数的思想很类似，知道数的规律，进行求解。

Python 是直接在论坛中找到

# coding=gbk

import time as time 

def run():
    MAX = 1000000
    d = [1]*MAX 
    for i in xrange(2,MAX//2):
        for j in xrange(2*i,MAX,i):
            d[j]+=i 
    max_cl = 0
    for i in xrange(2,MAX):
        n,chain = i,[]
        while d[n]<MAX:
            d[n],n = MAX+1,d[n]
            try:k=chain.index(n)
            except ValueError:chain.append(n)
            else:
                if len(chain[k:]) >max_cl:
                    max_cl,min_link = len(chain[k:]),min(chain[k:])
    print min_link 
t0 = time.time()
run() 
t1 = time.time()
print "running time=",(t1-t0),"s"
running time= 5.47899985313 s