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.

Posted by programmingpraxis

Filed in Exercises

5 Comments »

5 Responses to “Billboard Challenge, Part 1”

Programming Praxis – Billboard Challenge, Part 1 « Bonsai Code said
June 22, 2012 at 10:19 AM
[…] today’s Programming Praxis exercise, our goal is to solve the problem posed to potential employees by a […]

Remco Niemeijer said

June 22, 2012 at 10:20 AM

My Haskell solution (see http://bonsaicode.wordpress.com/2012/06/22/programming-praxis-billboard-challenge-part-1/ 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

Mike said

June 24, 2012 at 3:43 AM

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)
    
else:
    print number

The Google Billboard Puzzle | Irreal said
July 2, 2012 at 11:11 AM
[…] recent Programming Praxis problem resurrected the famous Google billboard puzzle. Back in July of 2004, Google put up billboards all over the country […]

Alex Malone said

July 11, 2012 at 3:40 AM

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]

Programming Praxis