Duncan's blog

October 28, 2014

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

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

74I’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!

Leave a Comment »

No comments yet.

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Blog at WordPress.com.

%d bloggers like this: