Goldbach's Other Conjecture

QUESTION : 

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×1²
15 = 7 + 2×2²
21 = 3 + 2×3²
25 = 7 + 2×3²
27 = 19 + 2×2²
33 = 31 + 2×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?

Reference : Project Euler

SOLUTION :

All we could come up with was a brute force logic which stores an ArrayList of prime numbers and caculates all the composite numbers based on this list (since every non-prime number is composite, ignoring all numbers less than or equal to 1). We thus have the LHS and the first part of the RHS. We subtract them and divide the result by 2. Finally, we check if the result is now a perfect square using Math.sqrt(double). Here is a well-commented Java code for the same.

PS: The required answer is 5777!

	import java.util.ArrayList;
	public class GoldbachsConjecture {
	public static ArrayList<Integer> primes = new ArrayList<Integer>();
	/*list containing all the prime numbers
	* list is used instead of an array since size is not known
	*/
	public static void main(String[] args) {
	primes.add(2);//first prime number is 2. Added for simplicity
	getPrimeNumbers();//populates the list
	goldbach();//finds the number disproving Goldbach's theory
	}
	public static void getPrimeNumbers(){
	boolean isPrime = true;
	for (int i = 3; i < 10001; i++) {
	/* For simplicity, we only add numbers upto 1000.
	* We observed that only 5777 and 5993 are the only numbers upto 1 bilion that
	disprove the said conjecture*/
	isPrime = true;
	for (int j = 2; j < i; j++) {
	if(i%j == 0){
	isPrime = false;
	break;
	}
	}
	if(isPrime){
	primes.add(i);
	}
	}
	}
	public static void goldbach(){
	int i = 9, temp, pos; //pos is the index traversing over the list primes
	boolean isConjectureCorrect = false;
	while(true){//this loop will go on indefinitely
	for (pos = 0; pos < primes.size() && primes.get(pos) < i; pos++) { //this is the calculating for-loop
	temp = i;
	temp -= primes.get(pos);
	temp /= 2;
	if((int)Math.sqrt(temp)*(int)Math.sqrt(temp) == temp){//check for perfect square
	isConjectureCorrect = true;
	break;
	}
	}//calculating for-loop ends
	if(!isConjectureCorrect){
	System.out.println(i);
	return;
	}
	isConjectureCorrect = false;
	//checking double-loop
	i += 2;
	for (int k = pos; k < primes.size(); k++) {
	if(primes.get(k) == i){
	i += 2;
	}
	}
	}//while-loop ends
	}
	}

view raw Goldbach's Other Conjecture hosted with ❤ by GitHub