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.

Advertisements

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

%d bloggers like this: