A conjecture is a statement considered to be probably true but not yet proven. A vote proved its worth becomes a theorem. Goldbach's Conjecture is one of the oldest problems to be resolved, it dates back to 1742, was enunciated by Euler to Goldbach and reformulated as follows:

Every natural number equal greater than 2 can 'To be an written as the sum of two
prime numbers.

For example:
4 = 2 + 2
6 = 3 + 3
8 = 3 + 5
10 = 3 + 7 = 5 + 5
12 = 5 + 7
14 = 3 + 11 = 7 + 7
16 = 3 + 13 = 5 + 11

We try to demonstrate its inaccuracy

On a conjecture we can make two kinds of demonstrations, we can prove its correctness or its inaccuracy. Obviously the one excludes the other. We will attempt to prove that the conjecture is false, to do this by finding a counterexample to the statement that prove to be false tele. So in our case, just find a single even number which is not the sum of two primes. To find this number we write a program.

Some considerations

All the prime numbers are odd with the exception of 2. This is true for the definition of odd number. The prime number 2 added to a first from any other number as a result of an odd number. The only case in which 2 are added to another prime number as a result has an even number is 2 + 2. From this we deduce that the 4 is the only even number which can be written as the sum of the prime number 2 with a different prime number. In the program without considering the primes 2 and all even numbers greater than four.

Decompose the problem into sub problems

His actions in a program can schematizarsi succesioni of distinct phases:

1. Find all prime numbers from 3 to n
2. Take all pairs of prime numbers (p1, p2) such that their sum does not exceed n (ie, p1 + p2 <= n) and if it is considered (p1, p2) then it will be discarded (p2, p1).
3. Mark from 6 equal to n if they are the result of p1 + p2 for each pair (p1, p2) found previously.
4. Print all the even numbers are not marked as a sum of primes.

Sieve of Eratosthenes

Torvare For all prime numbers from 3 to n there is a very ancient method known as the Sieve of Eratosthenes. It is to write all the numbers from 2 to n and then delete all the multiples of 2 (excluded), all multiples of 3 (excluded), all multiples of 5 (excluded) and so on. The numbers "survivors" are all and only the prime numbers between 2 and n.

So we use a vector v flag, the idea and 'simple, we mark all the numbers in multiples of 2, 3, 5, etc. .. so the remaining are prime. To save memory I have from the carrier 3 and examined only by the odd numbers, eg:

index vector (s): 0 1 2 3 4 5 6
information (j): 3 5 7 9 11 13 15
v [i]: TTTFTTF

to go from i to j using the function j = 2 * i + 3
conversely i = (j - 3) / 2
Note: j - 3 always a number divisible by two as ij are all odd.

  long int n ) { riempi_v void (long int n) {
   k ; int i, k;
   i = 0 ; i < Size ( n ) ; i ++ ) { for (i = 0; i <Size (n) i + +) {
     v [ i ] == TRUE ) if (v [i] == TRUE)
       k = 3 ; ( 2 * i + 3 ) * k < n + 2 ; k = k + 2 ) for (k = 3, (2 * i + 3) * k <n + 2, k = k + 2)
         * i * k + 3 * k - 3 ) / 2 ] = FALSE ; v [(2 * i * k * k + 3 - 3) / 2] = FALSE;
   }
 } 

Backtracking algorithm

Once the vector v I know what are the prime numbers up to n.
Now I must find all pairs (p1, p2). To do this using an algorithm that takes advantage of the method of the backtracking. The algorithm "prunes" the tree recursion so they do not consider all the pairs of numbers that do not need. So to be as optimized as possible, we realize that the optimization of this program is essential if we are to achieve good results.

  / * Find the sum and all pairs of prime numbers found above * /
 long int n , int i , int p1 , int p2 ) { backtraking void (long int n, int i, int p1, int p2) {
   int x;
   i == 2 ) { if (i == 2) {
     p2 ) / 2 ] = FALSE ; of [(p1 + p2) / 2] = FALSE;
     / * Printf ("(% d,% d) \ n", p1, p2) * /
   }
   else {
     i == 0 ) if (i == 0)
       x = 3 ; x != - 1 ; x = primo_successivo ( n , x ) ) { for (x = 3, x! = - 1, x = primo_successivo (n, x)) {
         i + 1 , x , p2 ) ; backtraking (n, i + 1, x, p2);
       }
     else
       / ** 
         * Initialize x p1 is to verify the conjecture Goldback. 
         * Place primo_successivo x = (n, p1) to find all of 
         * Data from p1 + p2 p1! = P2 
         * /
       x = p1 ; x != - 1 ; x = primo_successivo ( n , x ) ) { for (x = p1 x! = - 1, x = primo_successivo (n, x)) {
         p1 + x <= n ) if (p1 + x <= n)
           i + 1 , p1 , x ) ; backtraking (n, i + 1, p 1, x);
         ; else break;
       }
   }
 } 

Found the pair (p1, p2) is the sum of the vector and updates. The carrier has a size equal to n / 2, each element corresponds to an even number.

We developed the points 1, 2 and 3 of our problem, we just have to scroll through the vector of the index and print only in the presence of an even number that is not the sum of two primes.

  i = 0 ; i < n / 2 ; i ++ ) for (i = 0; i <n / 2, i + +)
     pari [ i ] == TRUE ) if (equal to [i] == TRUE)
       "%d:i = %d \n " , pari [ i ] , 2 * i ) ; printf ("% d: i =% d \ n", that [i], 2 * i); 

Results

You will find effettaundo of tests that also increases as n increases the execution time. With a computer with Intel processor 5336.88 bogomips I spent 5 days with n equal to 100,000,000.

The Goldbach conjecture is supposed to be true by the fact that the probability for an even number to be the sum of two first increases with the number. There is a distributed computing project that has so far verified the conjecture up to 2 * 10 ¹⁷ (at the time of this writing.)

Another conjecture

I do not want to compare me to Euler or Goldbach but probably also find it interesting that other passta I guess my mind while writing the program in question. It is a refinement of the statement of Goldbach.

All natural numbers greater than 6 and equal can be written as the sum of two primes p1 and p2 such that p1 p2 is different from

You have the proof. I can tell you with certainty that up to 10 ⁸ is true.