# Project Euler

### A Taste of Number Theory

#### Problem 46: Goldbach's Other Conjecture

9 = 7 + 2 x 12
15 = 7 + 2 x 22
21 = 3 + 2 x 32
25 = 7 + 2 x 32
27 = 19 + 2 x 22
33 = 31 + 2 x 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?

#### 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;
}
}
```