Project Euler 95: Find the smallest member of the longest amicable chain with no element exceeding one million.

Project Euler 95: Find the smallest member of the longest amicable chain with no element exceeding one million.

Written by on 5 May 2012

Topics: Project Euler

Even though we are still below 5000 people who have solved Problem 95 of Project Euler this problem it proved to be a relatively easy problem to solve. The main challenge was to find a method to get the speed of the solution to reasonable level. The problem reads

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.

I managed to make two solutions which differs in the way they calculate the sum of factors. Otherwise they are the same. The first solution relies on a function to return the sum of factors when needed. This method I will cover first.

Brute force

At first I used a very stupid method for calculating the sum of factors at least until I realized that we had spent the majority of Problem 21 generating methods for calculating the sum of factors in an efficient way. So I will refer you to that problem in order to see solution to see how this function works.

Once we have a way to generate the sum of factors we need to identify the chains we can generate. I have done this by looping through all numbers and generate chains until I reach a number which is in the chain, is above the limit,  or has been searched before.

If the identified number is one of the latter two options this is nor a valid chain, and thus I stop investigating. If it is the first option that the number is already in the current chain. I find the loop part of it (which does not have to be from the beginning). And then I check if that is longer than the current longest chain. If so we have a new candidate chain.

So it is mainly a bit of logic to sort through all the numbers.  The C# implementation I have made looks like

int limit = 1000000;
int result = 0;
int chainLength = 0;

bool[] numbers = new bool[limit + 1];

for (int i = 2; i < limit + 1; i++) {
    if (numbers[i]) continue;
    List<int> chain = new List<int>();

    int newNumber = i;
    bool broken = false;

    while (!chain.Contains(newNumber)) {
        chain.Add(newNumber);
        newNumber = sumOfFactors(newNumber);

        if (newNumber > limit || numbers[newNumber]) {
            broken = true;
            break;
        }
    }

    if (!broken) {
        int smallest = int.MaxValue;
        int first = chain.IndexOf(newNumber);

        if (chain.Count - first > chainLength) {
            for (int j = first; j < chain.Count; j++) {
                if (chain[j] < smallest)
                    smallest = chain[j];
            }

            chainLength = chain.Count - first;
            result = smallest;
        }
    }

    for (int j = 0; j < chain.Count; j++) {
        numbers[chain[j]] = true;
    }
}

This runs in

The smallest number in the intest chain is 14316
Solution took 344,8525 ms

So it is not that great a result. I know I have made it a bit more complicated than I had to since I actually kept track of already searched numbers. If you don’t do that you can multiply the solution time by a factor of 10 for this solution.

Sieving

Once I started messing around with the solution from Problem 24, or more particular the sieve used in Problem I realized that since we need all numbers up to the limit it would probably be faster to sieve them instead. So I decided to make a small sieve for the sum of factors. Such that I run through all numbers starting from 1, and every for every multiplum of that number I add the number since it will be a factor for the number. I have implemented the sieve as this

private void generateFactors(int limit) {
    sumOfFactorsList = new int[limit + 1];
    for (int i = 1; i <= limit / 2; i++) {
        for (int j = 2 * i; j <= limit; j += i) {
            sumOfFactorsList[j] += i;
        }
    }
}

The result is a list of the sum of factors for all numbers less than or equal to the limit. All I have done is to change the method of calculating the sum of factors in line 16. You can see the whole source code here.

This reduced the solution time to

The smallest number in the intest chain is 14316
Solution took 114,3127 ms

After that I don’t have ideas how to improve the problem significantly.

Wrapping up

Yet another problem solved in Project Euler. This time not with the fastest solution speed, but by using sieving and caching we managed to lower it significantly from the most brute force approach I could conjure up in the beginning.

As usual I would urge you to ask questions and point out mistakes if you find them as well as show your solution to this problem. You can find the source code here.

The blog image for today is used under the creative commons license, and is kindly shared by Prantanti. Thanks for letting me borrow it.

5 Comments For This Post I'd Love to Hear Yours!

  1. Bjarki Ágúst says:

    Are you sure you’re talking about Problem 24? I’m pretty sure it had nothing to do with sum of divisors.

  2. Kristian says:

    No, I am actually pretty sure that I didn’t mean problem 24. I meant problem 21 and it is corrected now. Thanks.

  3. BabakSairafi says:

    Hello Kristian
    your code is good, continue I write my code that you see and tell me abou it.
    of course I think our code could faster than this, if operator new and add to it cleared and use from global array
    operator new and method add cause slow code although about this problem not need.

            const int max = 1000000;
            int[] sigma = new int[max + 1];
            int[] l = new int[max + 1];
    
            void calcSigma()
            {
                for (int i = 1; i <= max; i++)
                    for (int j = 2 * i; j <= max; j += i)
                        sigma[j] += i;
            }
    
            int euler95()
            {
                calcSigma();
                for (int i = 1; i <= max; i++)
                    if (l[i] == 0)
                    {
                        List<int> list = new List<int>();
                        int n = i;
                        list.Add(n);
                        while (true)
                        {
                            n = sigma[n];
                            if (n >= max || l[n] == -1)
                            {
                                l[i] = -1;
                                break;
                            }
                            int h = list.IndexOf(n);
                            if (h != -1)
                            {
                                for (int j = 0; j < h; j++)
                                        l[list[j]] = -1;
    
                                for (int j = h; j < list.Count; j++)
                                        l[list[j]] = list.Count - h;
                                break;
                            }
                            else
                                list.Add(n);
                        }
                    }
    
                int m = -1, pos = 0;
                for (int i = 0; i <= max; i++)
                    if (m == -1 || l[i] > m)
                    {
                        m = l[i];
                        pos = i;
                    }
                return pos;
            }
    
            private void button1_Click(object sender, EventArgs e)
            {
                int s = Environment.TickCount;            
                textBox1.Text = euler95().ToString();
                Text = (Environment.TickCount - s).ToString();
            }
    

    regards

  4. Kristian says:

    I am not sure what your question is here. Are you trying to make the code I made faster? In that case, it would be fun if you could post both the execution time you get with your code and the one you get with my code.

  5. anonymous says:

    By definition, the solution must be the smallest number in its chain. You can speed up the solution greatly by breaking out of the loop whenever newNumber < i.

Leave a Comment Here's Your Chance to Be Heard!

You can use these html tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

You can use short tags like: [code language="language"][/code]

The code tag supports the following languages: as3, bash, coldfusion, c, cpp, csharp, css, delphi, diff,erlang, groovy, javascript, java, javafx, perl, php, plain, powershell, python, ruby, scala, sql, tex, vb, xml

You can use [latex]your formula[/latex] if you want to format something using latex

Notify me of comments via e-mail. You can also subscribe without commenting.