Improve Prime Pairs Code

[jzakiya]

Hi.

First, I'm not a Python programmer so please escuse my ignorance.

I'm looking for help to improve this code.
It generate prime pairs that sum to even integers.

If you want to know the hows|whys of its design read this paper I just released.

Proof of Goldbach's Conjecture and Bertrand's Postulate Using Prime Generator Theory (GPT)
https://www.academia.edu/127404211/Proof...heory_PGT_

Here's the Ruby code from the paper.

# Enable YJIT if using CRuby >= 3.3"
RubyVM::YJIT.enable if RUBY_ENGINE == "ruby" and RUBY_VERSION.to_f >= 3.3

def prime_pairs_lohi(n)
  return puts "Input not even n > 2" unless n.even? && n > 2
  return (pp [n, 1]; pp [n/2, n/2]; pp [n/2, n/2]) if n <= 6

  # generate the low-half-residues (lhr) r < n/2
  lhr = 3.step(n/2, 2).select { |r| r if r.gcd(n) == 1 }
  ndiv2, rhi = n/2, n-2            # lhr:hhr midpoint, max residue limit
  lhr_mults = []                   # for lhr values not part of a pcp

  # store all the powers of the lhr members < n-2
  lhr.each do |r|                  # step thru the lhr members
    r_pwr = r                      # set to first power of r
    break if r > rhi / r_pwr       # exit if r^2 > n-2, as all others are too
    while    r < rhi / r_pwr       # while r^e < n-2
      lhr_mults << (r_pwr *= r)    # store its current power of r
    end
  end

  # store all the cross-products of the lhr members < n-2
  lhr_dup = lhr.dup                # make copy of the lhr members list
  while (r = lhr_dup.shift) && !lhr_dup.empty? # do mults of 1st list r w/others
    ri_max = rhi / r               # ri can't multiply r with values > this
    break if lhr_dup[0] > ri_max   # exit if product of consecutive r’s > n-2
    lhr_dup.each do |ri|           # for each residue in reduced list
      break if ri > ri_max         # exit for r if cross-product with ri > n-2
      lhr_mults << r * ri          # store value if < n-2
    end                            # check cross-products of next lhr member
  end

  # convert lhr_mults vals > n/2 to their lhr complements n-r,
  # store them, those < n/2, in lhr_del; it now holds non-pcp lhr vals
  lhr_del = lhr_mults.map { |r_del| (r_del > ndiv2 ? n - r_del : r_del) }

  pp [n, (lhr -= lhr_del).size]    # show n and pcp prime pairs count
  pp [lhr.first, n-lhr.first]      # show first pcp prime pair of n
  pp [lhr.last,  n-lhr.last]       # show last  pcp prime pair of n
end

def tm; t = Time.now; yield; Time.now - t end  # to time runtime execution

n = ARGV[0].to_i                   # get n value from terminal
puts tm { prime_pairs_lohi(n) }    # show execution runtime as last output

Here's my Python3 translation.

import time
from math import gcd

def prime_pairs_lohi(n):
    if n&1 == 1 or n < 4: return print("Input not even n > 2")
    if n <= 6: print([n, 1]); print([n/2, n/2]); print([n/2, n/2]); return

    # generate the low-half-residues (lhr) r < n/2
    lhr = []                              # lhr (low half residues) of n
    ndiv2, rhi = n//2, n-2                # lhr:hhr midpoint, max residue limit
    for r in range(3, ndiv2, 2):
        if gcd(r, n) == 1: lhr.append(r)

    # store all the powers of the lhr members < n-2
    lhr_mults = []                        # lhr multiples, not part of a pcp
    for r in lhr:                         # step thru the lhr members
        r_pwr = r                         # set to first power of r
        if r > rhi // r_pwr: break        # exit if r^2 > n-2, as all others are too
        while r < rhi // r_pwr:           # while r^e < n-2
            r_pwr *= r                    # increase power of r
            lhr_mults.append(r_pwr)       # store its current power of r

    # store all the cross-products of the lhr members < n-2
    lhr_dup = lhr.copy()                  # make copy of the lhr members list
    while True:                           # do mults of 1st list r w/others
        r = lhr_dup.pop(0)                # get first lhr_dup element, reduce it by 1
        if len(lhr_dup) == 0: break       # exit if lhr_dup empty
        ri_max = rhi // r                 # ri can't multiply r with values > this
        if lhr_dup[0] > ri_max: break     # exit if product of consecutive r’s > n-2
        for ri in lhr_dup:                # for each residue in reduced list
            if ri > ri_max: break         # exit for r if cross-product with ri > n-2
            lhr_mults.append(r * ri)      # store value if < n-2

    # convert lhr_mults vals > n/2 to their lhr complements n-r,
    # store them, those < n/2, in lhr_del; it now holds non-pcp lhr vals
    for r in lhr_mults:
        i =  r if r < ndiv2 else n-r
        if i in lhr: lhr.remove(i)

    print([n, len(lhr)])                 # show n and pcp prime pairs count
    print([lhr[0], n-lhr[0]])            # show first pcp prime pair of n
    print([lhr[-1],  n-lhr[-1]])         # show last  pcp prime pair of n

