A Goldbug number is an even number 2m for which there exists some subset of the prime non-divisors (PNDs) of 2m, 2 < p1 < p2 < p3 < ... < pk < m, such that (2m-p1)*(2m-p2)*(2m-p3)*...*(2m-pk) has only p1,p2,p3,...,pk as factors and one of the pi is between n/2 and n for even n and (n+1)/2 and n-1 for odd n. We do not need to consider the case where n is prime since then n itself is a Goldbach Pair.

Goldbug's Algorithm to find Goldbach Pairs for Non-Goldbug Numbers
------------------------------------------------------------------

1. By Lemma 1 we need only consider prime non-divisors (PNDs) of n. Given 2n>6 which is not a Goldbug Number there exists a prime by Bertrand’s Postulate that must be a PND of n or a Goldbach Pair. If 2n mod 4=0 then there exists n/2<p1<n. If 2n mod 4<>0 then there exists (n+1)/2<p1<n+1. If p1=n then done since 2n=2p1=p1+p1. Else p1<n.

2. Consider 2n-p1. If prime then done since p1 and 2n-p1 are a Goldbach Pair. Else factors of 2n-p1 must be unknown PNDs of n by Lemmas 2 and 3. Add the new PNDs to list of known PNDs.

3. Consider the factors of (2n-p1)(2n-p2)...(2n-pk) corresponding to the list of known PNDs. If one of the 2n-p is prime then done. Else must contain unknown PNDs since non-Goldbug. Add the new PNDs to list of known PNDs.

4. Repeat step 3. The process must halt eventually by finding a Goldbach Pair else contradiction by infinite descent since there are only a finite number of PNDs.

Lemma 1
-------

For a given n, every Goldbach pair consists of prime non-divisors of n.

Assume that one of the primes is a divisor of n.

2n=p1+p2

2n-p1=p2

p1(2n/p1-1)=p2

This implies that the other prime is also divisible by p1 which is a contradiction since p2 is prime. Therefore any prime pair that adds to 2n must not contain any divisors of n and we need only consider primes which are non-divisors of n.

Lemma 2
-------

Given p, a PND of n, 2n-p is not divisible by any divisor of n.

Assume d is a divisor of n.

2n-p mod d=0

->p mod d=0

This is a contradiction since p is prime.


Lemma 3
-------

Given p, a PND of n, 2n-p is not divisible by p.


2n-p mod p=0

->2n mod p=0