# Duncan's blog

## October 28, 2014

### Project Euler: problem 74 (PHP) – Digit factorial chains

Filed under: PHP,Project Euler — duncan @ 8:00 am

I’m doing these Project Euler mathematical puzzles as a simple practical exercise for teaching myself PHP, and I’d appreciate any feedback on my code.

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?

Code:

```<?php
\$countChains = 0;
\$limit = 1000000;
\$terms = 60;

\$factorials = getFactorials();

foreach (range(1, \$limit) as \$number) {
\$currentNumber = \$number;
\$count = 0;
\$chain = [\$currentNumber];

while (true) {
\$sum = 0;
\$count++;

\$digits = str_split(\$currentNumber);

foreach(\$digits as \$digit) {
\$sum += \$factorials[\$digit];
}

\$currentNumber = \$sum;

if (in_array(\$currentNumber, \$chain)) {
break;
}

\$chain[] = \$sum;

}

if (\$count == \$terms) {
\$countChains++;
}
}

echo \$countChains;

function getFactorials() {
\$factorials = [];

for (\$i = 0; \$i <= 9; \$i++) {
\$factorials[\$i] = factorial(\$i);
}

return \$factorials;
}

function factorial(\$x) {
\$factorial = 1;

for (\$i = \$x; \$i > 1; \$i--) {
\$factorial *= \$i;
}

return \$factorial;
}
```

Re-using the approach here from Problem 34, where I first calculated the factorials for the digits 0..9.

Then I loop from one to a million.  I create an array which initially contains the current number.  I then loop over the digits of that number, adding up the factorials of each digit.

If that value is already in our array, then we need to break out of the inner loop, as we’ve reached a repeating term.

Otherwise, add that into the array, and keep on adding up the factorial values of that new value, ad infinitum (well, ad 60 really).

After finishing with our inner loop, i.e. the point at which we’ve reached a repeating term, I check if the length of that chain was 60.

This is pretty slow stuff, taking over 2 minutes to execute!