123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990 |
- #!/usr/bin/ruby
- # Try to generate a Fermat pseudoprime to base 2, that is also a Fibonacci pseudoprime and has the Kronecker symbol (5/n) = -1.
- func lucas_znorder(n, P=1, Q=-1) {
- var e = kronecker(P*P - 4*Q, n)
- n-e -> divisors.first {|d|
- lucasUmod(P, Q, d, n) == 0
- }
- }
- func squarefree_fermat_pseudoprimes_in_range(a, b, k, base, callback) {
- a = max(k.pn_primorial, a)
- func (m, lambda, lambda2, p, k) {
- var y = idiv(b,m).iroot(k)
- return nil if (p > y)
- if (k == 1) {
- var x = max(p, idiv_ceil(a, m))
- say "# Prime: #{p} (#{x}, #{y}) -- #{[lambda, lambda2]} -- #{m}";
- each_prime(x, y, {|p|
- kronecker(5, p) == -1 || next
- with (m*p - 1) {|t|
- if ((lambda `divides` t) && (kronecker(5, t+1) == -1) && (znorder(base, p) `divides` t)) {
- say "# Fermat: #{t+1}"
- with(m*p + 1) {|w|
- if ((lambda2 `divides` w) && (lucas_znorder(p) `divides` w)) {
- die "Found special term: #{t+1}"
- callback(t+1)
- }
- }
- }
- }
- })
- return nil
- }
- for(var r; p <= y; p = r) {
- r = p.next_prime
- p.divides(base) && next
- kronecker(5,p) == -1 || next
- p.inc.is_smooth(43) || next
- p.dec.is_smooth(43) || next
- var L = lcm(lambda, znorder(base, p))
- m.is_coprime(L) || next
- var L2 = lcm(lambda2, lucas_znorder(p))
- m.is_coprime(L2) || next
- var t = m*p
- var u = idiv_ceil(a, t)
- var v = idiv(b, t)
- if (u <= v) {
- __FUNC__(t, L, L2, r, k-1)
- }
- }
- }(1, 1, 1, 2, k)
- return callback
- }
- var k = 11
- var base = 2
- var from = 2**64
- var upto = 2*from
- loop {
- say "# [#{k}] Sieving: #{[from, upto]}"
- squarefree_fermat_pseudoprimes_in_range(from, upto, k, base, { .say })
- from = upto+1
- upto = 2*from
- }
|