Skip to content

Instantly share code, notes, and snippets.

@callerobertsson
Created January 21, 2015 13:34
Show Gist options
  • Save callerobertsson/0f1ff0deacbc4d9910d5 to your computer and use it in GitHub Desktop.
Save callerobertsson/0f1ff0deacbc4d9910d5 to your computer and use it in GitHub Desktop.
Haskell: Lucas Carmichael number generator
-- Lucas Carmichael Numbers
--
-- inspired by the Youtube channel Numberphile
-- episode https://www.youtube.com/watch?v=yfr3BIk6KFc
-- "Something special about 399 (and 2015)"
--
-- by [email protected], jan 2015
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
putStrLn "Is 3235967 a LC number? "
print $ isLC 3235967
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment