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 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)

We used a simple primality checker based on trial division and define-generator from a previous exercise. You can run the program at

The web site 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 […]

  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 701 other followers

%d bloggers like this: