Duncan's blog

December 18, 2014

Project Euler: problem 46 – Goldbach’s other conjecture

Filed under: PHP,Project Euler — duncan @ 11:57 pm
Tags: , , ,

46I’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 46:

It was proposed by Christian Goldbach that every odd composite number can be written as the sum of a prime and twice a square.

9 = 7 + 2×12
15 = 7 + 2×22
21 = 3 + 2×32
25 = 7 + 2×32
27 = 19 + 2×22
33 = 31 + 2×12

It turns out that the conjecture was false.

What is the smallest odd composite that cannot be written as the sum of a prime and twice a square?

This was another of those problems that I’d initially passed over, having decided it looked a bit tricky.  Then looking at it again realised it probably wasn’t too difficult.  And I turned out to be right!

A composite number is basically any positive integer that isn’t a prime number.

My logic is simply:

  • Loop through odd numbers, from 3 upwards.
  • For each number, if it’s prime, add it to an array of primes for later reference.
  • If it’s not prime, work out if it matches the conjecture:
    • Subtract the next largest prime, then examine the remainder
    • Divide the remainder by 2.  if it’s a square number then we’re meeting the conjecture.  Move onto the next odd number.
    • Otherwise keep subtracting the primes, checking the remainders.
    • If we’ve looped through all the primes then we must have reached a number that doesn’t meet the conjecture.

This runs in about 40ms:

<?php
$primes = [2];

$i= 1;

while (true) {
	$i+= 2;

	if (isPrime($i)) {
		$primes[] = $i;
	} else {
		for($j = count($primes)-1; $j > 0; $j--) {
			$remainder  = $i - $primes[$j];
			$remainder = $remainder / 2;
			$root = sqrt($remainder);
			if ((int) $root == $root) {
				continue 2;
			}
		}
		
		echo $i;
		break;
	}
}


function isPrime($x)
{
	$root = sqrt($x);
	
	for ($i = 3; $i <= $root; $i += 2) {
		if ($x % $i == 0) {
			return false;
		}
	}
	
	return true;
}

I’m using a modified version of my original isPrime function, just because I know I don’t need to check for even numbers.

The loop backwards through the primes was maybe a bit of overkill; using a simple foreach loop through the primes in ascending order took more like 100ms.

What else… I check if a square root is the same as when it’s cast to an integer (not sure this is the best approach).  Then use continue 2; to get out of our inner-most loop and move onto the next value in our parent loop.

2 Comments »

  1. You could possibly expedite this by optimising your prime look-up. You don’t need to check whether the number is divisible by every odd number, you only need to check if they’re divisible by other primes. This does require maintaining the list of previously discovered primes though, but this is probably OK in this context as you seem to be counting up anyhow (I did not look at the entirety of the logic). Or I did write that prime generator thing a while back… you could pinch that if you wanted to… http://blog.adamcameron.me/2014/09/php-another-generator-example-primes.html


    Adam

    Comment by dacameron — December 19, 2014 @ 12:17 am | Reply

    • ah ok, good call. It probably won’t make much difference here, but that could be useful for some of the other Euler puzzles where you’re looping over primes into the millions

      Comment by duncan — December 19, 2014 @ 9:10 am | 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: