Project Euler 74: Determine the number of factorial chains that contain exactly sixty non-repeating terms.

Project Euler 74: Determine the number of factorial chains that contain exactly sixty non-repeating terms.

Written by on 10 December 2011

Topics: Project Euler

And now for something completely different. Problem 74 of Project Euler has as far as I know nothing to do with proper fractions nor Farey sequences. So let’s have a look at the problem description

The number 145 is well known for the property that the sum of the factorial of its digits is equal to 145:

1! + 4! + 5! = 1 + 24 + 120 = 145

Perhaps less well known is 169, in that it produces the longest chain of numbers that link back to 169; it turns out that there are only three such loops that exist:

169 → 363601 → 1454 → 169
871 → 45361 → 871
872 → 45362 → 872

It is not difficult to prove that EVERY starting number will eventually get stuck in a loop. For example,

69 → 363600 → 1454 → 169 → 363601 (→ 1454)
78 → 45360 → 871 → 45361 (→ 871)
540 → 145 (→ 145)

Starting with 69 produces a chain of five non-repeating terms, but the longest non-repeating chain with a starting number below one million is sixty terms.

How many chains, with a starting number below one million, contain exactly sixty non-repeating terms?

I have made 3 different solutions for this problem but before we even start to look at these solutions there is something all of them need. A way to calculate the factorial sum. Back in Problem 34 we dealt with making factorial sums. So I have more or less reused that code, but handcoded the factorials from 0-9. The code looks like

int[] f = {1,1, 2, 6, 24, 120, 720, 5040, 40320, 362880};
public int FacSum(int n){
    int temp = n;
    int facsum = 0;

    while (temp > 0) {
        facsum += f[temp % 10];
        temp /= 10;
    }
    return facsum;
}

All the solutions I have found here use some sort of brute force. With those words of wisdom, I believe we are ready to look at the first solution. The first one stores the current solution in a list and is just pure brute force. The second solution implies a caching strategy to avoid calculating things twice. The third uses almost no memory as the stopping criteria are changed such that we can avoid using a list to store the current sequence in. I think we are ready to look at the first solution now.

Brute force

The first solution is just pure brute force. For every number I build a list of the sequence, and once I find a number which is already contained in the list I stop. This is implemented in C# as

int limit = 1000000;             
int result = 0;
            
for(int i = 1; i <= limit; i++){
    int n = i;
    List<int> seq = new List<int>();
                
    while(!seq.Contains(n)){
        seq.Add(n);
        n = FacSum(n);
    }
                
    if (seq.Count == 60) result++;                
}

Running it gives

There are 402 chains of length 60
Solution took 6584 ms

which is not pretty at all. 6.5s for finding a solution for this problem just doesn’t cut it.

Caching the result

For this solution I am caching the result. So if we have the sequence

69 → 363600 → 1454 → 169 → 363601 (→ 1454)

there is no need to redo the calculations once we reach 363600, we already know how long the sequence is since we encountered the number for the sequence starting with 69.

Rereading the problem description I realised that there only consists three loops which are entered if we reach one of the loops 169, 871 or 872. Alternatively the sequence ends up with one number mapping to itself. This allows us to change the stop criteria a bit along with caching the solution. My C# implementation loops like

int limit = 1000000;            
int result = 0;
int[] seqlengths = new int[limit+1];
seqlengths[169] = 3;
seqlengths[363601] = 3;
seqlengths[1454] = 3;
seqlengths[871] = 2;
seqlengths[45361] = 2;
seqlengths[872] = 2;
seqlengths[45362] = 2;

for (int i = 1; i <= limit; i++) {
    int n = i;                
    int count = 0;
    List<int> seq = new List<int>();
    seq.Add(0);
                
    while (seq[seq.Count-1] != n) {                    
        seq.Add(n);
        n = FacSum(n);
        count++;

        if(n <= limit && seqlengths[n] > 0){
            count += seqlengths[n];
            break;
        }
    }
    if (count == 60) result++;

    for (int j = 1; j < seq.Count; j++) {
        if (seq[j] <= limit) seqlengths[seq[j]] = count;                    
        count--;
    }
}

Using this solution yields

There are 402 chains of length 60
Solution took 118 ms

which is significantly faster than the other.

Memory limited solution

The last solution I will present here is slower than the second solution. However, it has the advantage that it does not use much memory. It utilises no sorts of arrays and therefore I like it. By know we know that the stopping criteria of a sequence is one of the 7 numbers listed above or a number which maps into itself. Therefore we can make some code looking like this

int limit = 1000000;
int result = 0;

for (int i = 1; i <= limit; i++) {
    int n = i;
    int last = 0;
    int count = 0;
    while (n != last &&
           n != 169 && n != 363601 && n != 1454 &&
           n != 871 && n != 45361 &&
           n != 872 && n != 45362) {
        last = n;
        n = FacSum(n);
        count++;
    }

    if (count == 57 &&
       (n == 169 || n == 363601 || n == 1454))
        result++;
}

It executes as

There are 402 chains of length 60
Solution took 1436 ms

which is 10 times slower than the caching solution, but I still like it.

Wrapping up

I presented you three different solutions for problem 74, non of them were below 100ms, but the solution using caching was fast enough for the purpose of finding a solution.

I have uploaded the source code, if you want a closer look. You can find it here. If you have other solutions, especially faster than mine, please leave a comment on the blog and let me know what you have found out. Comments and questions are of course welcome as well.

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

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

  1. Arun kumar says:

    while (seq[seq.Count-1] != n)

    can you please explain me this line?
    Why are you not using contains() method ,i.e., not check whether the entire list contains the number, but checking only the last entry?

  2. Arun kumar says:

    while (seq[seq.Count-1] != n)

    can you please explain me this line?
    Why are you not using contains() method ,i.e., not checking whether the entire list contains the number, but checking only the last entry?

  3. Amir says:

    Your second approach, Caching the result, is not working correctly!

    Assume you first compute and store the length of the chain for 169 (and not any number else).
    Then your code claims the length of chain for 69 to be 6 instead of 5.

    You are lucky that your code works for this problem!

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=""> <s> <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

This site uses cookies.