Home
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. For example,
It turns out the conjecture was false. What is the smallest odd composite that cannot be written as the sum of a prime and twice a square?
Related Tags:
Before we break this down into components, let's try rearranging the conjecture.
n = p + 2 x s2
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.
To obtain a list of values less than some n, we can apply the Sieve of Eratosthenes.
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;
}
}
}
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;
}
}
This problem is the 46th problem on Project Euler.
Came up with a better solution or have a question? Comment below!
Next Challenge: Finding all prime factors