Duncan's blog

November 2, 2014

Project Euler: problem 95 (PHP) – Amicable chains

Filed under: PHP,Project Euler — duncan @ 3:50 pm

bike chainI’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 95:

The proper divisors of a number are all the divisors excluding the number itself. For example, the proper divisors of 28 are 1, 2, 4, 7, and 14. As the sum of these divisors is equal to 28, we call it a perfect number.

Interestingly the sum of the proper divisors of 220 is 284 and the sum of the proper divisors of 284 is 220, forming a chain of two numbers. For this reason, 220 and 284 are called an amicable pair.

Perhaps less well known are longer chains. For example, starting with 12496, we form a chain of five numbers:

12496 → 14288 → 15472 → 14536 → 14264 (→ 12496 → …)

Since this chain returns to its starting point, it is called an amicable chain.

Find the smallest member of the longest amicable chain with no element exceeding one million.

This puzzle took me a while to get right.  The question doesn’t really give you enough details I think, so it pays to do a bit of research into what perfect numbers, amicable pairs and amicable chains are.  Perfect numbers are an amicable chain with length = 1, and amicable pairs are amicable chains with length = 2.

Continuously adding up the divisors of numbers (the factors of a number apart from the number itself) is called the Aliquot sequence.  Eventually you should either end up running into an amicable chain, or you’ll reach a prime number (i.e. its divisors = 1, and you can’t go any further).  However there are theoretically numbers who’s Aliquot sequence never terminates.  I guess that’s why this question makes sure we don’t have any individual numbers over 1 million.

One thing that’s useful to know, the question doesn’t give you a clue on when you’ll know you’ve reached the longest amicable chain; I assumed it might be into the hundreds.  Fortunately the Wikipedia article on sociable numbers reveals that the longest one is a chain of only 28 numbers in length.

Code:

<?php
$start = microtime(true);

$number = 1;
$limit = 1000000;
$amicableChains = []; 
$length = 0;
$maxLength = 28;

while ($length < $maxLength) {
	$chain = [];
	$currentNumber = $number;

	while (true) {
		$divisors = getDivisors($currentNumber);
		$currentNumber = array_sum($divisors);
		
		if (array_key_exists($currentNumber, $amicableChains)) {
			$amicableChains[$number] = $amicableChains[$currentNumber];
			break;
		}
		
		if ($currentNumber == 1) {
			break;
		}
		
		// break out if we're over a certain length of number
		if ($currentNumber > $limit) {
			break;
		}
		
		if (in_array($currentNumber, $chain)) {
			$key = array_search($currentNumber, $chain);
			$amicableChains[$number] = array_slice($chain, $key);
			$length = count($amicableChains[$number]);
			break;
		}
		
		$chain[] = $currentNumber;
	}
	
	$number++;
}

uasort($amicableChains, function($a, $b) {
	return count($a) > count($b);
});


echo min(end($amicableChains));

$end = microtime(true);
printf("<br>Execution time: %dms", ($end - $start) * 1000);


function getDivisors($number) {
	$factors = [1];
	$root = sqrt($number);
	for ($i = 2; $i <= $root; $i++)
	{
		if ($number % $i == 0)
		{	// it's a factor
			$factor1 = $i;
			$factor2 = $number / $i;
			
			$factors[] = $factor1;
			
			if ($factor1 != $factor2) {
				$factors[] = $factor2;
			}
		}
	}
	
	return $factors;
}

So we loop until we’ve reached a chain with a length of 28+.

Within that loop we have an inner loop, where we calculate the sum of the divisors.  We break out of that inner loop if:

  • we reach a value we already have the amicable chain for
  • the sum of divisors reaches 1
  • we have a value that exceeds one million
  • we get to a value that we already have in the current chain, i.e. we’ve reached a new amicable chain

Initially I had some logic in that inner loop to break out if the current number equalled the previous number, i.e. we had reached a perfect number, an amicable chain of length = 1.  However that wasn’t really required, as the final if statement further down covered it anyway, and it didn’t really slow things down to just use that.

Once we get an amicable chain, I store that chain keyed on the number we’re currently looping over.  N.B this number may not be part of the chain itself.  For instance the divisors of 562 are 1, 2 and 281.  The sum of these is 284.  We already know that 284 is part of the amicable chain 220 → 284.  So the aliquot sequence for 562 is 220 → 284.

Once we’ve reached our limit of a chain with length of 28, I then use the uasort() function to have a user-defined function which sorts my array of amicable chains based on the length of each array within it.  Then I use end() to get the last of those amicable chains, i.e. the longest.  And min() to get the smallest value within that chain.

Job done, running time about 1.5 seconds on average.

 

Advertisements

1 Comment »

  1. If you are interested in number theory and recreational mathematics, and wish to practice your programming skills further, indulge yourself with these number curiosities: http://www.glennwestmore.com.au/category/advanced-number-curiosities/ or http://www.glennwestmore.com.au/category/number-curiosities/

    Comment by Glenn Westmore — June 3, 2016 @ 6:37 pm | Reply


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: