1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798 |
- #!/usr/bin/ruby
- # Daniel "Trizen" Șuteu
- # Date: 29 August 2022
- # https://github.com/trizen
- # Generate all the squarefree Fermat pseudoprimes to a given base with n prime factors in a given range [a,b]. (not in sorted order)
- # See also:
- # https://en.wikipedia.org/wiki/Almost_prime
- # https://trizenx.blogspot.com/2020/08/pseudoprimes-construction-methods-and.html
- # PARI/GP program:
- # squarefree_fermat(A, B, k, base=2) = A=max(A, vecprod(primes(k))); (f(m, l, p, k, u=0, v=0) = my(list=List()); if(k==1, forprime(p=u, v, if(base%p != 0, my(t=m*p); if((t-1)%l == 0 && (t-1)%znorder(Mod(base, p)) == 0, listput(list, t)))), forprime(q = p, sqrtnint(B\m, k), my(t = m*q); if (base%q != 0, my(L=lcm(l, znorder(Mod(base, q)))); if(gcd(L, t) == 1, my(u=ceil(A/t), v=B\t); if(u <= v, my(r=nextprime(q+1)); if(k==2 && r>u, u=r); list=concat(list, f(t, L, r, k-1, u, v))))))); list); vecsort(Vec(f(1, 1, 2, k)));
- func squarefree_fermat_pseudoprimes_in_range(a, b, k, base, callback) {
- a = max(k.pn_primorial, a)
- func (m, L, lo, k) {
- var hi = idiv(b,m).iroot(k)
- return nil if (lo > hi)
- if (k == 1) {
- lo = max(lo, idiv_ceil(a, m))
- lo > hi && return nil
- var t = m.invmod(L)
- t > hi && return nil
- t += L*idiv_ceil(lo - t, L) if (t < lo)
- t > hi && return nil
- for p in (range(t, hi, L)) {
- p.is_prime || next
- with (m*p) {|n|
- if (znorder(base, p) `divides` n.dec) {
- callback(n)
- }
- }
- }
- return nil
- }
- each_prime(lo, hi, {|p|
- p.divides(base) && next
- var t = lcm(L, znorder(base, p))
- m.is_coprime(t) || next
- __FUNC__(m*p, t, p+1, k-1)
- })
- }(1, 1, 2, k)
- return callback
- }
- # High-level implementation (unoptimized):
- func squarefree_fermat_pseudoprimes_in_range_unoptimized(A, B, k, base, callback) {
- func F(m, lambda, p, k) {
- if (k == 1) {
- each_prime(max(p, ceil(A/m)), floor(B/m), {|q|
- if (lcm(lambda, znorder(base, q)) `divides` (m*q - 1)) {
- callback(m*q)
- }
- })
- }
- elsif (k >= 2) {
- for q in (primes(p, (B/m)**(1/k))) {
- if (gcd(lcm(lambda, znorder(base, q)), m) == 1) {
- F(m*q, lcm(lambda, znorder(base, q)), q.next_prime, k-1)
- }
- }
- }
- }
- F(1, 1, 2, k)
- }
- # Generate all the squarefree Fermat pseudoprimes to base 2 with 5 prime factors in the range [100, 10^7]
- var k = 5
- var base = 2
- var from = 100
- var upto = 1e7
- say gather { squarefree_fermat_pseudoprimes_in_range(from, upto, k, base, { take(_) }) }.sort
- say gather { squarefree_fermat_pseudoprimes_in_range_unoptimized(from, upto, k, base, { take(_) }) }.sort
- __END__
- [825265, 1050985, 1275681, 2113665, 2503501, 2615977, 2882265, 3370641, 3755521, 4670029, 4698001, 4895065, 5034601, 6242685, 6973057, 7428421, 8322945, 9223401, 9224391, 9890881]
|