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:                \$<
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 :)

 Interpreter steps: 376 912 541 Execution time (BefunExec): 49s (7.66 MHz) Program size: 1224 x 833 Solution: 402 Solved at: 2015-08-25

made with vanilla PHP and MySQL, no frameworks, no bootstrap, no unnecessary* javascript