Sequence of primorial primes: Difference between revisions
Content added Content deleted
Line 2,755: | Line 2,755: | ||
<lang Ruby> |
<lang Ruby> |
||
# Sequence of primorial primes |
# Sequence of primorial primes |
||
require 'prime' # for creating prime_array |
|||
# I found that using only standard Class Prime.prime?(), indeed produce very short-line of code but stacked on Primorial Prime |
|||
require 'openssl' # for using fast Miller–Rabin primality test (just need 10.14 seconds to complete) |
|||
# sequence 8 with JRuby or standard Ruby. So here I adopt RUby code for Miller–Rabin_primality_test from |
|||
⚫ | |||
# https://rosettacode.org/wiki/Miller%E2%80%93Rabin_primality_test#This_is_a_correct_M-R_test_implementation_for_using_bases_.3E_input._3 |
|||
⚫ | |||
# From output, using Ruby-MR test took time 34.011 sec to finish which by Python code (in this page) took 289.50 sec on same computer. |
|||
require 'prime' |
|||
require 'openssl' # for fast n.to_bn.mod_exp(exponent, modulus) method |
|||
⚫ | |||
start = Time.now |
start = Time.now |
||
prime_array = Prime.first (500) |
prime_array = Prime.first (500) |
||
# Begin code for Miller–Rabin_primality_test .......................... |
|||
class Integer |
|||
# Returns true if +self+ is a prime number, else returns false. |
|||
def primemr? |
|||
primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47] |
|||
return primes.include? self if self <= primes.last |
|||
modp47 = 614_889_782_588_491_410 # => primes.reduce(:*), largest < 2^64 |
|||
return false if self.gcd(modp47) != 1 # eliminates 86.2% of all integers |
|||
# Choose witness bases for input; wits = [range, [wit_bases]] or nil |
|||
wits = WITNESS_RANGES.find {|range, wits| range > self} |
|||
witnesses = wits && wits[1] || primes |
|||
miller_rabin_test(witnesses) |
|||
end |
|||
⚫ | |||
private |
|||
# Returns true if +self+ passes Miller-Rabin Test with witness bases +b+ |
|||
def miller_rabin_test(witnesses) # use witness list to test with |
|||
neg_one_mod = n = d = self - 1 # these are even as 'self' always odd |
|||
d >>= 4 while (d & 0xf) == 0 # suck out factors of 2 |
|||
(d >>= (d & 3)^2; d >>= (d & 1)^1) if d.even? # 4 bits at a time |
|||
witnesses.each do |b| # do M-R test with each witness base |
|||
next if (b % self) == 0 # **skip base if a multiple of input** |
|||
s = d |
|||
y = b.to_bn.mod_exp(d, self) # y = (b**d) mod self |
|||
until s == n || y == 1 || y == neg_one_mod |
|||
y = y.mod_exp(2, self) # y = (y**2) mod self |
|||
s <<= 1 |
|||
end |
|||
return false unless y == neg_one_mod || s.odd? |
|||
end |
|||
true |
|||
end |
|||
# Best known deterministic witnesses for given range and set of bases |
|||
# https://miller-rabin.appspot.com/ |
|||
# https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test |
|||
WITNESS_RANGES = { |
|||
341_531 => [9345883071009581737], |
|||
1_050_535_501 => [336781006125, 9639812373923155], |
|||
350_269_456_337 => [4230279247111683200, 14694767155120705706, 16641139526367750375], |
|||
55_245_642_489_451 => [2, 141889084524735, 1199124725622454117, 11096072698276303650], |
|||
7_999_252_175_582_851 => [2, 4130806001517, 149795463772692060, 186635894390467037, |
|||
3967304179347715805], |
|||
585_226_005_592_931_977 => [2, 123635709730000, 9233062284813009, 43835965440333360, |
|||
761179012939631437, 1263739024124850375], |
|||
18_446_744_073_709_551_615 => [2, 325, 9375, 28178, 450775, 9780504, 1795265022], |
|||
318_665_857_834_031_151_167_461 => [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37], |
|||
3_317_044_064_679_887_385_961_981 => [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41] |
|||
} |
|||
end |
|||
# End code for Miller–Rabin_primality_test .......................... |
|||
until urutan > 20 |
until urutan > 20 |
||
primorial_number *= prime_array[i-1] |
primorial_number *= prime_array[i-1] |
||
⚫ | |||
⚫ | |||
puts "#{Time.now - start} \tPrimorial prime #{urutan}: #{i}" |
puts "#{Time.now - start} \tPrimorial prime #{urutan}: #{i}" |
||
urutan += 1 |
urutan += 1 |
||
end |
end |
||
i += 1 |
i += 1 |
||
end |
end |
||
Line 2,838: | Line 2,777: | ||
Output: |
Output: |
||
<pre> |
<pre> |
||
0. |
0.000501 Primorial prime 1: 1 |
||
0. |
0.00094 Primorial prime 2: 2 |
||
0. |
0.001474 Primorial prime 3: 3 |
||
0. |
0.001969 Primorial prime 4: 4 |
||
0. |
0.002439 Primorial prime 5: 5 |
||
0. |
0.003557 Primorial prime 6: 6 |
||
0. |
0.004167 Primorial prime 7: 11 |
||
0. |
0.004849 Primorial prime 8: 13 |
||
0. |
0.006287 Primorial prime 9: 24 |
||
0. |
0.020018 Primorial prime 10: 66 |
||
0. |
0.022049 Primorial prime 11: 68 |
||
0. |
0.026954 Primorial prime 12: 75 |
||
0.213867 Primorial prime 13: 167 |
|||
0.243797 Primorial prime 14: 171 |
|||
0.256598 Primorial prime 15: 172 |
|||
1.469281 Primorial prime 16: 287 |
|||
2.012719 Primorial prime 17: 310 |
|||
3.598149 Primorial prime 18: 352 |
|||
5.252034 Primorial prime 19: 384 |
|||
10.147519 Primorial prime 20: 457 |
|||
</pre> |
</pre> |
||