Project Euler Problem 46: Goldbach's other conjecture

Related Tags:

Writing out the math

Before we break this down into components, let's try rearranging the conjecture.

n = p + 2 x s²

Where n is the number, p is our prime number, and s is the value we need to square.

We then rearrange this equation to obtain the following:

s = sqrt((n-p)/2)

Since s must be an integer, the right hand side of the equation must equate to a whole number. If not, the conjecture does not hold for those values of n and p.

Furthermore, we note how n < p since we can't take the square root of a negative number.

Algorithm Pseudocode

1. Given a value n, obtain a list of all primes less than n.
2. For each prime p in our list, we take sqrt( (n - p) / 2 ).
3. If the result is an integer, (no decimal places) then the conjecture holds, and we can move on to the next odd n.
4. If not, move onto the next prime value, p.
5. If we have exhausted our prime values list, then we found the value of which the conjecture does not hold.

Obtaining a list of all primes < our number

To obtain a list of values less than some n, we can apply the Sieve of Eratosthenes.

Implementation in Java

Here's the implementation. The findPrimes() method returns an ArrayList of primes less than a given input.

This method returns the value 5777.

static int disproveGoldbach() {

	// Start at 1
	int currentNum = 1;

	// Our list of prime arrays
	ArrayList<Integer> listOfPrimes;

	// Boolean to exit loop when all done
	boolean done = false;

	// Keep running until we find a value that doesn't work
	while (true) {

		// Get list of prime numbers for the current number
		listOfPrimes = findPrimes(currentNum);

		// Try out all options in our list of prime numbers
		for (int j = 0; j < listOfPrimes.size(); j++) {

			int currentPrime = listOfPrimes.get(j);

			double eval = Math.sqrt((currentNum - currentPrime) / 2) % 1;

			// If there exists an int we can square and double
			if (eval == 0.0) {
				break;
			}

			// If we've exhausted our list, and no solutions are found, return!
			if (j == listOfPrimes.size() - 1) {
				return currentNum;
			}
		}

		// only odd numbers
		currentNum += 2;

	}
}
}

Full runnable code

Here's the full, runnable code in case you want to test it out yourself.

import java.lang.Math;
import java.util.HashMap;
import java.util.ArrayList;

public class Goldbach {

	public static void main(String[] args) {

		System.out.println(disproveGoldbach());

	}

	static int disproveGoldbach() {

		// Start at 1
		int currentNum = 1;

		// Our list of prime arrays
		ArrayList<Integer> listOfPrimes;

		// Boolean to exit loop when all done
		boolean done = false;

		// Keep running until we find a value that doesn't work
		while (true) {

			// Get list of prime numbers for the current number
			listOfPrimes = findPrimes(currentNum);

			// Try out all options in our list of prime numbers
			for (int j = 0; j < listOfPrimes.size(); j++) {

				int currentPrime = listOfPrimes.get(j);

				double eval = Math.sqrt((currentNum - currentPrime) / 2) % 1;

				// If there exists an int we can square and double
				if (eval == 0.0) {
					break;
				}

				// If we've exhausted our list, and no solutions are found, return!
				if (j == listOfPrimes.size() - 1) {
					return currentNum;
				}
			}

			// only odd numbers
			currentNum += 2;

		}
	}

	static ArrayList<Integer> findPrimes(int n) {

		// A key prime Integer will have a Boolean value of true.
		HashMap<Integer, Boolean> primeTable = new HashMap<>();

		// Load our table with values up to and including n.
		for (int i = 1; i <= n; i++) {
			primeTable.put(i, true);
		}

		// 1 is by definition not prime.
		primeTable.put(1, false);

		// For every value up to the sqrt(n).
		for (int i = 2; i * i < n; i++) {
			// If particular value is still set as prime
			// (otherwise those values will have already been covered.
			if (primeTable.get(i)) {

				// Set each multiple as not a prime 
				for (int p = i+i; p <= n; p += i) {
					primeTable.put(p, false);
				}
			}
		}

		// Now store all primes into a list and return
		ArrayList<Integer> primes = new ArrayList<>();	
		
		for (int i = 1; i <= primeTable.size(); i++) {
			if (primeTable.get(i))
				primes.add(i);
		}

		return primes;

	}
}

Sources

This problem is the 46th problem on Project Euler.

Came up with a better solution or have a question? Comment below!