Posts Tagged ‘e’

Programming Praxis – Billboard Challenge, Part 2

June 26, 2012

In today’s Programming Praxis challenge, our goal is to solve the second part of the billboard test, which is to find the fifth group of ten digits of e that sum up to 49. Reusing our definition of stream_e from the previous exercise, the solution becomes a simple one-liner:

main :: IO ()
main = print $ [x | x <- map (take 10) $ tails stream_e, sum x == 49] !! 4

Programming Praxis – Billboard Challenge, Part 1

June 22, 2012

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

Programming Praxis – Digits Of E

June 19, 2012

In today’s Programming Praxis exercise, our goal is to implement two algorithms to calculate the digits of e using a spigot algorithm: one bounded and one unbounded version. My solution for the unbounded version is already posted in the exercise itself, so I’ll only cover the bounded version here. Let’s get started, shall we?

A quick import:

import Data.List

The main trick used for the whole carry and modulo stuff is the use of mapAccumR; it allows us to produce a list of the modulos while also producing the resulting digit. Other than that, the implementation is straightforward: call the function n-1 times with an initial argument of n+1 ones and tack a 2 on the front.

spigot_e :: Int -> [Int]
spigot_e n = 2 : take (n - 1) (f $ replicate (n + 1) 1) where
    f = (\(d,xs) -> d : f xs) .
        mapAccumR (\a (i,x) -> divMod (10*x+a) i) 0 . zip [2..]

A test to see if everything is working properly:

main :: IO ()
main = print $ spigot_e 30

Programming Praxis – E

August 13, 2010

In today’s Programming Praxis exercise our task is to determine how many random numbers between 0 and 1 we have to sum on average to exceed 1. Let’s get started, shall we?

Some imports:

import Control.Monad
import System.Random

First, the algorithm itself, which counts the number of required additions.

f :: Float -> IO Int
f s = if s > 1 then return 0 else fmap succ . f . (s +) =<< randomRIO (0, 1)

To get an average, we run the algorithm a number of times and take the average.

test :: Int -> IO Float
test n = fmap ((/ toEnum n) . toEnum . sum) $ replicateM n (f 0)

As usual, a test to see if everything works:

main :: IO ()
main = print =<< test 100000

Three sequential test produce 2.72085, 2.71691 and 2.71838. Certainly in the right ballpark of the expected result of e, with the last one accurate to three places behind the comma, so it looks like everything’s okay.