Digit factorial chains

2015-08-25

Problem 074: Digit factorial chains

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?

Solution:

v      X ##########            // Project Euler - Problem 74
CCC
XXXX   |------------------------------------------------------------|

# ... #
. . . .
.  .  .
. . . .
# ... #

>98+8*9*11p"+&"*2/21p"}}@"**31p042p31g>1-:0\:11g%v
vg11:-8*:+"W~"2p+4/g11\%g11:/3*"'C"2p<|:p+4/g11\ <       v   <
%>8-:11g%\11g/4+p3",!"*2+:11g%\11g/4+^$      >:70g:1+70p9 +0v
\^**"CCQ"3p+4/g11\%g11:+"+~"3p+4/g11\<>070p11|-+55g07*g07  p<^          p22+g22_v
>11g/4+p2"m"8*:11g%\11g/4+ v         ^%g11:00<           # >:55+%9+0v>11g/4+g: ^$
v1$p+4/g11\%g11:-7*:+"W~"2p<>12g22g1+:22p9+2p32g1+32p12g0\:|:/+55\g <^\%g11:g21<
>:12p022p092p032p32g9+2g12g-|-g21g2+9g23                  <>$>\# :#+_+:12p31g`!|
v                          <                            <^                    <<
+>22g"<"-#v_42g1+42p>1>:9+2g31g`#v_::22g1+\-\9+2v
1 >$42g.@ >         ^ ^+1_v#-g23:<p+4/g11\%g11:g<
^_^#-g13:                $<

Download

This program is too big to display/execute here, click [download] to get the full program.

Explanation:

The factorial part is pretty easy - we cache the factorials from 1 to 9 and then we can calculate facdigitsum(n) in O(log_10(n)).

The problemdescription tells us there are only seven numbers in a loop ({169, 363601, 1454}, {871, 45361}, {872, 45362}). So every other chain ends with a number mapping to itself. We manually insert these seven numbers in our grid and calculate the rest (where we only need to test if f(n) == f(n-1)).

And we cache ever calculated value of chainlength() in our 1000000-element array. So as soon as we reach an already calculated number we can stop. This works because there are no loops (except the seven pre-inserted values) and every chain is strictly linear.

Be sure to check out the pre-optimized version of this to see just how much more condensed this version is :)