Problem 46 of Project Euler reads

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×1^{2}

15 = 7 + 2×2^{2}

21 = 3 + 2×3^{2}

25 = 7 + 2×3^{2}

27 = 19 + 2×2^{2}

33 = 31 + 2×1^{2}

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?

We will work with a Goldbach Conjecture. Not THE Goldbach conjecture. The Goldbach conjecture states

Every even integer greater than 2 can be expressed as the sum of two primes

That one is still an unsolved problem in mathematics and I wont try to deal with that here.

Back to the main problem. I haven’t found ways to solve this except for brute force, but I have found three slightly different approaches brute forcing the problem.

- Generate a list of primes and a list of squares. Sum them up and check which is the smallest odd integer that has not been hit.
- Generate a list of squares and check odd numbers to see if the number minus twice a square is a prime.
- As number two but make a list of primes instead and check if the difference is twice a square.

The first option has the disadvantage that I don’t really know when to stop generating the lists, we might generate one list too big or the other. The second and third option are very similar in approach. The third option has the advantage that subtracting a prime we are left with something we need to check if that is twice a square. It can be done by an inverse function and thus we only need to generate a list of primes. So lets go for that strategy.

## The Algorithm

I have sort of explained approach already. For each odd number (n) we will check if n-p is twice a square for the all primes (p) less than n.

I know it starts to become boring, but the easiest way is to use an inverse function like the previous couple of problems. In this case the function looks like

private bool isTwiceSquare(long number) { double squareTest = Math.Sqrt(number/2); return squareTest == ((int)squareTest); }

and the main loop looks like

int[] primeList = ESieve(10000); int result = 1; bool notFound = true; while(notFound){ result += 2; int j = 0; notFound = false; while (result >= primeList[j]) { if(isTwiceSquare(result-primeList[j])){ notFound = true; break; } j++; } }

When we execute the code we get

The smallest counter example is 5777 Solution took 6 ms

which was a number much smaller than what I had expected.

## Wrapping up

I must admit that I don’t have that much to say about this problem. As usual the source code is available. One thing I have found interesting is this small article by Laurent Hodges describing the conjecture and development of it. It is a mere three pages long and states that the only two numbers that has been found as counter examples are 5777 and 5993.

I can add to the article that checking numbers up to 4.000.000.000 does not yield new results.

Which one is faster?

squareTest == ((int)squareTest)

or

squareTest == Math.Floor(squareTest)

squareTest == ((int)squareTest)

seems to be faster.

Yep, seeing your first post I tried both options as well, and the one you point at seems to be a whole lot faster.

/Kristian

When a smart friend of mine was going to check if a number was an integer, and having never done that before, he came up with n % 1 == 0. I’ve never seen anyone do that before, even though it makes perfect sense. I did a quick benchmark and saw that it was faster than using n == Math.Floor(n) or n == Math.Truncate(n), but n == (int)n is still way faster.

Just wanted to share 🙂

Thanks for sharing.

I don’t think I would ever use that way of doing it though. If I want readability I would probably use the flooring function and if I wanted speed I would use the n == (int) n.

However, it is always great with new input.

/Kristian

I adopted the same approach with a minor change.

Instead of creating a list of primes beforehand, I modify the list on the fly. You can’t be sure if your list of prime is too small or too big.

To counter that, I check the number, if it is prime, I add it to the prime list else I check for the conjecture condition. This approach has an advantage of having the just appropriate number of primes. Moreover, I start checking from the end of the list instead of beginning. I am not sure if it gives any advantage. Overall, this approach saved a little bit of time and I get the result in 1 ms.

That is a brilliant approach. I just made an estimate of how much I would need and then went on to use that prime list. But yours would scale better.

Table 1

Odd composites (OC) generated by equations:

[OC = p + 2 x (53^2)] or [OC = p + 2 x (54^2)]

where p is an odd composite.

http://img11.hostingpics.net/pics/895027pe46table1.jpg

Table 1 begins with 5777 and 5993, the smallest odd composites that cannot be written as the sum of a prime and twice a square.

We can see a list of odd composites (OC) generated by equations :

[OC = p + 2 x (53^2)] or [OC = p + 2 x (54^2)]

where p is an odd composite.

With the exception of 5777, this sequence shows excerpts from ref. (2).

Sources to the comment above :

1) Microsoft Office Excel (2007)

2) A lesser-known Goldbach conjecture

LAURENT HODGES

Physics Department, Iowa State University

http://learning.physics.iastate.edu/hodges/mm-1.pdf

3) Prime Factorization Calculator

http://www.mathblog.dk/tools/prime-factorization/

An improvement would be to subtract 2*squares and then check if the remainder is a prime; The amount of checks is lower, as 2*squares is very low when i grows. Also no need for generating primes or keeping lists.

Simply put, the amount of primes to check in e.g. 5735 is way higher then the amount of 2*squares.

Isn’t something missing? You never check if result is a composite number but you go through every odd number. This way it should fail right away with result = 3. Am I missing something?

hi

my question is about 5777!

couldn’t it be written as 3599 + 2 * 33 ^ 2 ??

so it is sum of a prime (3599) and twice a square (2 * 1089)

3599 is not a prime number – it is divisible by 59 and 61.

5977 Can be written as 5927 + 2*5^2 Where 5927 is a prime.

This is about 5777, not 5977.