turingprimes.hs

-- Stolen from http://www.haskell.org/haskellwiki/Testing_primality
primes :: [Integer]
primes = 2: 3: sieve (tail primes) [5,7..]
         where
             sieve (p:ps) xs = h ++ sieve ps [x | x <- t, x `rem` p /= 0]
                  where (h,~(_:t)) = span (< p*p) xs

isPrime :: Integer -> Bool
isPrime n = n > 1 && all (\ p -> n `rem` p /= 0) (takeWhile (\ p -> p*p < n) primes)

-- Converts 42d -> 101010d
binread :: Integer -> Integer
binread 0 = 0
binread n = let (q, r) = n `divMod` 2
            in  r + 10 * binread q

turingPrimes :: [Integer]
turingPrimes = filter (isPrime.binread) primes

main = do
    let ps     = takeWhile (< (2^28)) turingPrimes
    let ps_num = zip [1..] ps
    mapM_ print $ map (\ (i, n) -> (n, binread n, i)) ps_num
    print $ length ps
    return ()