# Duncan's blog

## December 18, 2014

### Project Euler: problem 46 – Goldbach’s other conjecture

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

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

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.

Advertisements

Blog at WordPress.com.