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.
[…] today’s Programming Praxis exercise, our goal is to solve the problem posed to potential employees by a […]
My Haskell solution (see http://bonsaicode.wordpress.com/2012/06/22/programming-praxis-billboard-challenge-part-1/ for a version with comments):
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
[…] recent Programming Praxis problem resurrected the famous Google billboard puzzle. Back in July of 2004, Google put up billboards all over the country […]
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.