chernick-carmichael_numbers.sf

#!/usr/bin/ruby

# Daniel "Trizen" Șuteu
# Date: 30 March 2019
# https://github.com/trizen

# Generate the extended Chernick-Carmichael numbers below a given limit.

# See also:
#   https://oeis.org/A317126
#   https://oeis.org/A317136

# Generate the factors of a Chernick number, given m and k,
# where k is the number of distinct prime factors.
func chernick_carmichael_factors (n, m) {
    [6*m + 1, 12*m + 1, {|k| 2**k * 9*m + 1 }.map(1 .. n-2)...]
}

func is_chernick_carmichael (n, m) {
    (n==2) ? (is_prime(6*m + 1) && is_prime(12*m + 1))
           : (is_prime(2**(n-2) * 9*m + 1) && __FUNC__(n-1, m))
}

# Generate the Chernick-Carmichael below a given limit
func chernick_carmichael_numbers(limit) {

    var terms = []

    for n in (3 .. Inf) {

        # We can stop the search when:
        #   (6*m + 1) * (12*m + 1) * Product_{j=1..n-2} (9 * 2^j * m + 1)
        # is greater than the limit, for m=1.
        if (chernick_carmichael_factors(n, 1).prod > limit) {
            break
        }

        # `m` must be divisible by 2^(n-4), for n > 4
        var multiplier = (n>4 ? (2**(n-4)) : 1)

        # Optimization for n > 5
        multiplier *= 5 if (n > 5)

        for k in (1 .. Inf) {

            var m = (k * multiplier)

            # All factors must be prime
            #is_chernick_carmichael(n, m) || next

            # Generate the n-distinct factors
            var f = chernick_carmichael_factors(n, m)

            # All factors must be prime
            f.all_prime || next

            # The product of these primes is Carmichael number
            var c = f.prod

            # Stop the loop if the limit has been exceeded
            break if (c > limit)

            # Sanity check (optional)
            assert(c.is_carmichael, "#{c} is not a Carmichael number")

            # Is a Chernick-Carmichael number (we store it)
            terms << c
        }
    }

    # Return the sorted list
    return terms.sort
}

say chernick_carmichael_numbers(10**11)

__END__
[1729, 63973, 294409, 56052361, 118901521, 172947529, 216821881, 228842209, 1299963601, 2301745249, 9624742921, 11346205609, 13079177569, 21515221081, 27278026129, 65700513721, 71171308081]