Two students have asked what algorithm does the Goldbach calculator of Plus magazine use. They have been breefly answered here. Yesterday I found a detailed answer here. The algorithm is great, but unfortunately it can't divide an even number into two equal prime numbers. This means it :
- can't divide 4 at all (even that 4=2+2);
- can't find all pairs in some cases. For instance, it can't show that 26=13+13 (which the calculator made by Plamen Antonov based on my algorithm here can easily do).
Today, while I was walking, I found an improved algorithm. What I mean is that it is better than the one used by Plus magazine and than my old one (the only fault of which is it can't divide 4 into 2+2):
Step 1. Use the sieve of Eratosthenes (or another algorithm) to calculate all the primes lesser than X (X is the even number chosen). Memorize the primes.
Step 2. Subtract from X every prime X1 (2<=X1<X), which has been produced in Step 1, in order to find X2, i.e. the other prime in the pair. If the other number is not prime (check the numbers produced in Step 1) disregard this particular pair (incl. all pairs consisting of even numbers without the one consisting of X1=X2=2, i.e. the one where X=4). Disregard the second pair in case of redundant pairs, i.e. as in the case of 5+3 and 3+5.
Step 3. Show all other pairs, i.e. pairs consisting of two primes.
My new algorithm in action: Number 12 is chosen.
Step 1. Find all primes lesser than 12:
2, 3, 5, 7, 11
Step 2. Calculate the differences between 12 and the primes (as calculated in Step 1):
a) 12-11=1 (Disregard the pair 11+1 as 1 is not prime)
b) 12-7=5 (Step 1 shows 5 is a prime, therefore memorize the pair)
c) 12-5=7 (Step 1 shows 7 is a prime, but the pair has to be desregarded as it is redundant)
d) 12-3=9 (Disregard the pair 3+9 as 9 is not prime)
e) 12-2=10 (Disregard the pair 2+10 as 2 and 10 are both even)
Step 3. Show the result, which is the pair 7+5 (b).
This is a copyrighted material. See Copyright Notice, Legal Disclaimer and Commenting Rules.
