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

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?

Analysis

Did you know that 60-length chains (and others) always start with a given set of values? Neither did we until we ran some tests and noted that it does. We even came up with a way to calculate these values for any length string for any limit. The margin of this page, unfortunately, does not provide enough room to write it down.

Anyway, most other solutions couldn’t handle 10^12, but this can. Just supply more signatures. We have enough for 10^8. We also included a file of values from 0 to 10^8 that have a 60-length chain and its signature. Not sure why, really, just did it.

Project Euler 74 Solution

Comments

• File containing 62058 integer pairs of n and n’s signature for 60-length chains for L < 100,000,000.
• Function sof_digits is listed in Sum of the factorials of the digits of n