Generate Prime Pairs for Goldbach's Conjecture

Jabari Zakiya — Fri, 07 Feb 2025 23:48:50 +0000

Hi.

This is my first program of any substance done in Julia.
It was told Julia is easy to program in, and fast, so I gave it a try.

The code works (gives correct results) but I'm looking for help to improve it.
It generates all the prime pairs that sum to any even integer n.

If you want an explanation of hows|whys it works read my just released paper.

Proof of Goldbach's Conjecture and Bertrand's Postulate Using Prime Genrator Theory(GPT)

https://www.academia.edu/127404211/Proof_of_Goldbachs_Conjecture_and_Bertrands_Postulate_Using_Prime_Generator_Theory_PGT_

Here's the Ruby code from the paper, which is much faster than my Julia 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
  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 Julia (functional) translation.
I know there's gotta be a faster, more elegant, idomatic way to do it.

function prime_pairs_lohi(n)
  if (n&1 == 1 || n < 4) return println("Input not even n > 2") end
  if (n <= 6) println([n, 1]); println([div(n,2),div(n,2)]); println([div(n,2),div(n,2)]); return end

  # generate the low-half-residues (lhr) r < n/2
  ndiv2, rhi = div(n,2), n-2         # lhr:hhr midpoint, max residue limit
  lhr = []                           # array for low half residues
  for r in 3:2:ndiv2; if (gcd(r, n) == 1) append!(lhr, r) end end
  lhr_mults = []                     # for lhr values not part of a pcp

  # store all the powers of the lhr members < n-2
  for r in lhr                       # step thru the lhr members
    r_pwr = r                        # set to first power of r
    if (r > div(rhi, r_pwr)) break end # exit if r^2 > n-2, as all others are too
    while (r < div(rhi, r_pwr))      # while r^e < n-2
      r_pwr *= r                     # increase power of r
      append!(lhr_mults, r_pwr)      # store its current power of r
    end
  end

  # store all the cross-products of the lhr members < n-2
  i = 1; ln = length(lhr)
  while (i < ln)
    r = lhr[i]
    rmax = div(rhi, r)               # ri can't multiply r with values > this
    if (lhr[i+1] > rmax) break end   # exit if product of consecutive r’s > n-2
    j = i+1
    while (j < ln)                   # for each residue in reduced list
      ri = lhr[j]
      if (ri > rmax) break end       # exit for r if cross-product with ri > n-2
      append!(lhr_mults, r * ri)     # store value if < n-2
      j += 1
    end
    i += 1
  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 = []
  for r in lhr_mults
    r_del = (r > ndiv2) ? n - r : r
    append!(lhr_del, r_del)
  end

  lhr = setdiff(lhr,lhr_del)         # remove lhr_del residues from lhr

  println([n,  length(lhr)])         # show n and pcp prime pairs count
  println([first(lhr),n-first(lhr)]) # show first pcp prime pair of n
  println([last(lhr), n-last(lhr)])  # show last  pcp prime pair of n
end


num = readline()                     # get n value from terminal
n = parse(Int64, num)
prime_pairs_lohi(n)                  # show execution runtime as last output
println()

It computes correct answers but:
1) It's slower than the Ruby version.
2) Taking input directly from the cli isn't the same as Ruby
3) It doesn't take input numbers using underscores: 123_456_780
4) It needs internal timer like Ruby

Here a timing difference example.

➜  ~ ruby prime_pairs_lohi.rb 100_000_000
[100000000, 291400]
[11, 99999989]
[49999757, 50000243]
24.21507651

➜  ~ time julia prime_pairs_lohi.jl
100000000
[100000000, 291400]
[11, 99999989]
[49999757, 50000243]

julia prime_pairs_lohi.jl  39.54s user 3.68s system 87% cpu 49.275 total

So I'm asking help to improve performance and make entering numbers the same as Ruby.
I used the latest Julia 1.11.3 and Ruby 3.4.1 w/YJIT

Julia Community 🟣: Jabari Zakiya

Generate Prime Pairs for Goldbach's Conjecture