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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: