## Billboard Challenge, Part 2

### June 26, 2012

You may recognize some of the early digits of *e* in f(1) = 7182818284, and with that hint and the knowledge that you have just completed an exercise on the digits of *e*, you will doubtless recognize that all the numbers are found in consecutive digits of *e*. With a little bit of work and a small flash of inspiration you will find the pattern in these numbers:

7 + 1 + 8 + 2 + 8 + 1 + 8 + 2 + 8 + 4 = 49

8 + 1 + 8 + 2 + 8 + 4 + 5 + 9 + 0 + 4 = 49

8 + 7 + 4 + 7 + 1 + 3 + 5 + 2 + 6 + 6 = 49

7 + 4 + 2 + 7 + 4 + 6 + 6 + 3 + 9 + 1 = 49

So the task is to find the next ten-digit number found in consecutive digits of *e* with digits that sum to 49. This is just a variant of the previous billboard challenge:

`(define (billboard2 k)`

(let loop ((k k) (i 0) (n (e-spigot)))

(if (and (< #e1e9 n) (= (sum (digits n)) 49))

(if (= k 1)

(values i n)

(loop (- k 1) (+ i 1)

(+ (* 10 (modulo n #e1e9)) (e-spigot))))

(loop k (+ i 1) (+ (* 10 (modulo n #e1e9)) (e-spigot))))))

The fifth sum-of-ten-digits = 49 number in the digits of *e* is:

`> (billboard2 5)`

136

5966290435

You can see more at A095926, and you can run the program at http://programmingpraxis.codepad.org/14Q1hJvZ.

Back in 2004, if you solved this problem and went to login as directed, you were directed to a Google recruiting web site, with these two programming challenges forming an “entrance examination” for Google recruiters. The challenge became rather famous, with pieces on *NPR*, the *Boston Globe* and the *Oakland Tribune*, not to mention a few dozen blog posts (and now, this one). Presumably Google found some good talent, and all the publicity was doubtless good for their branding image. Good job, Google!

Pages: 1 2

[…] today’s Programming Praxis challenge, our goal is to solve the second part of the billboard test, which is […]

My Haskell solution (see http://bonsaicode.wordpress.com/2012/06/26/programming-praxis-billboard-challenge-part-2/ for a version with comments):

The difficulty with these kinds of problems is that the given terms often do not identify a unique sequence.

For example, I determined that the values for f(1), f(2), f(3), and f(4) start at position 2, 6, 24, and 100, respectively, in the digits of e. After a few minutes at OEIS.org, I discovered that the differences between successive indices–2, 4, 18, 76–correspond to the first few even Lucas numbers. So I whipped up the following Python code to calculate f(5):

Which results in the following output:

f(1) = 7182818284

f(2) = 8182845904

f(3) = 8747135266

f(4) = 7427466391

f(5) = 4637721112

If you’ve looked at the Praxis solution, this is not the answer they were looking for.

Mike: Yes, that’s a problem.

My solution also differs from the suggested solution at A095926, because I require all numbers to be ten digits long, as in the first challenge problem, but the OEIS solution permits leading zero.