n = int(input())                         # get n value from terminal
t1 = time.time()
prime_pairs_lohi(n)
print(time.time() - t1)

It computes correct answers but:
1) It's way slower than the Ruby version.
2) It doesn't take input directly from the command line following the method
3) It doesn't take input numbers using underscores: 123_456_780

Here a timing difference example.

➜  ~ ruby prime_pairs_lohi.rb 1_000_000
[1000000, 5402]
[17, 999983]
[499943, 500057]
0.13848254

➜  ~ python3 prime_pairs_lohi.py
1000000
[1000000, 5402]
[17, 999983]
[499943, 500057]
222.1770532131195

So I'm asking help to improve performance and make entering numbers the same as Ruby.

[alexjordan]

The Python translation is functionally correct but significantly slower than the Ruby version. To improve performance, consider using NumPy or Cython for optimized calculations, replacing list operations with sets for faster lookups, and implementing memoization where possible. For command-line input and underscores in numbers, use int(input().replace('_', '')) to parse correctly. Let me know if you need further optimizations.

[jzakiya]

The Python translation is functionally correct but significantly slower than the Ruby version. To improve performance, consider using NumPy or Cython for optimized calculations, replacing list operations with sets for faster lookups, and implementing memoization where possible. For command-line input and underscores in numbers, use int(input().replace('_', '')) to parse correctly. Let me know if you need further optimizations.

I'm not a Python programmer so how to use those libraries is foreign to me.
Can you alter the code to do what you suggested?

[jzakiya]

I've updated the code to make it shorter|simpler and a bit faster.
Still would like to see ways to optimize performance.

import time
from math import gcd

def prime_pairs_lohi(n):
    if n&1 == 1 or n < 4: return print("Input not even n > 2")
    if n <= 6: print([n, 1]); print([n/2, n/2]); print([n/2, n/2]); return

    # generate the low-half-residues (lhr) r < n/2
    lhr = []                              # lhr (low half residues) of n
    ndiv2, rhi = n//2, n-2                # lhr:hhr midpoint, max residue limit
    for r in range(3, ndiv2, 2):
        if gcd(r, n) == 1: lhr.append(r)

    # store all powers and cross-products of the lhr members < n-2
    lhr_mults = []                        # lhr multiples, not part of a pcp
    lhr_dup = lhr.copy()                  # make copy of the lhr members list
    while True:                           # do mults of 1st list r w/others
        r = lhr_dup.pop(0)                # get first lhr_dup element, reduce it by 1
        if len(lhr_dup) == 0: break       # exit if lhr_dup empty
        rmax = rhi // r                   # ri can't multiply r with values > this
        if r < rmax: lhr_mults.append(r*r) # for r^2 multiples
        if lhr_dup[0] > rmax: break       # exit if product of consecutive r’s > n-2
        for ri in lhr_dup:                # for each residue in reduced list
            if ri > rmax: break           # exit for r if cross-product with ri > n-2
            lhr_mults.append(r * ri)      # store value if < n-2

    # convert lhr_mults vals > n/2 to their lhr complements n-r,
    # store them, those < n/2, in lhr_del; it now holds non-pcp lhr vals
    for r in lhr_mults:                   # remove lhr mults from lhr
        i =  r if r < ndiv2 else n-r
        if i in lhr: lhr.remove(i)

    print([n, len(lhr)])                  # show n and pcp prime pairs count
    print([lhr[0],  n-lhr[0]])            # show first pcp prime pair of n
    print([lhr[-1], n-lhr[-1]])           # show last  pcp prime pair of n

