Verifying Goldbach's Conjecture

Travail de Recherche , 2012 , 9 Pages

Informatique - Informatique appliquée

Paper discusses Goldbach's Conjecture that all even integers can be represented as the sum of two prime numbers and presents an algorithm to verify the conjecture which is only limited by the size of the primes that can be generated.

Introduction

The Goldbach conjecture is a conjecture made to Euler by Goldbach regarding the nature of even integers. It remains an unproven concept in mathematics. The conjecture states that for any even integer, there exists two prime numbers that sum to it [1]. For example, integer 8 has 3 and 5 which can sum to it. For the purposes of this paper, the conjecture is taken to mean that for any even integer greater than or equal to 8, there exists at least one pair of primes, p and q, which can sum to it. Note that there may be more than one pair that sum to the same even integer. This paper develops an algorithm which can be used to verify the conjecture and the algorithm is limited by the size of the largest prime number that can be generated. It is in fact order of the sieve used to generate the primes needed in its computation. For additional work on verification of Goldbach's conjecture see references [4] and [5].

Verification Algorithm

Consider the integer n and a set Sn consisting of all primes less than or equal to n. One can generate all such primes using a sieve such as the Sieve of Eratosthenes in O(nloglogn) time [1].

From this set of primes, we do not consider integers 0, 1, or 2 from the results and for the purpose of this article such numbers are not part of the prime number set Sn . For example, given n=12, we would have Sn = {3, 5, 7, 11}.

Given Sn one can generate the combination of all pairs of primes possible. That is, one can compute n choose k where k = 2 for all primes in the set. Such an algorithm would be order O(n!/(k!(n-k)!)). With Sn stored in memory as variable v_primes of type std::vector<int>, and m_primes being a variable of type std::map<int, std::pair<int,int> >, the algorithm would be:

Abbildung in dieser Leseprobe nicht enthalten

The output would be a map of sums of prime pairs computed as v_primes[i] + v_primes[j] which are associated with the pair of primes v_primes[i], v_primes[j]. For the purpose of this article, let integer e = v_primes[i] + v_primes[j], p = v_primes[i], and q = v_primes[j]. In the example of n = 12, the pairs generated would be: {3,5} {3,7} {3,11}, {5,7} {5,11}, {7,11}. The values for e would be 8, 10, 14, 12, 16, 18. Let Sprime be the set of all prime pairs generated by Algorithm 1. This set is the set of all semi-primes that have both factors in set Sn.

Lemma 1. Given an even integer e = p + q where p and q are prime, then e can factor n = p * q. Proof: Consider the equation: x2 - (p + q)x + p*q = 0. Let a=1, b = p + q, and c = p * q. Then by Quadratic formula[3] we have:

a x2 - bx + c = 0

x = (-b ± √(b2 – 4 ac)) / 2

x = p+q ± √((p+q)2 – 4 *p*q)) / 2

Where the solutions are x = p and x = q.

Observation 1. The set of all semi-primes Sprime must generate all even numbers e where e ≥ 8 and e ≤ n by summation of primes p + q where {p,q} ε Sprime of each semi-prime if Goldbach's Conjecture is true. Arguments: If this were not true, then there must exist an even integer e' where e' ≥ 8 and e' ≤ n and that there is no prime summation from {p,q} ε Sprime. Such an e' would mean that either p or q or both p and q are not in the set Sn or alternatively, that e' does not have any two primes that sum to it. In the above, we have 8 = {3+5}, 10 = {3+7}, 12 = {5+7}. If e' exists in that set, then no semi-prime factors {p,q} sum to it. Moreover, such an e' can not factor any semi-prime in the set by Lemma 1 since it would not be a sum of a prime number pair in the set. Therefore, it is possible that there exists a semi-prime s={p,q} which is not in the set Sprime and that e' sums to it instead of any other semi-prime in the set. Note that a given semi-prime factors {p,q} must sum to an even number as by definition, both factors are prime and prime numbers are by definition odd. Thus adding two primes produces an even number. However, p and q must be in Sn by our requirement that e' be between 8 and n inclusive and our construction of Sprime as a combination of all pairs of n choose 2 from the set Sn implies that such an semi-prime s={p,q} can not exist as it is a contradiction.

To verify that all such values of integer e where e ≥ 8 and e ≤ n are generated, consider:

Abbildung in dieser Leseprobe nicht enthalten

Algorithm 2 iterates from 8 to n inclusive and checks the map m_primes for a value. The returned value is the semi-prime that sums to the desired even integer. The algorithm returned successfully for all cases in which it was tried and was able to verify Goldbach's Conjecture up to 1 million cases. Additionally, a simple factoring algorithm can be implemented where instead of storing e = p + q, one can store n = p + q, and to factor, one would need to query the map with a value for n retrieving its factorization.

Algorithm 1. above has a major performance issue in that it requires the computation of all combinations prior to termination, and then, the verification Algorithm 2 executes. The verification requires O(n) operations and is much more efficient than computing all combinations. Thus, combining the two algorithms to produce a single combination generating and verification algorithm would yield an O(n) algorithm. Additionally, the space complexity of the algorithm need not be O(n) or O(n!/(k!(n-k)!)) as the data stored in the m_primes map can be removed when it is no longer needed as well as not added once the algorithm has verified the values less than the current value. Consider:

[...]

• Université: Northcentral University
• Auteur: Dr. Roger Doss (Auteur)
• Année de publication: 2012
• Pages: 9
• N° de catalogue: V206611
• ISBN (ebook): 9783656340591
• Langue: anglais
• mots-clé: verifying, goldbach, conjecture