Billboard Challenge, Part 1

June 22, 2012

Several years ago, a billboard with this text appeared in the tech centers of Silicon Valley and Route 128:

{ first 10-digit prime found in consecutive digits of e }.com

Your task is to write a program that finds the first 10-digit prime found in consecutive digits of e. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

About these ads

Pages: 1 2

5 Responses to “Billboard Challenge, Part 1”

  1. […] today’s Programming Praxis exercise, our goal is to solve the problem posed to potential employees by a […]

  2. My Haskell solution (see for a version with comments):

    import Data.List
    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)
    primes :: [Integer]
    primes = 2 : filter prime [3,5..]
    prime :: Integer -> Bool
    prime n = all ((> 0) . mod n) $ takeWhile (\p -> p * p <= n) primes
    main :: IO ()
    main = print $ find prime . map (foldl1 ((+) . (10 *)) . take 10) $ tails stream_e
  3. Mike said

    Python solution

    At first I didn’t check to make sure ‘number’ had 10 digits, and it found a ‘0’ followed by a 9-digit prime.

    e_digits() and is_prime() come from previous exercises

    from digits_of_e import e_digits
    from isprime import is_prime
    from itertools import islice
    digit = e_digits()
    number = reduce(lambda t,d: 10*t + d, islice(digit, 10))
    while number < 1000000000 or not is_prime(number):
        number = number%1000000000*10 + next(digit)
        print number
  4. […] recent Programming Praxis problem resurrected the famous Google billboard puzzle. Back in July of 2004, Google put up billboards all over the country […]

  5. I’m falling in love with Python. This takes a while to run because it doesn’t evaluate lazily, but that’s a consequence of my structure phobia.

    from euler import prime
    l = "718281828459045235360287471352662497757247093699959574966967627724076630353547594571382178525166427427466391932003059921817413596629043572900334295260595630738132328627943490763233829880753195251019011573834187930702154089149934884167509244761460668082264800168477411853742345442437107539077744992069551702761838606261331384583000752044933826560297606737113200709328709127443747047230696977209310141692836819025515108657463772111252389784425056953696770785449969967946864454905987931636889230098793127736178215424999229576351482208269895193668033182528869398496465105820939239829488793320362509443117301238197068416140397019837679320683282376464804295311802328782509819455815301756717361332069811250996181881593041690351598888519345807273866738589422879228499892086805825749279610484198444363463244968487560233624827041978623209002160990235304369941849146314093431738143640546253152096183690888707016768396424378140592714563549061303107208510383750510115747704171898610687396965521267154688957035035402123407849819334321068170121005627880235193033224745015853904730419957777093503660416997329725088687696640355570716226844716256079882651787134195124665201030592123667719432527867539855894489697096409754591856956380236370162112047742722836489613422516445078182442352948636372141740238893441247963574370263755294448337998016125492278509257782562092622648326277933386566481627725164019105900491644998289315056604725802778631864155195653244258698294695930801915298721172556347546396447910145904090586298496791287406870504895858671747985466775757320568128845920541334053922000113786300945560688166740016984205580403363795"
    print list(int(l[i:i+10]) for i in range(0,len(l)-10) if prime(int(l[i:i+10])))[0]

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Get every new post delivered to your Inbox.

Join 644 other followers

%d bloggers like this: