123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117 |
- #!/usr/bin/julia
- # Daniel "Trizen" Șuteu
- # Date: 06 September 2022
- # Edit: 23 February 2023
- # 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 (in range):
- # 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)));
- using Primes
- const BIG = false # true to use big integers
- function big_prod(arr)
- BIG || return prod(arr)
- r = big(1)
- for n in (arr)
- r *= n
- end
- return r
- end
- function carmichael_numbers_in_range(A, B, k)
- A = max(A, fld(big_prod(primes(prime(k+1))), 2))
- # Largest possible prime factor of Carmichael numbers <= B
- # Proof: By the Chinese Remainder Theorem, if n is a Carmichael number, then:
- # n == p (mod p*(p-1)), where p is a prime factor of n
- # therefore `n = p + j*p*(p-1)`, for some j >= 2. (j=1 gives p^2)
- # With j=2, we have `2*p^2 - p <= n`, hence `p <= (1 + sqrt(8*n + 1))/4`.
- max_p = (1 + isqrt(8*B + 1))>>2
- terms = []
- F = function(m, L, lo, k)
- hi = round(Int64, fld(B, m)^(1/k))
- if (lo > hi)
- return nothing
- end
- if (k == 1)
- hi = min(hi, max_p)
- lo = round(Int64, max(lo, cld(A, m)))
- lo > hi && return nothing
- t = invmod(m, L)
- t > hi && return nothing
- if (t < lo)
- t += L*cld(lo - t, L)
- end
- t > hi && return nothing
- for p in t:L:hi
- if ((m*p - 1) % (p-1) == 0 && isprime(p))
- push!(terms, m*p)
- end
- end
- return nothing
- end
- for p in primes(lo, hi)
- if (gcd(m, p-1) == 1)
- F(m*p, lcm(L, p-1), p+1, k-1)
- end
- end
- end
- F((BIG ? big(1) : 1), (BIG ? big(1) : 1), 3, k)
- return sort(terms)
- end
- # Generate all the Carmichael numbers in range [A,B]
- function carmichael(A, B)
- k = 3
- terms = []
- while true
- # Stop when the lower-bound (`primorial(prime(k+1))/2`) is greater than the upper-limit
- if (big_prod(primes(prime(k+1)))/2 > B)
- break
- end
- append!(terms, carmichael_numbers_in_range(A, B, k))
- k += 1
- end
- return sort(terms)
- end
- println("=> Carmichael numbers <= 10^6:")
- println(carmichael(1, 10^6));
- # Generate all the 6-Carmichael numbers in the range [100, 10^10]
- k = 6
- from = 100
- upto = 10^10
- arr = carmichael_numbers_in_range(from, upto, k)
- println("\n=> Carmichael numbers with $k prime factors in range [$from, $upto]:")
- println(arr)
|