Lucas/Carmichel Numbers

Note: this is an old blog post from my old and closed down blog but, you know, recycling is good.

One of my favorite Youtube channels are Numberphile and today I watched a short talk about Lucas-Carmichael numbers.

It look like a perfect problem to solve in Haskell so I created the following little program producing all LC numbers less than 100000.

-- Lucas Carmichael Numbers

import Data.Numbers.Primes

isAllFactors :: (Integral a) => a -> [a] -> Bool
isAllFactors n = all (\f -> mod n f == 0)

isSquareFree :: (Integral a) => a -> Bool
isSquareFree n = 
    let pfs = primeFactors n
    in
        all (\p -> mod n (p^2) /= 0) pfs

isLC :: (Integral a) => a -> Bool
isLC n = 
    let pfs = primeFactors n
        n'  = n + 1
        fs' = map (+ 1) pfs
    in
        odd n 
        && not (isPrime n)
        && isSquareFree n
        && isAllFactors n' fs'

lcNumbers :: [Integer]
lcNumbers = filter isLC [3..]

main = do
    putStrLn "Lucas Carmichael numbers less than 100 000"
    print $ takeWhile (<100000) lcNumbers

Here's a gist with the code

There are for certain better ways to solve it but I think it is a neat and clear solution.

I think they forgot to mention it the video that the number must be odd and not contain any squared prime factors. Found that out on Wikipedia.

/Calle