In today’s Programming Praxis exercise, our goal is to solve the problem posed to potential employees by a tech firm a couple of years ago: find the first 10-digit prime in the digits of e. Let’s get started, shall we?
A quick import:
First we reuse the unbounded spigot algorithm for calculating e from the last exercise;
stream :: Integral a => (a, a) -> (a, a, a) -> [(a, a, a)] -> [a] stream (lo, hi) z ~(x:xs) = if lbound == approx z hi then lbound : stream (lo, hi) (mul (10, -10*lbound, 1) z) (x:xs) else stream (lo, hi) (mul z x) xs where lbound = approx z lo approx (a,b,c) n = div (a*n + b) c mul (a,b,c) (d,e,f) = (a*d, a*e + b*f, c*f) streamDigits :: (Num a, Integral a, Enum a) => (a -> (a, a, a)) -> (a, a) -> [a] streamDigits f range = stream range (1,0,1) [(n, a*d, d) | (n,d,a) <- map f [1..]] stream_e :: [Integer] stream_e = streamDigits (\k -> (1, k, 1)) (1, 2)
Next we need a function to test if a number is prime. In the interest of simplicity we just use trial division. To speed things up, we use the three simplest optimizations: only testing odd numbers, only testing up to the square root of the tested number, and only testing with primes. The list of all primes is defined at root level so Haskell memoizes it.
primes :: [Integer] primes = 2 : filter prime [3,5..] prime :: Integer -> Bool prime n = all ((> 0) . mod n) $ takeWhile (\p -> p * p <= n) primes
With those two building blocks out of the way, the rest is trivial: take all groups of 10 consecutive digits, convert them to numbers and find the first prime.
main :: IO () main = print $ find prime . map (foldl1 ((+) . (10 *)) . take 10) $ tails stream_e