Project Euler

Problem 46: Goldbach's Other Conjecture

9 = 7 + 2 x 1²
15 = 7 + 2 x 2²
21 = 3 + 2 x 3²
25 = 7 + 2 x 3²
27 = 19 + 2 x 2²
33 = 31 + 2 x 1²

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?

The Catch

How to tell when an odd composite number cannot be written as the sum of a prime and twice a square.

The Light

To prove Goldbach wrong, we have to find the first instance where an odd number cannot be written as the sum of a prime and twice a square. The algorithm to check whether an odd number satisfies the above condition is fairly simple: for every odd number n, start substracting prime numbers p from a list of prime numbers, one at a time (p ≤ n). If the difference is not twice a square, the corresponding number n will be the first instance to disprove Goldbach's other conjecture. In order to implement this algorithm, we need to:

• Provide a list of prime numbers. This can be done using the Sieve of Eratosthenes discussed in Problem 35.
• Check whether a quantity x is twice a square. Utilize the discussion of inverse functions in Problem 42, x is twice a square if sqrt(x/2) is an integer.

The Code

import java.util.*;

public class Problem46
{
  public static void main(String[] args)
  {
    List primeList = new ArrayList();
    primeList = generatePrimes(10000);

    for(double i = 33.0;; i += 2.0)
    {
      boolean flag = false;
      for(int index = 0; primeList.get(index) <= i; index++)
      {
        if(isTwiceASquare(i - primeList.get(index)))
        {
          flag = true;
          break;
        }
      }
      if(!flag)
      {
        System.out.println(i);
        break;
      }
    }
  }

  public static boolean isTwiceASquare(double n)
  {
    double square = Math.sqrt(n/2.0);
    return square == (int)square;
  }

  public static List generatePrimes(int max) 
  {
    boolean[] isComposite = new boolean[max + 1];
    for (int i = 2; i * i <= max; i++) 
    {
      if (!isComposite [i]) 
        for (int j = i; i * j <= max; j++) 
        {
          isComposite [i*j] = true;
        }
    }   
    ArrayList list = new ArrayList();

    for (int i = 2; i <= max; i++)  
    {
      if (!isComposite [i]) 
        list.add(new Integer(i));
    }
    return list;
  }
}