carmichael_generation_erdos_method.sf

#!/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