123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112 |
- #!/usr/bin/ruby
- # Daniel "Trizen" Șuteu
- # Date: 29 August 2022
- # https://github.com/trizen
- # Generate all the Carmichael numbers 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 (slow):
- carmichael(A, B, k) = A=max(A, vecprod(primes(k+1))\2); (f(m, l, p, k, u=0, v=0) = my(list=List()); if(k==1, forprime(p=u, v, my(t=m*p); if((t-1)%l == 0 && (t-1)%(p-1) == 0, listput(list, t))), forprime(q = p, sqrtnint(B\m, k), my(t = m*q); my(L=lcm(l, q-1)); 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, 3, k)));
- # PARI/GP program (in range) (faster):
- carmichael(A, B, k) = A=max(A, vecprod(primes(k+1))\2); my(max_p=(1+sqrtint(8*B+1))\4); (f(m, l, lo, k) = my(list=List()); my(hi=min(max_p, sqrtnint(B\m, k))); if(lo > hi, return(list)); if(k==1, lo=max(lo, ceil(A/m)); my(t=lift(1/Mod(m,l))); while(t < lo, t += l); forstep(p=t, hi, l, if(isprime(p), my(n=m*p); if((n-1)%(p-1) == 0, listput(list, n)))), forprime(p=lo, hi, if(gcd(m, p-1) == 1, list=concat(list, f(m*p, lcm(l, p-1), p+1, k-1))))); list); vecsort(Vec(f(1, 1, 3, k)));
- # PARI/GP program to generate all the Carmichael numbers <= n (fast):
- carmichael(A, B, k) = A=max(A, vecprod(primes(k+1))\2); my(max_p=(1+sqrtint(8*B+1))\4); (f(m, l, lo, k) = my(list=List()); my(hi=min(max_p, sqrtnint(B\m, k))); if(lo > hi, return(list)); if(k==1, lo=max(lo, ceil(A/m)); my(t=lift(1/Mod(m,l))); while(t < lo, t += l); forstep(p=t, hi, l, if(isprime(p), my(n=m*p); if((n-1)%(p-1) == 0, listput(list, n)))), forprime(p=lo, hi, if(gcd(m, p-1) == 1, list=concat(list, f(m*p, lcm(l, p-1), p+1, k-1))))); list); f(1, 1, 3, k);
- upto(n) = my(list=List()); for(k=3, oo, if(vecprod(primes(k+1))\2 > n, break); list=concat(list, carmichael(1, n, k))); vecsort(Vec(list));
- }
- func carmichael_numbers_in_range(A, B, k, callback) {
- A = max(pn_primorial(k+1)/2, A)
- # Largest possisble prime factor for Carmichael numbers <= B
- var max_p = ((1 + isqrt(8*B + 1))>>2)
- func (m, L, lo, k) {
- var hi = idiv(B,m).iroot(k)
- if (lo > hi) {
- return nil
- }
- if (k == 1) {
- hi = max_p if (hi > max_p)
- 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 (p.dec `divides` n.dec) {
- callback(n)
- }
- }
- }
- return nil
- }
- each_prime(lo, hi, {|p|
- m.is_coprime(p-1) || next
- __FUNC__(m*p, lcm(L, p-1), p+1, k-1)
- })
- }(1, 1, 3, k)
- return callback
- }
- # High-level implementation (unoptimized):
- func carmichael_numbers_in_range_unoptimized(A, B, k, callback) {
- func F(m, lambda, p, k) {
- if (k == 1) {
- each_prime(max(p, ceil(A/m)), min(floor((1+isqrt(8*B + 1))/4), floor(B/m)), {|q|
- if (lcm(lambda, q-1) `divides` (m*q - 1)) {
- callback(m*q)
- }
- })
- }
- elsif (k >= 2) {
- for q in (primes(p, floor((B/m)**(1/k)))) {
- if (gcd(lcm(lambda, q-1), m) == 1) {
- F(m*q, lcm(lambda, q-1), q+1, k-1)
- }
- }
- }
- }
- F(1, 1, 3, k)
- }
- # Generate all the 5-Carmichael numbers in the range [100, 2*10^7]
- var k = 5
- var from = 100
- var upto = 2e7
- say gather { carmichael_numbers_in_range(from, upto, k, { take(_) }) }.sort
- say gather { carmichael_numbers_in_range_unoptimized(from, upto, k, { take(_) }) }.sort
- __END__
- [825265, 1050985, 9890881, 10877581, 12945745, 13992265, 16778881, 18162001]
|