n = int(input())                          # get n value from terminal
t1 = time.time()                          # start timing code
prime_pairs_lohi(n)                       # execute code
print(time.time() - t1)                   # show code execution time

[snippsat]

Can try this,should be 🚀

import sys
import time
from math import gcd

def prime_pairs_lohi(n):
    # Check for even numbers > 2
    if n & 1 or n < 4:
        print("Input not even n > 2")
        return
    # Special case for very small n
    if n <= 6:
        print([n, 1])
        print([n // 2, n // 2])
        print([n // 2, n // 2])
        return
    ndiv2, rhi = n // 2, n - 2

    # --- Step 1: Generate the low-half-residues (lhr)
    # These are the odd numbers in 3..(n//2 - 1) that are coprime with n.
    lhr = [r for r in range(3, ndiv2, 2) if gcd(r, n) == 1]

    # --- Step 2: Compute powers of lhr members (that are < n-2)
    lhr_mults = []
    for r in lhr:
        if r * r > rhi:
            break
        r_pwr = r
        # While the next power is still < n-2, multiply and store.
        while r_pwr * r < rhi:
            r_pwr *= r
            lhr_mults.append(r_pwr)

    # --- Step 3: Compute cross-products of lhr members (< n-2)
    # Instead of using pop(0) (which is slow), we iterate using indices.
    L = len(lhr)
    for i in range(L):
        r = lhr[i]
        # For a given r, we only care about partners ri with r * ri < n-2.
        ri_max = rhi // r
        # If even the smallest candidate after r is too big, we can break out.
        if i + 1 < L and lhr[i + 1] > ri_max:
            break
        for j in range(i + 1, L):
            if lhr[j] > ri_max:
                break
            lhr_mults.append(r * lhr[j])

    # --- Step 4: Remove all non-ppc (prime pair complement) numbers from lhr.
    # For each value from the multiples, compute its "complement" in the lhr sense.
    lhr_del = { (x if x < ndiv2 else n - x) for x in lhr_mults }
    # Filter out all values that appear in the lhr_del set.
    lhr = [x for x in lhr if x not in lhr_del]

    # --- Finally, display the results.
    print([n, len(lhr)])
    print([lhr[0], n - lhr[0]])
    print([lhr[-1], n - lhr[-1]])

if __name__ == '__main__':
    # Allow input from the command line like Ruby.
    # Also allow underscores in numbers (e.g. 1_000_000)
    if len(sys.argv) > 1:
        # Remove any underscores then convert to int.
        try:
            n = int(sys.argv[1].replace('_', ''))
        except ValueError:
            print("Invalid number:", sys.argv[1])
            sys.exit(1)
    else:
        try:
            n = int(input("Enter even number > 2: ").replace('_', ''))
        except ValueError:
            print("Invalid input.")
            sys.exit(1)
    start_time = time.time()
    prime_pairs_lohi(n)
    print("Elapsed time:", time.time() - start_time)

Output:
Enter even number > 2: 400000
[400000, 2487]
[11, 399989]
[199967, 200033]
Elapsed time: 0.1609971523284912

Your code.

Output:
400000
[400000, 2487]
[11, 399989]
[199967, 200033]
70.47208786010742

[jzakiya]

Hey thanks for your great fast translation!
My faith in Python has been restored.

I modded it a bit to match it with the updated Ruby code version.

Here's the updated Ruby code.

# Enable YJIT if using CRuby >= 3.3"
RubyVM::YJIT.enable if RUBY_ENGINE == "ruby" and RUBY_VERSION.to_f >= 3.3

def prime_pairs_lohi(n)
  return puts "Input not even n > 2" unless n.even? && n > 2
  return (pp [n, 1]; pp [n/2, n/2]; pp [n/2, n/2]) if n <= 6

  # generate the low-half-residues (lhr) r < n/2
  lhr = 3.step(n/2, 2).select { |r| r if r.gcd(n) == 1 }
  ndiv2, rhi = n/2, n-2            # lhr:hhr midpoint, max residue limit

  # identify and store all powers and cross-products of the lhr members < n-2
  lhr_mults = []                   # lhr multiples, not part of a pcp
  lhr_dup = lhr.dup                # make copy of the lhr members list
  while (r = lhr_dup.shift) && !lhr_dup.empty? # do mults of 1st list r w/others
    rmax = rhi / r                 # r can't multiply others with values > this
    lhr_mults << r * r if r < rmax # for r^2 multiples
    break if lhr_dup[0] > rmax     # exit if product of consecutive r’s > n-2
    lhr_dup.each do |ri|           # for each residue in reduced list
      break if ri > rmax           # exit for r if cross-product with ri > n-2
      lhr_mults << r * ri          # otherwise store cross-product
    end                            # check cross-products of next lhr member
  end

  # remove from lhr its lhr_mults, convert vals > n/2 to lhr complements first
  lhr -= lhr_mults.map { |r_del| r_del > ndiv2 ? n - r_del : r_del }

  pp [n, lhr.size]                 # show n and pcp prime pairs count
  pp [lhr.first, n-lhr.first]      # show first pcp prime pair of n
  pp [lhr.last,  n-lhr.last]       # show last  pcp prime pair of n
end

n = ARGV[0].to_i                   # get n value from terminal
t1 = Time.now                      # start execution timing
prime_pairs_lohi(n)                # execute code
pp Time.now - t1                   # show execution time

Here's my modification of the Python code to mimic Ruby style|functionally.

import sys
import time
from math import gcd

def prime_pairs_lohi(n):
    if (n & 1 == 1) or n < 4: print("Input not even n > 2"); return
    if n <= 6: print([n, 1]); print([n // 2, n // 2]); print([n // 2, n // 2]); return
    ndiv2, rhi = n // 2, n - 2                # lhr:hhr midpoint, max residue limit

    # generate the low-half-residues (lhr) r < n/2
    lhr = [r for r in range(3, ndiv2, 2) if gcd(r, n) == 1]

    # identify and store powers and cross-products of lhr members < n-2
    lhr_mults = []                            # lhr multiples, not part of a pcp
    L = len(lhr)-1                            # last lhr index value
    for i in range(L):                        # iterate thru lhr indexes
        r = lhr[i]                            # current lhr value
        rmax = rhi // r                       # r can't multiply others with values > this.
        if r < rmax: lhr_mults.append(r * r)  # for r^2 multiples
        if lhr[i + 1] > rmax: break           # exit if product of consecutive r’s > n-2
        for j in range(i + 1, L):             # for reduced lhr array indexes
            if lhr[j] > rmax: break           # exit for r if cross-product with ri > n-2
            lhr_mults.append(r * lhr[j])      # otherwise store cross-product

    # remove from lhr its lhr_mults, convert vals > n/2 to lhr complements first
    lhr_del = { (r if r < ndiv2 else n - r) for r in lhr_mults }
    lhr = [r for r in lhr if r not in lhr_del]  # removed lhr_mults leaves lhr all pcp primes

    print([n, len(lhr)])                      # show n and pcp prime pairs count
    print([lhr[0], n - lhr[0]])               # show first pcp prime pair of n
    print([lhr[-1], n - lhr[-1]])             # show last  pcp prime pair of n

if __name__ == '__main__':
    # Allow input from the command line like Ruby.
    # Also allow underscores in numbers (e.g. 1_000_000)
    if len(sys.argv) > 1:
        # Remove any underscores then convert to int.
        try:
            n = int(sys.argv[1].replace('_', ''))
        except ValueError:
            print("Invalid number:", sys.argv[1])
            sys.exit(1)
    else:
        try:
            n = int(input("Enter even number > 2: ").replace('_', ''))
        except ValueError:
            print("Invalid input.")
            sys.exit(1)
    start_time = time.time()
    prime_pairs_lohi(n)
    print(time.time() - start_time)

Here are some timing comparison examples.

Python 3.13.2 compiled from source code

➜  ~ ~/Python/python prime_pairs_lohi.py 315_000_000
[315000000, 1938593]
[11, 314999989]
[157499801, 157500199]
39.40176320075989

Ruby 3.1.4 installed with RVM

➜  ~ ruby prime_pairs_lohi.rb 315_000_000
[315000000, 1938593]
[11, 314999989]
[157499801, 157500199]
38.399992715

------------------------------------------
      n      | Ruby 3.4.1 | Python 3.13.2
-------------|------------|---------------
  10,000,000 |    1.96    |     1.72
-------------|------------|---------------
  50,000,000 |   11.27    |    10.12
-------------|------------|---------------
 100,000,000 |   24.51    |    20.91
-------------|------------|---------------
 150,000,000 |   20.35    |    23.33
-------------|------------|---------------
 200,000,000 |   51.45    |    45.40
-------------|------------|---------------
 250,000,000 |   70.42    |   118.68
-------------|------------|---------------
 300,000,000 |   44.01    |    49.28
-------------|------------|---------------
 315,000,000 |   38.40    |    39.40

The Python and Ruby versions are now pretty much comparable in speed,
though for n = 250M, I have no idea why Python was so much slower.

As I explain in my paper, the variance in the times between numbers is
due to the differences in the factorizatoin of each n. The more residues
an n has, the relatively fewer pcp prime pairs it will have.

Again, I really appreciate the presentation of the optimized Python code.
I'll study it in depth to learn more from it.

[Pedroski55]

You must have one fast computer if you can do 10 million such calculations in 1.72 seconds! How fast can you do 400 000?

My laptop takes

Elapsed time: 11.912400484085083

for 10 000 000

or

Elapsed time: 0.1457960605621338

for 400 000

I think Python is popular because we can give variables names which indicate what they are, not like lhr, rhi to baffle the general public!

#! /usr/bin/python3
import time

# for a given even number, find prime numbers in that range which add up to that number
# function to find prime numbers
def is_prime(num):
    sqr_num = int(num**0.5 + 1) 
    for i in range(3, sqr_num, 2):
        if (num % i) == 0:
          return False
    return True   

def get_prime_pairs(num):
    small_primes = [2]
    half = num // 2
    for j in range(1, half, 2):
        if is_prime(j):
            small_primes.append(j)    
    # now we have a list of primes in the range of num // 2
    # subtract each one from the number and see if the result is a prime number
    results =[]
    for p in small_primes:
        if is_prime(num - p):
            results.append((p, num - p))    
    return results
    
if __name__ == "__main__":
    anum = input('Enter an even number like 242424 or 24 24 24 or 242_424 ... ')
    word = anum.replace('_', '').replace(' ', '')
    while not word.isdigit():
        anum = input('Enter an even number like 242424 or 24 24 24 or 242_424, use space or _ to separate digits if you wish ... ')
        word = anum.replace('_', '').replace(' ', '')    
    num = int(word)
    start_time = time.time()    
    res = get_prime_pairs(num)
    print("Elapsed time:", time.time() - start_time)
    print(f'Length of prime pairs list = {len(res)}')
    print(f'Start number was: {num}, first prime pair = {res[0]}, last prime pair = {res[-1]}')
    # check the results for mistakes
    for i in range(len(res)):
         tup = res[i]
         total = tup[0] + tup[1]
         if not total == num:
             print(f'Found a mistake: total = {total}')
    print('Johann Carl Friedrich Gauß for President!')

[jzakiya]

FYI.
I released the final paper.
I replaced all the Ruby code in it with optimized Crystal versions, for speed.
They're simple, so can be easily translated in Python if desired.

[url=https://www.academia.edu/127404211/Proof_of_Goldbachs_Conjecture_and_Bertrands_Postulate_Using_Prime_Generator_Theory_PGT_[/url]