The famous Goldbach Conjecture states that every even integer is a sum of two odd primes. Today, I will write a small program to split an even number into a sum of two odd primes. The conjecture states that this function I am about to define always returns a non-trivial pair of primes splitting the given even integer.
First a simple function to test whether a given number is prime:
(defun primep (n)
(if (oddp n)
(let ((m (floor (sqrt n))))
(do ((i 3 (+ i 2)))
((or (> i m) (zerop (mod n i)))
(and (> i m) n))))))
PRIMEPThe function will return nil if the number is composite,
otherwise returns the number n which is prime.
Next, I have a function which will return the first prime number coming after a given integer.
(defun next-prime (n)
(cond ((< n 2) 2)
((= n 2) 3)
(t (let ((m (if (evenp n) (1+ n) (+ n 2))))
(or (primep m)
(next-prime m))))))
NEXT-PRIMENow, a function which returns the first Goldbach pair
(defun goldbach-pair (n)
(if (evenp n)
(do ((i 3 (next-prime i)))
((primep (- n i)) (list i (- n i))))))
GOLDBACH-PAIRLet us test:
(goldbach-pair (expt 2 40))
(167 1099511627609)Finally, a function which returns all Goldbach pairs:
(defun all-goldbach-pairs (n)
(if (evenp n)
(let ((m (/ n 2))
(res nil))
(do ((i 3 (next-prime i)))
((> i m) (reverse res))
(if (primep (- n i))
(push (list i (- n i)) res))))))
ALL-GOLDBACH-PAIRSAnd its test
(all-goldbach-pairs (expt 2 10))
((3 1021) (5 1019) (11 1013) (41 983) (47 977) (53 971) (71 953) (83 941)
(113 911) (137 887) (167 857) (197 827) (227 797) (251 773) (263 761)
(281 743) (347 677) (383 641) (431 593) (461 563) (467 557) (503 521))