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

Written by on 4 June 2011

Topics: Project Euler

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.

14 Comments For This Post I'd Love to Hear Yours!

  1. SuprDewd says:

    Which one is faster?

    squareTest == ((int)squareTest)

    or

    squareTest == Math.Floor(squareTest)

  2. SuprDewd says:

    squareTest == ((int)squareTest)

    seems to be faster.

  3. Kristian says:

    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

  4. SuprDewd says:

    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 🙂

  5. Kristian says:

    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

  6. Shobhit says:

    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.

  7. Kristian says:

    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.

  8. Jean-Marie Hachey says:

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

  9. Jean-Marie Hachey says:

    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/

  10. Fluttert says:

    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 answer = 0;
    	long i = 9;
    	bool GoldbachFound = false;
    	while (!GoldbachFound)
    	{
    		if (!IsPrime(i))
    		{	// odd composite number
    			for (int j = 1; j < i; j++)
    			{	// check for primes up to 2*j*j < i
    				long twiceSquare = 2*j*j;
    				if (twiceSquare <= i)
    				{
    					if (IsPrime(i - twiceSquare))
    					{
    						//Console.WriteLine("{0} = 2*{1}^2 + {2}", i, j, (i - twiceSquare));
    						break;
    					}
    				}
    				else
    				{	// first counter example
    					GoldbachFound = true;
    					answer = i;
    				}
    			}
    		}
    		i+=2; // next odd number
    	}
    	sw.Stop();
    	Console.WriteLine("Answer: {0}", answer); // Answer Euler 46: 5777 , runs in 1 ms
    	Console.WriteLine("Runtime in milliseconds: {0}", sw.ElapsedMilliseconds);
    	Console.ReadKey();
    }
    
    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 < 4) { return false; }
    	long maxFactor = (long)Math.Sqrt(candidate);
    	for (int p = 5; p <= 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
    }
    
  11. Henrik says:

    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?

  12. mhsa says:

    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)

  13. nzqri says:

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

  14. ksdme says:

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

Leave a Comment Here's Your Chance to Be Heard!

You can use these html tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

You can use short tags like: [code language="language"][/code]

The code tag supports the following languages: as3, bash, coldfusion, c, cpp, csharp, css, delphi, diff,erlang, groovy, javascript, java, javafx, perl, php, plain, powershell, python, ruby, scala, sql, tex, vb, xml

You can use [latex]your formula[/latex] if you want to format something using latex

This site uses cookies.