Week 6: if you have read this and you have no questions, please close this issue.

[BertLisser]

.
This is good-looking, clear, concise report, you did he bonus, and
used the right definition of Carmichael numbers (++).

A few remarks:

I don't believe your remark. Factorisation of large numbers is very expensive.
I bet that on the large run compositesAlternative wins.

composites :: [Integer]
composites = composite_sieve [2..]
-- Get all composite numbers from an inputted integer list.
composite_sieve :: [Integer] -> [Integer]
composite_sieve xs = [i | i <- xs, head (factors i) /= i]
-- Credits to Ferry for optimalisation.

-- This function is implemented according the hints in the assignment, but the function above is much faster
compositesAlternative :: [Integer]
compositesAlternative = [x | (x,False) <- sieveComposites [(i,True) | i <- [2..]]]

sieveComposites :: [(Integer,Bool)] -> [(Integer,Bool)]
sieveComposites ((i,False):ibs) = (i,False) : sieveComposites ibs
sieveComposites ((i,True):ibs) = (i,True) : sieveComposites (map (\ (n,b) -> (n, b && rem n i /= 0)) ibs)

This is very good observatiion.

- Results of testing:
-- testF 1 carmichael -> seems to return all CarMicheal numbers
-- testF 2 carmichael -> seems to return all CarMicheal numbers
-- testF 5 carmichael -> does not return the first CarMicheal number (294409) as a number that fools Fermat's little theory

-- So if 'k' gets higher, not all CarMicheal numbers are returned as numbers that fool Fermat's little theory. This is because
-- Fermat's little theory states that prime numbers have the property a^p = a (mod p). CarMicheal numbers have the property
-- a^p = a (mod p) too, however 'a' and 'p' have to be relatively prime (i.e. gcd has to be 1). So if we find an 'a' that is
-- not relatively prime with 'p', is does not pass Fermat's prime check. The higher 'k' gets, the higher the probability we
-- find such an 'a'.

This routine doesn't terminate. Why not testing from which primes
are connected to Mersenne Primes (see Answers Week 6).

-- Precondition: input is a prime number
mersennePrimes :: Integer -> IO ()
mersennePrimes p = do
  print(show p)
  let p1 = (2^p - 1) in
    do
      r <- primeMR 5 p1
      when r $ mersennePrimes p1