123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778 |
- #!/usr/bin/ruby
- # Erdos construction method for Carmichael numbers:
- # 1. Choose an integer L with many prime factors.
- # 2. Let P be the set of primes d+1, where d|L and d+1 does not divide L.
- # 3. Find a subset S of P such that prod(S) == 1 (mod L). Then prod(S) is a Carmichael number.
- # Alternatively:
- # 3. Find a subset S of P such that prod(S) == prod(P) (mod L). Then prod(P) / prod(S) is a Carmichael number.
- func lambda_primes(L) {
- L.divisors.map { .inc }.grep { .is_odd && .is_coprime(L) && .is_prime }
- }
- func method_1(L, callback) { # small numbers first
- var P = lambda_primes(L)
- for k in (3..P.len) {
- P.combinations(k, {|*S|
- if (S.prodmod(L) == 1) {
- callback(S.prod)
- }
- })
- }
- return nil
- }
- func method_2(L, callback) { # large numbers first
- var P = lambda_primes(L)
- var T = P.prod
- var B = T%L
- for k in (1 .. (P.len-3)) {
- P.combinations(k, {|*S|
- if (S.prodmod(L) == B) {
- var c = idiv(T, S.prod)
- callback(c) if (c > 1)
- }
- })
- }
- return nil
- }
- method_1(720, {|c| say c })
- method_2(720, {|c| say c })
- __END__
- 15841
- 115921
- 488881
- 41041
- 172081
- 5310721
- 12262321
- 16778881
- 18162001
- 76595761
- 609865201
- 133205761
- 561777121
- 1836304561
- 832060801
- 1932608161
- 20064165121
- 84127131361
- 354725143201
- 1487328704641
- 3305455474321
- 1945024664401
- 2110112460001
- 8879057210881
- 65121765643441
- 30614445878401
|