Here’s the algorithm done by hand for 50, from my paper.
1) For even n treat as Zn, and identify its low-half-residues (lhr) < n/2.
The residue values r are odd integers coprime to n, e.g. gcd(r, n) = 1.
The 1st canonical residue is 1, but 1 is not prime, so it can't be part of
a prime pair, so test the odds numbers from 3 < n/2 to identify the lhr.
2) Store in lhr_mults the powers of ri in lrh < n-2; these are composite residues.
We test up to n-2 because n-1 is the mcp for 1, which can't be part of a pcp.
Once the square of an ri (i.e. ri^2) > n-2, exit process, as all other rj are > n-2.
We test against the nth roots of n-2 to prevent arithmetic overflow possibilities.
3) Store in lhr_mults the cross-products ri*rj < n-2.
Starting with smallest ri lhr, test cross-products with all larger lhr.
If ri > sqrt(n-2), exit process, as ri^2, and all other ri lhr cross-products, are > n-2.
If for next larger residue rj, ri*rj > n-2, exit process, as no others are < n-2.
Otherwise save in lhr_mults cross-product ri*rj < n-2, repeat for next larger rj lhr.
lhr_mults now has all the non-prime composite residue values < n-2.
4) Remove from the lhr the non-pcp lhr_mults values. The pcp prime pairs remain.
a) For lhr_mults values r > n/2, convert lhr to their mcp values n-r.
b) All now are non-pcp values < n/2; remove their values from the lhr list.
The lhr list now contains all prime residues whose mcp make a pcp prime pair.
For the remaining primes pn, the pcp for n are the prime pairs [pn, n - pn].
Let’s now do a non-trivial example that performs all the algorithmic parts.
Example: Find the pcp prime pairs for n = 50.
1) Identify the lhr values < n/2.
Write out list of odd numbers from 3 to < 25 = 50/2
[3 5 7 9 11 13 15 17 19 21 23]
The lhr are values r coprime to n; i.e gcd(r,50) = 1.
[3 7 9 11 13 17 19 21 23]
Thus: lhr = [3, 7, 9, 11, 13, 17, 19, 21, 23]
2) Store in lhr_mults the powers of the lhr < 48 = 50-2.
a) for 3: lhr_mults = []
3 * 3: lhr_mults = [9], as 9 < 48
3 * 9: lhr_mults = [9, 27], as 27 < 48
3 * 27: stop powers for 3, as 81 > 48
b) for 7: exit powers process; as 7*7 = 49 > 48; no other lhr power can be < 48.
3) Store in lhr_mults the lhr cross-products < 48.
a) for 3: lhr_mults = [9, 27]
3 * 7: lhr_mults = [9, 27, 21], as 21 < 48
3 * 9: lhr_mults = [9, 27, 21, 27], as 27 < 48
3 * 11: lhr_mults = [9, 27, 21, 27, 33], as 33 < 48
3 * 13: lhr_mults = [9, 27, 21, 27, 33, 39], as 39 < 48
3 * 17: stop cross-products process for 3, as 3 * 17 = 51 > 48
b) for 7: lhr_mults = [9, 27, 21, 27, 33, 39]
7 * 9: exit total cross-product process, as 7 * 9 = 63 > 48;
4) Remove from the lhr the lhr_mults values
lhr = [3, 7, 9, 11, 13, 17, 19, 21, 23]
lhr_mults = [9, 27, 21, 27, 33, 39]
a) Convert lhr_mults values > 50/2 = 25 to their modular complement value 50-r
lhr_mults = [9, 23, 21, 23, 17, 11]
b) Remove from lhr values in lhr_mults (software equivalent is: lhr -= lhr_mults)
lhr = [3, 7, 9, 11, 13, 17, 19, 21, 23]
lhr_mults = [9, 23, 21, 23, 17, 11]
b1) For lhr_mults val 9; remove from lhr:
lhr_mults = [9, 23, 21, 23, 17, 11]
^
lhr = [3, 7, 11, 13, 17, 19, 21, 23]
b2) For lhr_mults val 23; remove from lhr:
lhr_mults = [9, 23, 21, 23, 17, 11]
^
lhr = [3, 7, 11, 13, 17, 19, 21]
b3) For lhr_mults val 21; remove from lhr:
lhr_mults = [9, 23, 21, 23, 17, 11]
^
lhr = [3, 7, 11, 13, 19]
b4) For lhr_mults val 17; remove from lhr:
lhr_mults = [9, 23, 21, 23, 17, 11]
^
lhr = [3, 7, 11, 13, 19]
b5) For lhr_mults val 11; remove from lhr:
lhr_mults = [9, 23, 21, 23, 17, 11]
^
lhr = [3, 7, 13, 19]
lhr list of only primes now exists; as original lhr composite residues have been removed.
Thus lhr = [3, 7, 13, 19] now contains 4 prime pcp residues for n = 50.
Their 4 pcp prime pairs values for 50 are:
pcp for 3: [3, 50 - 3] = [3, 47]
pcp for 7: [7, 50 - 7] = [7, 43]
pcp for 13: [13, 50 - 13] = [13, 37]
pcp for 19: [19, 50 - 19] = [19, 31]
Every even integer n > 6 has at least one pcp prime pair.
This is a property of modular groups Zn over even integers n.
I urge people to do the algorithm by hand for 38, 40, and 46, Why?
38 is the largest even n with only one pcp prime pair.
(It’s of type n = 2p, so it has a trivial prime pair of 38 = 19 + 19)
Thus it has (p-1) = (19-1) = 18 residues.
Do the algorithm and see what those values are, and how they interact.
Now do 40. It has a different prime factor profile.
See how those residues interact.
Then do 46, because it’s the next larger type n = 2p; 46 = 2*23 = 23 + 23.
It has (23-1) = 22 residues.
Because they have more|larger values, there’s more spacing between them.
Doing the algorithm by hand creates a visceral cognitive experience of how the math works.
When you see the math done in steps, you can begin to realize how the outcomes must be.
So the (modern) Golbach’s Conjecture states:
Every even number > 2 can be written as the sum of 2 primes (not necessarily unique).
The PGT Goldbach Conjecture equivalent states:
Every even integer n > 6, has for its modular group Zn at least one prime complement pair (pcp).
FYI 1.
It seems a PR has been committed to fix the out-of-bounds indexing issue.
FYI 2.
I ran more n values on my new TUXEDO laptop, and made it to n = 1_5000_000_000 (1.5 billion).
Here’s the list with all the values in one place.
N # PCP First Prime Pair Last Prime Pair
100,000,000 291,400 [11, 99999989] [49999757, 50000243]
200,000,000 538,290 [37, 199999963] [99999787, 100000213]
300,000,000 1,547,388 [23, 299999977] [149999909, 150000091]
400,000,000 999,700 [41, 399999959] [199999949, 200000051]
500,000,000 1,219,610 [7, 499999993] [249999877, 250000123]
600,000,000 2,874,881 [29, 599999971] [299999549, 300000451]
700,000,000 1,979,689 [47, 699999953] [349999691, 350000309]
800,000,000 1,859,646 [13, 799999987] [399999829, 400000171]
900,000,000 4,132,595 [37, 899999963] [449999993, 450000007]
1,000,000,000 2,274,205 [71, 999999929] [499999931, 500000069]
1,100,000,000 2,748,595 [3, 1099999997] [549999811, 550000189]
1,200,000,000 5,352,052 [7, 1199999993] [599999783, 600000217]
1,300,000,000 3,137,228 [17, 1299999983] [649999793, 650000207]
1,400,000,000 3,688,114 [13, 1399999987] [699999841, 700000159]
1,500,000,000 6,543,613 [43, 1499999957] [749999927, 750000073]
Again, the number of pcp for n is a function of the number of residues it has.
The number of residues it has is a function of its prime factorization profile.
There should be no doubt in anyone’s mind, that as the numbers get larger and larger,
it’s not possible for some number n to have no (0|zero) pcp prime pairs.
I’ll take bets from anyone willing to claim they can prove otherwise.
The really more interesting (and fun) question is:
Can one determine the expected|minimum number of pcp for an n just from its prime factors?