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.

Problem 74:

*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!

### Like this:

Like Loading...

*Related*

## Leave a Reply