lucas-carmichael_from_combinations.sf

#!/usr/bin/ruby

# Generate Lucas-Carmichael numbers k, using primes p such that p+1 divides n, where n are various numbers with many divisors.

func a(n) {
    n.divisors.map{.dec}.grep{.is_prime}
}

var arr = [

4, 6, 8, 10, 12, 24, 30, 36, 48, 60, 72, 96, 108, 120, 144, 168, 180, 240, 360, 420, 480, 504, 540, 720, 840, 1008, 1080, 1200, 1260, 1440, 1620, 1680, 2016, 2160, 2520, 3360, 3780, 4200, 4320, 5040, 6480, 7560, 8400, 9240, 10080, 12600, 15120, 20160, 25200, 27720, 30240, 42840, 45360, 46200, 55440, 60480, 75600, 83160, 85680, 100800, 110880, 128520, 131040, 151200, 166320, 196560, 257040, 302400, 327600, 332640, 393120, 415800, 514080, 554400, 655200, 665280, 786240, 831600, 917280, 982800, 1081080, 1108800, 1179360, 1285200, 1310400, 1330560, 1441440, 1663200, 1965600, 2162160, 2751840, 2827440, 2882880, 3326400, 3341520, 3603600, 3931200, 4324320, 5654880, 6486480, 6652800, 6683040, 7207200, 8648640, 10810800, 12972960, 14137200, 14414400, 17297280, 18378360, 21621600, 25945920, 31600800, 32432400, 36756720, 41081040, 43243200, 54774720, 64864800, 68468400, 73513440, 82162080, 86486400, 109549440, 122522400, 129729600, 147026880, 164324160, 183783600, 220540320, 245044800, 294053760, 367567200, 551350800, 735134400, 1102701600, 1470268800, 2205403200, 2572970400, 2940537600, 3675672000, 4190266080, 4410806400, 5145940800, 6983776800, 10291881600, 13967553600, 20583763200, 20951330400, 25362136800, 27935107200, 41902660800, 48886437600, 55870214400, 69837768000, 83805321600, 97772875200, 139675536000, 146659312800

].uniq.sort

for n in (arr) {

    if (n.sigma0 > 1e6) {
        say "n = #{n} has too many divisors -- stopping"
        break
    }

    var primes = a(n)

    for k in (min(primes.len>>1, 20) `downto` 5) {
        var count = 0
        primes.shuffle.combinations(k, {|*list|
            var v = list.prod

            if (v > 1e12) {
                say v if v.is_lucas_carmichael
            }

            break if (++count > 1e4)
        })
    }
}