carmichael_from_combinations.sf

#!/usr/bin/ruby

# Generate 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{.inc}.grep{.is_prime && _>2}.grep { |p| (n%p) != 0 }
}

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
2160, 5040, 7560, 9600, 10080, 12096, 13464, 15120, 15840, 16560, 16800, 17640, 18000, 18480, 19656, 20160, 21420, 25200, 27720, 30240, 31680, 32400, 33660, 40320, 41580, 42840, 43680, 50400, 51840, 54432, 55440, 57960, 59616, 60480, 66528, 71280, 74880, 75600, 80640, 81900, 83160, 86400, 90720, 91080, 92400, 97440, 99792, 109200, 110160, 110880, 113400, 115500, 117936, 120960, 128520, 131040, 133056, 134400, 134640, 138600, 142560, 143640, 146880, 151200, 159120, 163800, 166320, 171360, 178020, 181440, 183600, 183744, 184800, 185640, 189000, 190080, 191520, 193200, 194040, 196560, 198000, 205632, 211200, 218400, 231840, 241920, 257040, 262080, 277200, 285600, 287280, 289800, 301392, 302400, 308448, 308880, 313200, 327600, 332640, 342720, 343200, 347760, 349440, 351120, 360360, 378000, 379440, 393120, 411840, 423360, 428400, 432000, 438480, 443520, 447120, 464100, 477360, 498960, 505440, 510048, 514080, 524160, 526680, 529200, 533520, 540540, 551760, 554400, 584640, 600600, 601920, 613200, 665280, 673200, 698544, 699300, 711360, 720720, 745920, 746640, 786240, 811440, 831600, 856800, 876960, 926640, 950400, 966000, 982800, 1029600, 1045440, 1060290, 1076400, 1081080, 1096200, 1108800, 1130220, 1164240, 1170960, 1179360, 1184040, 1201200, 1203840, 1211760, 1217520, 1229760, 1256640, 1275120, 1285200, 1319472, 1363824, 1413720, 1440720, 1441440, 1474200, 1493280, 1506960, 1542240, 1570800, 1580040, 1605240, 1635480, 1663200, 1675800, 1685376, 1702260, 1801800, 1808352, 1814400, 1867320, 1970640, 1995840, 2032800, 2048592, 2091600, 2106720, 2131920, 2138400, 2233440, 2343600, 2358720, 2368080, 2373840, 2447280, 2494800, 2537640, 2594592, 2620800, 2630880, 2649024, 2784600, 2812320, 2827440, 2893968, 2903040, 2937600, 2943360, 2949408, 3013920, 3072960, 3104640, 3124800, 3157056, 3182400, 3341520, 3534300, 3603600, 3669120, 3825360, 3869880, 3880800, 3908520, 4118400, 4173120, 4324320, 4371840, 4390848, 4455360, 4694400, 4726260, 4870800, 4900896, 4989600, 5261760, 5328960, 5359200, 5569200, 5597280, 5601960, 5700240, 5765760, 5969040, 5987520, 5992560, 6408000, 6462720, 6514200, 6630624, 6652800, 6966960, 7005240, 7182000, 7207200, 7286400, 7412580, 7454160, 7539840, 7592400, 7882560, 7927920, 8143200, 8353800, 8898120, 9172800, 9317700, 9729720, 9730800, 9815400, 10256400, 10417680, 10523520, 10785600, 10810800, 10838520, 10925460, 11043648, 11330880, 11370240, 11642400, 11823840, 11848320, 12012000, 12108096, 12113640, 12252240, 12558000, 13242240, 13431600, 13780800, 13843440, 14908320, 14922600, 14994720, 15301440, 16336320, 16470720, 17664768, 18125100, 18673200, 18944640, 19773600, 20123712, 21381360, 21495600, 22120560, 23474880, 24053400, 24116400, 24987960, 25618320, 25870320, 28501200, 31000320, 33486600, 34285680, 34344000, 34871760, 35259840, 37857600, 38069460, 38089656, 39944016, 40880400, 47567520, 52164000, 53105976, 55677600, 68886720, 69975360, 71910720, 72586800, 74113200, 78140160, 78397200, 79944480, 94731840, 98346528, 99459360, 100442160, 114465960, 116772480, 145918080, 149716800, 152565504, 166795200, 172138176, 190358784, 194535000, 199825920, 201152160, 206187696, 208731600, 242424000, 299871000, 304045280, 323734320, 349669320, 583568160, 589404816, 622843200, 634364640, 737919000, 789158160, 1016688960, 1078751520, 1201302960, 1265793408, 1586759328, 1595669400, 1966386240, 2307097800, 3022002000, 3234193680, 3283434000, 4458914460, 10449100200, 12948959520, 18005635008, 22276757160, 26607829248, 78417046080

].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 > 18446744073709551616) {
                say v if v.is_carmichael
            }

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