## Billboard Challenge, Part 1

### June 22, 2012

There are several ways to solve this problem. If you have access to a DNS server, you could extract all the 10-digit.com names, test each for primality, and look at each one until you find the likely solution. Or you could find the digits of e at any of several places on the web and test each successive 10-digits until you find a prime.

But since we just happen to have at hand an unbounded spigot generator for the digits of e, we can use it to solve the problem:

(define (billboard1)
(let loop ((i 0) (n (e-spigot)))
(if (and (< #e1e9 n) (prime? n)) (values i n)
(loop (+ i 1) (+ (* 10 (modulo n #e1e9)) (e-spigot))))))

The first 10-digit prime occurs early in the digits of e:

> (billboard1)
108
7427466391

We used a simple primality checker based on trial division and define-generator from a previous exercise. You can run the program at http://programmingpraxis.codepad.org/VDTr8wO7.

The web site 7427466391.com no longer exists. If you went to the web site back in 2004, when it was active, it gave you a second problem to solve, which we will see in the next exercise.

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 […]

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)

else:
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]