Project Euler: Problem 46 – Goldbach’s other conjecture

Problem 46:

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?

Idea:

First, I had to look up what “odd composite” meant (in short: odd, non-prime number). From there, I made a list of the first 10000 prime numbers and I started with 3 and looped through every odd number to see if it was prime. If it wasn’t, I looped through the list of prime numbers and applied the formula above until I found and odd composite that couldn’t be written as the sum of a prime and twice a square.

int answer = -1;

int[] primes = new int[10000];
BigInteger base = BigInteger.ONE;
for(int i = 0; i < primes.length; i++) {
   base = base.nextProbablePrime();
   primes[i] = base.intValue();
}

boolean found = false;
int number = 3;
while(!found) {
   //test odd composite for prime-ness
   if(BigInteger.valueOf((long)number).isProbablePrime(10)) {
      number += 2;
      continue;
   }
   boolean cantBeWritten = true;
   for(int i = 0; primes[i] < number && cantBeWritten; i++) {
      int tmp = number-primes[i];
      tmp = tmp / 2;
      int result = (int)Math.sqrt(tmp);
      if(result*result*2 + primes[i] == number) {
         cantBeWritten = false;
      }
   }
   if(cantBeWritten) {
      answer = number;
      found = true;
      break;
   }
   number += 2;
}
Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *