mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Blogorrhea > jzakiya

Reply
 
Thread Tools
Old 2022-07-09, 17:59   #78
jzakiya
 
Jul 2014

22×3×5 Posts
Default

Quote:
Originally Posted by Rustum View Post
It turns out that the Python codes of "hathix" have bugs (Issue 1 at the Github site). They report composite numbers as primes and leave out known primes (such as even a lowly 7) from the list of primes.

Until these bugs are fixed and the output lists of primes have been verified, any conclusions (regarding the correctness of the so called Prime Generators or the speed of the algorithm) are premature.
The proficiency and accuracy of the math of Prime Generators and Prime Generator Theory (PGT) has been verified and shown to be correct, over and over.

Because someone else, besides me, apparently made implementation errors with my sieve (and apparently other sieves) in no way reflects on the "correctness" of the algorithm, which MY CODE demonstrates.

If you doubt the "correctness" of the algorithm, math, or implementations, do it with my work, not others.
I assume you (nor anyone else) can find errors in the correctness of the results my code produces, or I'm sure I would have heard it by now.

If you think ANYTHING I have presented is incorrect, please provide a detailed explanation of exactly what you think is wrong, and we can have an objective discussion of the math and/or software you cite.

My latest paper fully explains the algorithm and software in detail, to educate those who want to know, as much about the math and software aspects of its implementation in detail, so people can implement it in any language, or in hardware.

The math works, the algorithm implements it, and the software demonstrates it.
Are there any other real questions anybody has about its efficacy, accuracy, and speed?
jzakiya is offline   Reply With Quote
Old 2022-07-09, 21:13   #79
mathwiz
 
Mar 2019

2·163 Posts
Default

Quote:
Originally Posted by jzakiya View Post
The math works, the algorithm implements it, and the software demonstrates it.
Are there any other real questions anybody has about its efficacy, accuracy, and speed?
Yes:

If you believe you have an actual, mathematically sound proof of the Twin Primes conjecture, why haven't you submitted your proof to a mathematical journal?
mathwiz is offline   Reply With Quote
Old 2022-07-09, 21:18   #80
Rustum
 
Jul 2022

5 Posts
Default How does one get a list of primes from your codes?

JZakiya, the issue that I have is that most of your codes only report the run time. Some of them report the last prime found and the count of primes found. However, for verification, we need to be able to retrieve from your code all the primes found and we need documentation regarding how to do that.

Such a facility is provided by Walisch's Primesieve, with his functions NextPrime(), PreviousPrime() and IsPrime().

Retrieving prime number values from a bitmap representation does entail overhead, but users of your codes need to be shown how to obtain these results in the form of function values or a returned Primes array, especially when your code is in a programming language other than the one they use most frequently.
Rustum is offline   Reply With Quote
Old 2022-07-09, 23:55   #81
jzakiya
 
Jul 2014

22·3·5 Posts
Default

Quote:
Originally Posted by Rustum View Post
JZakiya, the issue that I have is that most of your codes only report the run time. Some of them report the last prime found and the count of primes found. However, for verification, we need to be able to retrieve from your code all the primes found and we need documentation regarding how to do that.

Such a facility is provided by Walisch's Primesieve, with his functions NextPrime(), PreviousPrime() and IsPrime().

Retrieving prime number values from a bitmap representation does entail overhead, but users of your codes need to be shown how to obtain these results in the form of function values or a returned Primes array, especially when your code is in a programming language other than the one they use most frequently.
If you want to see the actual primes (which can be allot, depending on the number range you want),
the easiest way to do it is to use my primes-utils RubyGem: https://rubygems.org/search?query=primes-utils.
Of course, you need to run it on Ruby (I haven't released the Crystal version yet, though I have it).

If you want to see all the code see my PRIME-UTILS HANDBOOK:
https://www.academia.edu/19786419/PRIMES_UTILS_HANDBOOK

I've cited these references in almost all my papers (which apparently people don't read).

To see the number of primes do: n.primescnt or n1.primescnt n2 between a range
To see the primes values do: n.primes or n1.primes n2 between a range

I corrected the Python 2 code version of Hathix: https://github.com/hathix/prime-algorithms
Here's a modern correct version of the code, that still works with Python 2, as the original.
UnComment the last 2 print statement to see the primes count, and/or their values.

The Ruby code is way faster than this, which is no way as fast as the various compiled language versions.
But if you never run any of the code I guess it doesn't matter how fast it is, or what results they produce.
It seems like there always another reason not to accept the veracity of what I present.


Code:
#SIEVE OF ZAKIYA
from math import sqrt, ceil
from time import time

LIMIT = 1 * 10 ** 7
#LIMIT = 7919   # 1,000th prime
start = time()

# all prime candidates > 5 are of form 30*k+(7,11,13,17,19,23,31)
mod=30; rescnt=8             # modulus value; number of residues
residues = [7,11,13,17,19,23,29,31]
pos = [0,0,0,0,0,0,0,0,0,1,0,2,0,0,0,3,0,4,0,0,0,5,0,0,0,0,0,6,0,7]

num = LIMIT-1 | 1            # if LIMIT even number then subtract 1
k = (num-2)/mod              # resgroup value for num
modk = mod*k; r = rescnt - 1 # kth residue group, base num value
while num < modk+residues[r]: r -=1  # find last pc position <= num
maxprms = k*rescnt + r + 1   # max number of prime candidates
prms = [True]*maxprms        # set all prime candidates to True

# sieve to eliminate nonprimes from prms
sqrtN = int(sqrt(num))
modk=k=0; r = -1

for prm in prms:
    r += 1
    if r == rescnt: r = 0; k += 1; modk += mod
    if not prm: continue
    prm_r = residues[r]
    prime = modk + prm_r
    if prime > sqrtN: break
    prmstep = prime*rescnt
    for ri in residues:
        kn,rr = divmod(prm_r * ri - 2,mod)
        kpm = (k*(prime + ri) + kn)*rescnt + pos[rr]
        for nprm in xrange(kpm, maxprms, prmstep): prms[nprm] = False

# the prms array now has all the positions for primes 7..N
primes = [2,3,5]
modk=0; r=-1
for prime in prms:
    r += 1
    if r == rescnt: r = 0; modk += mod
    if prime: primes.append(modk+residues[r])

elapsed = time() - start
print("%.3f" % elapsed)
#print("Number of primes is: ", len(primes))
#print primes
jzakiya is offline   Reply With Quote
Old 2022-07-10, 05:48   #82
jzakiya
 
Jul 2014

22·3·5 Posts
Default

Here's the Ruby equivalent of the Python code, which is faster in Ruby.
Just paste the code in files sozp5.[py|rb] and run as: $ ruby|python sozp5.[rb|py]

Code:
# P5 Sieve of Zakiya (SoZ)

def sozp5(num)
  # P5 Prime Generator has form: P5 = 30*k + {7,11,13,17,19,23,31}
  mod = 30; rescnt = 8         # P5 modulus value; number of residues
  residues = [7,11,13,17,19,23,29,31]
  pos = [0,0,0,0,0,0,0,0,0,1,0,2,0,0,0,3,0,4,0,0,0,5,0,0,0,0,0,6,0,7]

  num = num-1 | 1              # if num even number then subtract 1
  k = (num-2)/mod              # resgroup value for num
  modk = mod*k; r = rescnt - 1 # kth residue group, base num value
  while num < modk+residues[r]; r -=1 end # find last pc position <= num
  maxprms = k * rescnt + r + 1 # max number of prime candidates
  prms = [true]*maxprms        # set all prime candidates to True

  # sieve to eliminate nonprimes from prms
  sqrtN = Integer.sqrt(num)
  modk, k, r = 0, 0, -1

  prms.each do |prm|
    r += 1; if r == rescnt; r = 0; k += 1; modk += mod end
    next unless prm
    prm_r = residues[r]
    prime = modk + prm_r
    break if prime > sqrtN
    prmstep = prime * rescnt
    residues.each do |ri|
      kn, rr = (prm_r * ri - 2).divmod mod
      kpm = (k * (prime + ri) + kn) * rescnt + pos[rr]
      while kpm < maxprms; prms[kpm] = false; kpm += prmstep end
  end end
  # the prms array now has all the positions for primes 7..N
  primes = [2, 3, 5]
  modk, r = 0, -1
  prms.each do |prime|
    r += 1; if r == rescnt; r = 0; modk += mod end
    primes << modk + residues[r] if prime
  end
  primes
end

num = 1 * 10 ** 9
start = Time.now
primes = sozp5 num
elapsed = Time.now - start
#print primes
puts "\nNumber of primes upto #{num} is #{primes.size}"
puts elapsed
jzakiya is offline   Reply With Quote
Old 2022-07-10, 20:46   #83
jzakiya
 
Jul 2014

1111002 Posts
Default

Here's a generic SoZ implementation (in Ruby) that will work for any generator from
P5 or greater. You give it the input value, and a prime >= 5 for the generator you want,
and it creates the Pn generator parameters, gives execution time(s), and returns a primes array.

Depending on how much memory your system has, it's set to go upto P17.
The larger the Pn the smaller the number space the primes will live in.
However there's a trade off. Larger Pn generators don't become useful until the inputs become large.
The switchover point from one Pn to the next is somewhat hardware dependent (vs purely mathematical).

You can see comparisons of how different Pn generators behavior for different input values, which I urge to do.
Paste the code in a file, e.g. sozpn.rb and run on different Rubies if you want: CRuby, JRuby, Truffleruby, etc.

Below is the code and some sample outputs run on my Linux based Lenovo Legion 7 with Ryzen 9 5900HX cpu.
Code:
# sozpn.rb

 # General method to perform Sieve of Zakiya (SoZ) for any Pn

def sozpn(numb, pn)
  tp = Time.now                          # start timing Pn paramatization
  prms = [2, 3, 5, 7, 11, 13, 17, 19]
  modpn, primes = 1, []                  # compute Pn's modulus, store primes
  prms.each { |prm| break if prm > pn; modpn *= prm; primes << prm }
  residues = []                          # save residues here
  rc, inc, mid = 5, 2, modpn / 2         # use P3's PGS to generate rcs
  while rc < mid                         # find PG's 1st half residues
    if rc.gcd(modpn) == 1                # if residue complement rc a residue
      residues << rc << modpn - rc       # save it and its modular complement
    end
    rc += inc; inc ^= 0b110              # create next P3 sequence pc: 5 7 11 13 17 19 ...
  end
  residues.sort!; residues << modpn - 1 << modpn + 1
  rescnt = residues.size
  #puts "P#{pn} paramatization time is #{Time.now - tp} secs"

  #ts = Time.now                 # start timing Pn sieve
  num = numb-1 | 1              # if num is even then subtract 1
  k, nr = (num-2).divmod modpn  # resgroup|residue value for num
  num_r, r = nr + 2, rescnt - 1 # num residue, last resgroup index value
  #puts num_r, r, k, nr, residues[r]
  if num_r < residues[0]; k -=1; r = rescnt - 1
  else while num_r < residues[r]; r -=1 end # find last pc position <= num
  end
  maxprms = k * rescnt + r + 1  # max number of prime candidates
  prms = [true]*maxprms         # set all prime candidates to True

  # sieve to eliminate nonprimes from prms
  sqrtN = Integer.sqrt(num)
  modk, k, r = 0, 0, -1

  prms.each do |prm|
    r += 1; if r == rescnt; r = 0; k += 1; modk += modpn end
    next unless prm
    prm_r = residues[r]
    prime = modk + prm_r
    break if prime > sqrtN
    prmstep = prime * rescnt
    residues.each do |ri|
      kn, rr = (prm_r * ri - 2).divmod modpn
      kpm = (k * (prime + ri) + kn) * rescnt + residues.index(rr + 2)
      while kpm < maxprms; prms[kpm] = false; kpm += prmstep end
  end end
  # the prms array now has all the positions for primes r0..N
  modk, r = 0, -1
  prms.each do |prime|
    r += 1; if r == rescnt; r = 0; modk += modpn end
    primes << modk + residues[r] if prime
  end
  puts "P#{pn} sieve time is #{Time.now - tp} secs"
  puts "Primes count upto #{numb} is #{primes.size}"
  primes
end

num = 1 * 10 ** 2
puts "Input = #{num}"
primes = sozpn num, 5
#print primes
puts
primes = sozpn num, 7
#print primes
puts
primes = sozpn num, 11
#print primes
puts

num = 1 * 10 ** 5
puts "Input = #{num}"
primes = sozpn(num, 5)
#print primes
puts
primes = sozpn(num, 7)
#print primes
puts
primes = sozpn(num, 11)
#print primes
puts

num = 1 * 10 ** 7
puts "Input = #{num}"
primes = sozpn num, 5
#print primes
puts
primes = sozpn num, 7
#print primes
puts
primes = sozpn num, 11
#print primes
puts

num = 1 * 10 ** 9
puts "Input = #{num}"
primes = sozpn(num, 5)
#print primes
puts
primes = sozpn(num, 7)
#print primes
puts
primes = sozpn(num, 11)
#print primes
puts
Sample output

Code:
$ ruby sozpn.rb 
Input = 100 
P5 sieve time is 1.5085e-05 secs 
Primes count upto 100 is 25 

P7 sieve time is 1.1244e-05 secs 
Primes count upto 100 is 25 

P11 sieve time is 6.3555e-05 secs 
Primes count upto 100 is 25 

Input = 100000 
P5 sieve time is 0.002141048 secs 
Primes count upto 100000 is 9592 

P7 sieve time is 0.002339746 secs 
Primes count upto 100000 is 9592 

P11 sieve time is 0.027745907 secs 
Primes count upto 100000 is 9592 

Input = 10000000 
P5 sieve time is 0.299301798 secs 
Primes count upto 10000000 is 664579 

P7 sieve time is 0.254148978 secs 
Primes count upto 10000000 is 664579 

P11 sieve time is 0.413922539 secs 
Primes count upto 10000000 is 664579 

Input = 1000000000 
P5 sieve time is 43.320939952 secs 
Primes count upto 1000000000 is 50847534 

P7 sieve time is 35.600202205 secs 
Primes count upto 1000000000 is 50847534 

P11 sieve time is 33.511398366 secs 
Primes count upto 1000000000 is 50847534
jzakiya is offline   Reply With Quote
Old 2022-07-11, 16:17   #84
jzakiya
 
Jul 2014

748 Posts
Default

Here are comparison results run on the 3 major Ruby VMs:

