## 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.

Pages: 1 2

### 3 Responses to “Goldbach’s Other Conjecture”

1. Zack said

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.

2. Paul said

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
break
```
3. sealfin said

June 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:

`The odd composite number greater than two 5777 cannot be formed from the sum of a prime number and twice a square, thus disproving Goldbach's Other Conjecture.`

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 :/ )