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!

About these ads

Pages: 1 2

4 Responses to “Billboard Challenge, Part 2”

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

  2. 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
    
  3. Mike said

    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.

  4. programmingpraxis said

    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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com 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

Follow

Get every new post delivered to your Inbox.

Join 616 other followers

%d bloggers like this: