# Project Euler 46: What is the smallest odd composite that cannot be written as the sum of a prime and twice a square?

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×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?

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.

1. 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.
2. Generate a list of squares and check  odd numbers to see if the number minus twice a square is a prime.
3. 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. ### Posted by Kristian SuprDewd

Which one is faster?

squareTest == ((int)squareTest)

or

squareTest == Math.Floor(squareTest) SuprDewd

squareTest == ((int)squareTest)

seems to be faster. Kristian

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 SuprDewd

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 🙂 Kristian

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 Shobhit

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. Kristian

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. Jean-Marie Hachey

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). Jean-Marie Hachey

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/ Fluttert

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.

```private static void Main(string[] args)
{
Stopwatch sw = new Stopwatch(); sw.Start();	// for timing
long i = 9;
bool GoldbachFound = false;
while (!GoldbachFound)
{
if (!IsPrime(i))
{	// odd composite number
for (int j = 1; j &lt; i; j++)
{	// check for primes up to 2*j*j &lt; i
long twiceSquare = 2*j*j;
if (twiceSquare &lt;= i)
{
if (IsPrime(i - twiceSquare))
{
//Console.WriteLine(&quot;{0} = 2*{1}^2 + {2}&quot;, i, j, (i - twiceSquare));
break;
}
}
else
{	// first counter example
GoldbachFound = true;
}
}
}
i+=2; // next odd number
}
sw.Stop();
Console.WriteLine(&quot;Runtime in milliseconds: {0}&quot;, sw.ElapsedMilliseconds);
}

public static bool IsPrime(long candidate)
{	// rule out 2 and 3
if (candidate == 2 || candidate == 3) { return true; }
// Even number check
if (candidate % 2 == 0 || candidate%3 == 0 || candidate &lt; 4) { return false; }
long maxFactor = (long)Math.Sqrt(candidate);
for (int p = 5; p &lt;= maxFactor; p += 6)
{	// all primes are 6n+1 or 6n-1; Only applies if 2 and 3 are already ruled out
if (candidate % p == 0 || candidate % (p+2) == 0)
{	// number is divisible, thus not prime
return false;
}
}
return true; // not divisible, thus prime
}
``` Henrik

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? mhsa

hi
couldn’t it be written as 3599 + 2 * 33 ^ 2 ??
so it is sum of a prime (3599) and twice a square (2 * 1089) nzqri

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

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

This is about 5777, not 5977. DrCocktor

I wonder if there are any more odd composite numbers that are
counterexamples. Moonfair

Hi,Kristian!
Sorry, but I’m a little confhow can you be sure that the upper limit of primes is 10000 before you get answer? Moonfair

Hi,Kristian!
Sorry, but I’m a little confused about how can you be sure that the upper limit of primes is 10000 before getting the answer? Lincoln Liu

I was the 57757th person to solve it!