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:

> 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:
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 piDigits

This 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 ;)