CRuby 3.1.2 (Matz's C VM), JRuby 9.3.6.0 (Java VM), TruffleRuby 22.1.0 (Graal VM)
These are all the current stable releases atow (M July 11, 2022).

Truffleruby really starts to shine as the inputs get bigger, followed by JRuby.

Code:
➜  ~ ruby -v
ruby 3.1.2p20 (2022-04-12 revision 4491bb740a) [x86_64-linux]
➜  ~ ruby sozpn.rb
Input = 100
P5 sieve time is 1.4178e-05 secs
Primes count upto 100 is 25

P7 sieve time is 1.1314e-05 secs
Primes count upto 100 is 25

P11 sieve time is 6.3904e-05 secs
Primes count upto 100 is 25

Input = 100000
P5 sieve time is 0.002120515 secs
Primes count upto 100000 is 9592

P7 sieve time is 0.002502057 secs
Primes count upto 100000 is 9592

P11 sieve time is 0.027268683 secs
Primes count upto 100000 is 9592

Input = 10000000
P5 sieve time is 0.298991633 secs
Primes count upto 10000000 is 664579

P7 sieve time is 0.248423825 secs
Primes count upto 10000000 is 664579

P11 sieve time is 0.399848304 secs
Primes count upto 10000000 is 664579

Input = 1000000000
P5 sieve time is 43.391012488 secs
Primes count upto 1000000000 is 50847534

P7 sieve time is 35.780079033 secs
Primes count upto 1000000000 is 50847534

P11 sieve time is 33.494564431 secs
Primes count upto 1000000000 is 50847534

➜  ~ ruby -v
jruby 9.3.6.0 (2.6.8) 2022-06-27 7a2cbcd376 Java HotSpot(TM) 64-Bit Server VM 15.0.2+7-27 on 15.0.2+7-27 +jit [x86_64-linux]
➜  ~ ruby -J-Xmx15000M sozpn.rb
Input = 100
P5 sieve time is 0.013915 secs
Primes count upto 100 is 25

P7 sieve time is 0.000808 secs
Primes count upto 100 is 25

P11 sieve time is 0.003893 secs
Primes count upto 100 is 25

Input = 100000
P5 sieve time is 0.028162 secs
Primes count upto 100000 is 9592

P7 sieve time is 0.010943 secs
Primes count upto 100000 is 9592

P11 sieve time is 0.049363000000000004 secs
Primes count upto 100000 is 9592

Input = 10000000
P5 sieve time is 0.33296600000000004 secs
Primes count upto 10000000 is 664579

P7 sieve time is 0.211999 secs
Primes count upto 10000000 is 664579

P11 sieve time is 0.267343 secs
Primes count upto 10000000 is 664579

Input = 1000000000
P5 sieve time is 36.422362 secs
Primes count upto 1000000000 is 50847534

P7 sieve time is 30.107352 secs
Primes count upto 1000000000 is 50847534

P11 sieve time is 27.155698 secs
Primes count upto 1000000000 is 50847534

➜  ~ ruby -v
truffleruby 22.1.0, like ruby 3.0.2, GraalVM CE Native [x86_64-linux]
➜  ~ ruby sozpn.rb
Input = 100
P5 sieve time is 0.0012900000000000001 secs
Primes count upto 100 is 25

P7 sieve time is 0.000133 secs
Primes count upto 100 is 25

P11 sieve time is 0.0013030000000000001 secs
Primes count upto 100 is 25

Input = 100000
P5 sieve time is 0.020905 secs
Primes count upto 100000 is 9592

P7 sieve time is 0.029612000000000003 secs
Primes count upto 100000 is 9592

P11 sieve time is 0.028702999999999923 secs
Primes count upto 100000 is 9592

Input = 10000000
P5 sieve time is 0.103038 secs
Primes count upto 10000000 is 664579

P7 sieve time is 0.062242000000000006 secs
Primes count upto 10000000 is 664579

P11 sieve time is 0.08458600000000001 secs
Primes count upto 10000000 is 664579

Input = 1000000000
P5 sieve time is 9.027282 secs
Primes count upto 1000000000 is 50847534

P7 sieve time is 6.710319 secs
Primes count upto 1000000000 is 50847534

P11 sieve time is 6.251931 secs
Primes count upto 1000000000 is 50847534
jzakiya is offline   Reply With Quote
Old 2022-07-11, 18:04   #85
jzakiya
 
Jul 2014

22×3×5 Posts
Default

Here's the fully revised code, completely commented.

Code:
# sozpn.rb
# General method to perform Sieve of Zakiya (SoZ) for any Pn

def sozpn(numb, pn)                      # find primes upto numb with Pn Prime Generator
  tp = Time.now                          # start timing Pn paramatization, full sieve
  prms = [2, 3, 5, 7, 11, 13, 17, 19]    # primes list to make modpn = pn#
  modpn, primes = 1, []                  # Pn's modulus, array to store primes
  prms.each { |prm| break if prm > pn; modpn *= prm; primes << prm }
  residues = []                          # save Pn's residues here
  rc, inc, mid = 5, 2, modpn / 2         # use P3's PGS to generate rcs
  while rc < mid                         # find Pn's 1st half residues
    if rc.gcd(modpn) == 1                # if residue candidate rc a residue
      residues << rc << modpn - rc       # save it and its modular complement
    end
    rc += inc; inc ^= 0b110              # create next P3 sequence rc: 5 7 11 13 17 19 ...
  end
  residues.sort!; residues << modpn - 1 << modpn + 1 # store all residues in order
  rescnt = residues.size                             # save Pn's residues count (pn-1)#
  #puts "P#{pn} paramatization time is #{Time.now - tp} secs" # (optional)

  #ts = Time.now                # (optional) start timing just Pn sieve
  num = numb-1 | 1              # if numb is even then subtract 1 (to make odd)
  k, nr = (num-2).divmod modpn  # resgroup|residue values for num
  num_r, r = nr+2, rescnt-1     # num residue; last index value for residues array
  if num_r < residues[0]; k -=1             # if true, largest resgroup is the one before num's
  else while num_r < residues[r]; r -=1 end # else find largest residue <= num's in its resgroup
  end
  maxprms = k*rescnt + r + 1    # max number of prime candidates positions needed in pcs table
  prms = [true]*maxprms         # set all prime candidates to True

  # sieve to eliminate nonprimes from prms
  sqrtN = Integer.sqrt(num)     # mark nonprimes with primes up to this limit
  modk, k, r = 0, 0, -1         # initialize Pn sieve parameters

  prms.each do |prm|            # mark nonprime pc positions in prms
    r += 1; if r == rescnt; r = 0; k += 1; modk += modpn end
    next unless prm             # if position not a prime, skip to next pc position
    prm_r = residues[r]         # save pc's residue if a prime
    prime = modk + prm_r        # numerate the prime value
    break if prime > sqrtN      # were finished when prime > limit
    prmstep = prime * rescnt    # pc positions to prime's next multiple in table
    residues.each do |ri|       # mark prime's multiples along each restrack in table
      kn, rr = (prm_r * ri - 2).divmod modpn
      kpm = (k * (prime + ri) + kn) * rescnt + residues.index(rr + 2)
      while kpm < maxprms; prms[kpm] = false; kpm += prmstep end
  end end
  # the prms array now has all the prime positions from r0..num, now extract them
  modk, r = 0, -1                                     # initialize Pn parameters
  prms.each do |prime|                                # check each pc position in array
    r += 1; if r == rescnt; r = 0; modk += modpn end  # divided into Pn residue groups
    primes << modk + residues[r] if prime             # for prime pc position, numerate|store it
  end
  puts "P#{pn} sieve time is #{Time.now - tp} secs"   # sieve time
  puts "Primes count upto #{numb} is #{primes.size}"  # prime count upto input numb
  primes                                              # return array of prime values
end

Last fiddled with by jzakiya on 2022-07-11 at 18:43
jzakiya is offline   Reply With Quote
Old 2022-07-12, 20:50   #86
jzakiya
 
Jul 2014

1111002 Posts
Default

Here is the Crystal (1.5.0, Tu July 12, 2022) version of the Ruby code.
Crystal is a typed compiled language that's "Ruby inspired".
Except for a few typing requirements, method name differences, et al,
the code is about ~95% the same, but results in huge performance increases.
As you can see, the times are much, much, faster.

The major limitation of this sozpn implementation is that the 'prms' array
of prime candidates (pcs) grows proportionally as input values increase.
So the size of your system memory determines how big your inputs can be.
This is why the Segmented Sieve of Zakiya (SSoZ) is necessary, to allow
processing of large numbers and ranges, to optimize system memory use.

I HOPE it's empirically clear now, the S|SoZ are the most efficient, flexible,
and fastest family of algorithms to find primes (here in only ~60 loc). And it's
due to the efficiency|simplicity of the math of Prime Generator Theory (PGT).

Code:
# sozpn.cr
# General method to perform Sieve of Zakiya (SoZ) for any Pn

require "bit_array"

def sozpn(numb, pn)                      # find primes upto numb with Pn Prime Generator
  tp = Time.monotonic                    # start timing Pn paramatization, full sieve
  prms = [2, 3, 5, 7, 11, 13, 17, 19]    # primes list to make modpn = pn#
  modpn, primes = 1u64, [] of UInt64     # Pn's modulus, array to store primes
  prms.each { |prm| break if prm > pn; modpn *= prm; primes << prm.to_u64 }
  residues = [] of UInt64                # save Pn's residues here
  rc, inc, mid = 5u64, 2u64, modpn / 2   # use P3's PGS to generate rcs
  while rc < mid                         # find Pn's 1st half residues
    if rc.gcd(modpn) == 1                # if residue candidate rc a residue
      residues << rc << modpn - rc       # save it and its modular complement
    end
    rc += inc; inc ^= 0b110              # create next P3 sequence rc: 5 7 11 13 17 19 ...
  end
  residues.sort!; residues << modpn - 1 << modpn + 1 # store all residues in order
  rescnt = residues.size.to_u64          # save Pn's residues count (pn-1)#
  #puts "P#{pn} paramatization time is #{Time.montonic - tp} secs" # (optional)

  #ts = Time.monotonic          # (optional) start timing just Pn sieve
  num = numb-1 | 1              # if numb is even then subtract 1 (to make odd)
  k, nr = (num-2).divmod modpn  # resgroup|residue values for num
  num_r, r = nr+2, rescnt-1     # num residue; last index value for residues array
  if num_r < residues[0]; k -=1             # if true, largest resgroup is the one before num's
  else while num_r < residues[r]; r -=1 end # else find largest residue <= num's in its resgroup
  end
  maxprms = k*rescnt + r + 1    # max number of prime candidates positions needed in pcs table
  prms = BitArray.new(maxprms, true)        # set all prime candidates to True

  # sieve to eliminate nonprimes from prms
  sqrtN = Math.isqrt(num)       # mark nonprimes with primes up to this limit
  modk, k, r = 0u64, 0u64, -1   # initialize Pn sieve parameters

  prms.each do |prm|            # mark nonprime pc positions in prms
    r += 1; if r == rescnt; r = 0; k += 1; modk += modpn end
    next unless prm             # if position not a prime, skip to next pc position
    prm_r = residues[r]         # save pc's residue if a prime
    prime = modk + prm_r        # numerate the prime value
    break if prime > sqrtN      # were finished when prime > limit
    prmstep = prime * rescnt    # pc positions to prime's next multiple in table
    residues.each do |ri|       # mark prime's multiples along each restrack in table
      kn, rr = (prm_r * ri - 2).divmod modpn
      kpm = (k * (prime + ri) + kn) * rescnt + residues.index(rr + 2).not_nil!.to_u64
      while kpm < maxprms; prms[kpm] = false; kpm += prmstep end
  end end
  # the prms array now has all the prime positions from r0..num, now extract them
  modk, r = 0u64, -1                                  # initialize Pn parameters
  prms.each do |prime|                                # check each pc position in array
    r += 1; if r == rescnt; r = 0; modk += modpn end  # divided into Pn residue groups
    primes << modk + residues[r] if prime             # for prime pc position, numerate|store it
  end
  puts "P#{pn} sieve time is #{Time.monotonic - tp} secs" # sieve time
  puts "Primes count upto #{numb} is #{primes.size}"  # prime count upto input numb
  primes                                              # return array of prime values
end

num = 1 * 10 ** 2
puts "Input = #{num}"
primes = sozpn num, 5
#print primes
puts
primes = sozpn num, 7
#print primes
puts
primes = sozpn num, 11
#print primes
puts

num = 1 * 10 ** 5
puts "Input = #{num}"
primes = sozpn(num, 5)
#print primes
puts
primes = sozpn(num, 7)
#print primes
puts
primes = sozpn(num, 11)
#print primes
puts

num = 1 * 10 ** 7
puts "Input = #{num}"
primes = sozpn num, 5
#print primes
puts
primes = sozpn num, 7
#print primes
puts
primes = sozpn num, 11
#print primes
puts

num = 1 * 10 ** 9
puts "Input = #{num}"
primes = sozpn(num, 5)
#print primes
puts
primes = sozpn(num, 7)
#print primes
puts
primes = sozpn(num, 11)
#print primes
puts

num = 5u64 * 10u64 ** 9   # greater than 32-bits
puts "Input = #{num}"
primes = sozpn(num, 5)
#print primes
puts
primes = sozpn(num, 7)
#print primes
puts
primes = sozpn(num, 11)
#print primes
puts
primes = sozpn(num, 13)
#print primes
puts
Here are the outputs and times.
The max input here is ~5,000,000,000, due to the amount of system memory available.

For these size inputs, P7|P11 perform the best, but for other
much larger values, P13|P17 will perform better, as my papers show.

Code:
➜  ~ crystal -v
Crystal 1.5.0 [994c70b10] (2022-07-06)

LLVM: 10.0.0
Default target: x86_64-unknown-linux-gnu

➜  ~ crystal run --release sozpn.cr
Input = 100
P5 sieve time is 00:00:00.000008032 secs
Primes count upto 100 is 25

P7 sieve time is 00:00:00.000004261 secs
Primes count upto 100 is 25

P11 sieve time is 00:00:00.000031499 secs
Primes count upto 100 is 25

Input = 100000
P5 sieve time is 00:00:00.000179491 secs
Primes count upto 100000 is 9592

P7 sieve time is 00:00:00.000181307 secs
Primes count upto 100000 is 9592

P11 sieve time is 00:00:00.003365851 secs
Primes count upto 100000 is 9592

Input = 10000000
P5 sieve time is 00:00:00.018031710 secs
Primes count upto 10000000 is 664579

P7 sieve time is 00:00:00.011563589 secs
Primes count upto 10000000 is 664579

P11 sieve time is 00:00:00.034712764 secs
Primes count upto 10000000 is 664579

Input = 1000000000
P5 sieve time is 00:00:02.974991783 secs
Primes count upto 1000000000 is 50847534

P7 sieve time is 00:00:02.536751905 secs
Primes count upto 1000000000 is 50847534

P11 sieve time is 00:00:01.980194110 secs
Primes count upto 1000000000 is 50847534

Input = 5000000000
P5 sieve time is 00:00:18.722788382 secs
Primes count upto 5000000000 is 234954223

P7 sieve time is 00:00:19.184386190 secs
Primes count upto 5000000000 is 234954223

P11 sieve time is 00:00:12.749896171 secs
Primes count upto 5000000000 is 234954223

P13 sieve time is 00:00:51.795914464 secs
Primes count upto 5000000000 is 234954223
jzakiya is offline   Reply With Quote
Old 2022-07-13, 21:59   #87
jzakiya
 
Jul 2014

748 Posts
Default

If 10 or more people are interested, I will do a Jitsi video conference to explain everything in my papers,
and answer any questions with regard to the math, algorithms, and software, etc. It will have to be in August at the earliest.

Just send me an email (it's at the top of all my papers) and we can figure out what are the best dates|times, or have multiple sessions.

Also, if people have specific issues or areas they want more clarity on, include them in your emails too.
But please, do your homework, and read my papers, and watch my video, and run the software first.
If you're not really interested in understanding what I've done, and won't put in the work to do so, don't respond.

This is a golden opportunity for all the doubters (you know who you are ) to raise your (earnest) questions, so I can address them live.
jzakiya is offline   Reply With Quote
Old 2022-07-13, 22:06   #88
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

22×3×7×67 Posts
Default

All items a poster names after himself are guaranteed work of a crank.

You fail this basic filter for legitimacy.
VBCurtis is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Twin Prime Constellations robert44444uk Prime Gap Searches 45 2022-02-24 18:28
How do you efficiently sieve for prime 3/4-tuples? Puzzle-Peter Software 156 2019-06-03 20:19
find very easy twin prime in the infamy twin primes hal1se Miscellaneous Math 13 2018-11-05 16:34
Highest Prime is also a twin prime... NOT hydeer Lone Mersenne Hunters 9 2018-04-03 22:54
Twin Prime Days, Prime Day Clusters cuBerBruce Puzzles 3 2014-12-01 18:15

All times are UTC. The time now is 15:18.


Sun Jan 29 15:18:33 UTC 2023 up 164 days, 12:47, 0 users, load averages: 0.77, 0.79, 0.87

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2023, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