Archive for Project Euler

Sum of Amicable Pair

I was quite fascinated by the problems presented in Project Euler when I first knew about it. I am quite fond of mathematical problems and interested in programming which brought me a strong will of solving them. Till date, I haven’t solved much of a problem (Around 22 I suppose) but I am trying it whenever I got time.

One of the problem which I am presenting here the solution for, is Amicable Pair. I wasn’t aware of what that means when I read the problem first and after knowing what it meant, I was quite curious about the numbers and their properties. Here is what it means.

Let d(n) be defined as the sum of proper divisors of n (numbers less than n which divide evenly into n). If d(a) = b and d(b) = a, where a ≠ b, then a and b are an amicable pair and each of a and b are called amicable numbers.

Fascinating, isn’t it? Now, since writing a code for this problem is not much of a deal here as it sounds quite simple, yet writing an efficient algorithm is the main gist here. And that’s what Project Euler stands for, Writing Efficient Algorithm. I am not quite sure of, if my algorithm is efficient (which I obviously don’t think so) but I am eager to learn what could be the best efficient algorithm for solving this kind of problem. So, if you have better solution and wants to share, please drop some comments! That would be appreciated. And for people who are looking into some help, I am sure the following code snippet would be.

/**
* Evaluate the sum of all amicable pairs under 10000
* @author _uJJwAL_
* @copyright 2012
*/
function sumOfDivisor($num) {
	$sum = 1;
	
	for($j = 2; $j <= $num / 2; $j++) {
		if($num % $j == 0) {
			$sum += $j;
		}
	}
	
	return $sum;
}

function sumOfAmicablePair($maxLimit) {
	$total = 0;
	
	for($a = 2; $a < $maxLimit; $a++) {
		$b = sumOfDivisor($a);

		if($b > $a) {
			if(sumOfDivisor($b) == $a){
				//echo 'Amicable Pair ' . $a. '   '. $b. PHP_EOL;
				$total += $a + $b;
			}
		}
	}
	
	return $total;
}

echo 'Sum of Amicable Pair: ' . sumOfAmicablePair(10000) . PHP_EOL;
www.000webhost.com