Goldbach’s Other Conjecture
June 7, 2016
Christian Goldbach (1690-1764) was a Prussian mathematician and contemporary of Euler. One of the most famous unproven conjectures in number theory is known as Goldbach’s Conjecture, which states that every even number greater than two is the sum of two prime numbers; for example, 28 = 5 + 23. We studied Goldbach’s Conjecture in a previous exercise.
Although it is not as well known, Goldbach made another conjecture as follows: Every odd number greater than two is the sum of a prime number and twice a square; for instance, 27 = 19 + 2 * (2 ** 2). (The conjecture is sometimes stated as every odd composite number is the sum of a prime number and twice a square, since it is trivially true with 0 as the square root for all prime numbers; alternately, it is sometimes limited so that the number being squared must be positive, in which case there are some odd primes that can be so expressed.) Sadly, it is easy to find a counter-example that disproves Goldbach’s other conjecture.
Your task is to write a program that finds the smallest number that disproves Goldbach’s other conjecture. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
function Goldbach(x::Int64) # x is odd
P = primes(x)
for p in P
z = sqrt(x – p)
if z == round(z)
return true
end
end
return false
end
function main(n::Int64 = 1000)
for i = 1:n
x = 2 * round(Int64, 10000*rand()) + 1
if !Goldbach(x)
return x
end
end
return -1
end
It would be interesting to see how this is implemented in other languages.
A generator in Python.
def goldbach(): for cand in count(3, 2): c, diff = cand, 2 while not is_prime(c): c -= diff diff += 4 if c <= 1: yield cand breakJune 7th, 2016.c:
#include "seal_bool.h" /* <http://GitHub.com/sealfin/C-and-C-Plus-Plus/blob/master/seal_bool.h> */ #include "printDateAndTime.h" /* <http://Gist.GitHub.com/sealfin/6d35f3a3958bd6797a0f> */ #include <stdio.h> #include <stdlib.h> bool *g_isPrime = NULL; long g_numberOfPrimes, *g_primes = NULL; void p_CleanUp( void ) { if( g_isPrime != NULL ) free( g_isPrime ); if( g_primes != NULL ) free( g_primes ); } bool f_IsPrime( const long p ) { if( p % 2 == 0 ) return p == 2; else return g_isPrime[ p ]; } void main( void ) { const long k_N_STEP = 10000; long N = 0, a = 3; p_PrintDateAndTime(); printf( "\n" ); atexit( p_CleanUp ); while( true ) { long i = 0, k; { const long old_N = N; N += k_N_STEP; if( N < old_N ) { fprintf( stderr, "Sorry, an error occurred: `N` overflowed.\n" ); exit( EXIT_FAILURE ); } } /* Firstly, let's determine the prime numbers in the range [ 0, N ) so that later we can avoid trying to determine if a prime number conforms to Goldbach's Other Conjecture. */ if( g_isPrime != NULL ) free( g_isPrime ); g_isPrime = ( bool* )malloc( sizeof( bool ) * N ); for( ; i < N; i ++ ) g_isPrime[ i ] = true; if( N >= 1 ) g_isPrime[ 0 ] = false; if( N >= 2 ) g_isPrime[ 1 ] = false; g_numberOfPrimes = 0; if( N >= 3 ) g_numberOfPrimes ++; for( i = 3; i < N; i += 2 ) if( g_isPrime[ i ] ) { g_numberOfPrimes ++; for( k = i + i; k < N; k += i ) g_isPrime[ k ] = false; } /* Secondly, let's create a list of the prime numbers in the range [ 0, N ) so that later we can subtract prime numbers from a number as part of testing if that latter number conforms to Goldbach's Other Conjecture. */ if( g_primes != NULL ) free( g_primes ); g_primes = ( long* )malloc( sizeof( long ) * g_numberOfPrimes ); k = 0; if( N >= 3 ) g_primes[ k ++ ] = 2; for( i = 3; k < g_numberOfPrimes; i += 2 ) if( f_IsPrime( i )) g_primes[ k ++ ] = i; /* Now, for every odd composite number a in the range [ 3, N ), we test if it conforms to Goldbach's Other Conjecture by, for (potentially) every prime number less than a, subtracting that prime number from a and then testing if there is a number b where 2 * b * b is equal to a. */ do { if( !f_IsPrime( a )) { bool example_found = false; i = 0; while( g_primes[ i ] < a ) { const long a_copy = a - g_primes[ i ]; long b = 1; while( 2 * b * b < a_copy ) b ++; if( 2 * b * b == a_copy ) { example_found = true; break; } i ++; } if( !example_found ) { printf( "The odd composite number greater than two %ld cannot be formed from the sum of a prime number and twice a square, thus disproving Goldbach's Other Conjecture.\n", a ); printf( "\n" ); p_PrintDateAndTime(); exit( EXIT_SUCCESS ); } } { const long old_a = a; a += 2; if( a < old_a ) { fprintf( stderr, "Sorry, an error occurred: `a` overflowed.\n" ); exit( EXIT_FAILURE ); } } } while( a < N ); } }Output:
On an Apple Power Mac G4 (AGP Graphics) (450MHz processor, 1GB memory) to run the solution took:
approximately twenty-two seconds on Mac OS 9.2.2 (International English) (the solution interpreted using Leonardo IDE 3.4.1);
approximately one second on Mac OS X 10.4.11 (the solution compiled using Xcode 2.2.1).
(I’m just trying to solve the problems posed by this ‘site whilst I try to get a job; I’m well aware that my solutions are far from the best – but, in my defence, I don’t have any traditional qualifications in computer science :/ )