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!

Posted by programmingpraxis

Filed in Exercises

4 Comments »

4 Responses to “Billboard Challenge, Part 2”

Programming Praxis – Billboard Challenge, Part 2 « Bonsai Code said
June 26, 2012 at 7:29 PM
[…] today’s Programming Praxis challenge, our goal is to solve the second part of the billboard test, which is […]
Remco Niemeijer said
June 26, 2012 at 7:30 PM
My Haskell solution (see http://bonsaicode.wordpress.com/2012/06/26/programming-praxis-billboard-challenge-part-2/ for a version with comments):
```
main :: IO ()
main = print $ [x | x <- map (take 10) $ tails stream_e, sum x == 49] !! 4
```
Mike said
June 27, 2012 at 2:14 AM
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):
```
from itertools import ifilter, islice
from myutils import accumulate, even

def Lucas():
    '''Lucas numbers are given by: L(0) = 2, L(1) = 1, and L(n) = L(n-1) + L(n-2).  Similar to Fibonacci numbers
    '''
    a, b = 2, 1

    while True:
        yield a
        a, b = b, a+b

for i, n in enumerate(islice(accumulate(ifilter(even, Lucas())), 5),1):
    print "f({}) = {}".format(i, ''.join(map(str, islice(e_digits(), n-1, n+9))))
```
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.
programmingpraxis said
June 27, 2012 at 5:30 PM
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.

Programming Praxis