Programming Praxis

3 Responses to “Goldbach’s Other Conjecture”

1. Zack said

   June 7, 2016 at 4:09 PM

   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

   June 8, 2016 at 8:48 AM

   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 19, 2017 at 1:38 PM

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