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:

import Data.List

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

### Like this:

Like Loading...

*Related*

Tags: bonsai, code, digits, e, Haskell, kata, praxis, primes, programming

This entry was posted on June 22, 2012 at 12:19 pm and is filed under Programming Praxis. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

June 26, 2012 at 9:29 pm |

[...] Bonsai Code Art is the elimination of the unnecessary « Programming Praxis – Billboard Challenge, Part 1 [...]