sidef-scripts/Math/carmichael_numbers_upto.sf

#!/usr/bin/ruby

# Generate all the Carmichael numbers, up to a given bound.

func carmichael_upto(n) {
    var C = Set()

    3 .. idiv(1+isqrt(8*n + 1), 4) -> each_prime {|p|

        var t = p*(p-1)
        var c = (p + 2*t)

        loop {
            C << c if c.is_carmichael
            c += t
            break if (c > n)
        }
    }

    return C.sort
}

var C = carmichael_upto(1e6)

say C
say C.len

__END__
[561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, 29341, 41041, 46657, 52633, 62745, 63973, 75361, 101101, 115921, 126217, 162401, 172081, 188461, 252601, 278545, 294409, 314821, 334153, 340561, 399001, 410041, 449065, 488881, 512461, 530881, 552721, 656601, 658801, 670033, 748657, 825265, 838201, 852841, 997633]
43