Another Haskell exercise
Posted on April 15, 2012
A few days ago there was a link on reddit: some company asked applicants to send resume to an address that is the first seven-digit Prime number taken from the consecutive digits of Pi which is also a palindrome. I cannot find the link anymore, but I wrote this just for fun:
> module Main where
Generate digits of Pi as an infinite list.
Use Unbounded Spigot Algorithm from this article:
http://www.cs.ox.ac.uk/jeremy.gibbons/publications/spigot.pdf
> piDigits :: [Integer]
> piDigits = g(1,0,1,1,3,3) where
> g(q,r,t,k,n,l) = if 4*q+r-t<n*t
> then n : g(10*q,10*(r-n*t),t,k,div(10*(3*q+r))t-10*n,l)
> else g(q*k,(2*q+r)*l,t*l,k+1,div(q*(7*k+2)+r*l)(t*l),l+2)
Find palindromes of specified length in an infinite list of digits.
Result is returned as an infinite list of Integers, each element
a palindrome when represented as digital characters. E.g.:
"findPali 3 [1,2,3,2,1,7,9,7]" returns "[232,797]".
> findPali :: Int -> [Integer] -> [Integer]
> findPali n x
> | length pref < n = [] -- Not necessary for infinite lists
> | pref == reverse pref = toint pref:findPali n (tail x)
> | otherwise = findPali n (tail x)
> where
> pref = take n x
> toint = foldl (\acc x -> acc*10+x) 0
Check if an Integer is a Prime number. Function copied from here:
http://stackoverflow.com/questions/4541415/haskell-prime-test
It is a "naive" implementaion but fast enough for our case, and
readily understandable.
> isPrime :: Integer -> Bool
> isPrime x = not $ any divisible $ takeWhile notTooBig [2..]
> where
> divisible y = x `mod` y == 0
> notTooBig y = y*y <= x
Find and return the first element in a list based on predicate.
Our list is infinite so we don't need the result to be of "Maybe"
type like the "canonical" implementation in Data.List.
> find' :: (a -> Bool) -> [a] -> a
> find' p (x:xs)
> | p x = x
> | otherwise = find' p xs
Print the first 7-digit palindrome of consecutive digits of Pi
that is a Prime number.
> main = putStrLn $ show $ find' isPrime $ findPali 7 piDigitsThis is not the fastest thing you can invent (prime check is very simplistic), but it gives the result in under a minute on my system.
UPDATE 2012-04-16: Found the link. Not writing it here ;)