Goldbach’s Other Conjecture
June 7, 2016
Although there are other ways to do this, we solve the problem by generating the double-squares, then checking if the difference to the target number is prime. The sequence of double-squares is 0, 2, 8, 18, 32, …, so starting from 0 we walk through the sequence by adding 1*2, 3*2, 5*2, 7*2, …:
(define (goldbach n)
(let loop ((dsq 0) (k 1))
(if (< n dsq) (list)
(if (prime? (- n dsq)) (list (- n dsq) (sqrt (/ dsq 2)))
(loop (+ dsq k k) (+ k 2))))))
Then, to find all the numbers that refute Goldbach’s other conjecture, we write:
> (do ((n 3 (+ n 2))) (#f)
(let ((g (goldbach n)))
(when (null? g)
(display n) (newline))))
5777
5993
That program quickly produces the two results you see above, then it will run for a long time producing no further results, since it is now conjectured that those are the only two counter-examples to the conjecture. See A060003 for more information, and especially the link given there to the paper by Hodges.
You can run the program at http://ideone.com/88RZja.
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 :/ )