Code Lore

A few years back, google did a recruitment drive whereby they put up a bill-board which said:

{First 10 digit prime in consecutive digits of e}.com

The idea being that you work out the first 10 prime digits in consecutive digits of e (as in euler's number), tack on '.com' and surf on over in your web-browser. What followed was another challenge, which appealed to the number theorists in the audience, and once that was solved, you finally got to an exam, whose successful completion would qualify you for an interview with google.

I was pretty happy with my job at the time, so I wasn't imediately looking for an 'in' to google. I thought it was a fun challenge though, so I did spend some time working on some of the questions. I just stumbled on some of the code I wrote to do this, so I thought it might be fun to run a series of articles here that work through the problems, providing solutions where I have them.

So this one is about the first part of the challenge: finding those 10 consecutive digits that are also prime. Like everyone else who worked on this challenge, I searched and downloaded n digits of e from somewhere. I then found a list of primes, and tested each one as a factor for every 10-digit substring of my n digits of e.

However, working out which ones were actually prime, rather than not trivially composite was sounding way-ay-ay too much like hard work. So I employed a slightly different approach: I used the DNS server as an IsPrime function. I reasoned that for this website to work, it would need to have a URL, so having reduced my set of 10-digit substrings of e to a set of likely candidates, I fired of a small zillion DNS queries to find which ones actually turned into resolvable addresses. The script unfortunately no longer works, since google have taken the site down (which is a shame), but the salient parts follow. If nothing else, it might serve as a good example of how to use Python's DNS module.

#!/usr/bin/python

# Solve google's "{first 10-digit prime in digits of e}.com" problem.

import DNS

DNS.DiscoverNameServers()

e = '''2718281828459''' # ...

distincts = {}

small_primes = [

    2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73

    # ...

]

def obviousComposite(n) :

    for f in small_primes :

        if n % f == 0 :

            return True

    return False

if __name__ == '__main__' :

    for i in range(len(e)) :

        current = int(e[i:i + 10])

        if obviousComposite(current) :

            continue

        # check if we've hit this before (which we won't) and check that the

        # string representation is actually 10 digits long (numbers which start

        # with 0s won't end up being 10 digits long)

        if not distincts.has_key(current) and len(str(current)) == 10:

            distincts[current] = i

    sfn = lambda x, y: cmp(distincts[x], distincts[y])

    nums = distincts.keys()

    nums.sort(sfn)

    # now, we're looking for the first of these numbers that is prime.

    # Fortunately, google's DNS servers provide us with a convenient primality

    # checker -- assuming the website they're advertising /exists/, there would

    # need to be DNS records for it. Thus, we search through the list for the

    # first number where there are zone records.com.

    for n in nums :

        host = '%d.com' % n

        try :

            host_info = DNS.Base.DnsRequest(host, qtype='a').req().answers[0]

            print host

            break

        except :

            pass

Of course, solving this in SQL should be a snap after my last post :)

The answer you end up getting is 7427466391.com, by the way. As I said before, the site is down. Here's what it said, when it was still online:

Congratulations. You've made it to level 2. Go to www.Linux.org and enter Bobsyouruncle as the login and the answer to this equation as the password.

f(1)= 7182818284
f(2)= 8182845904
f(3)= 8747135266
f(4)= 7427466391
f(5)= __________

If you're impatient, or less behind the times than I, you can go and find one of the zillions of others who have posted the solution. It's fairly simple though, so try it yourself if you don't know the answer (it's fun!). I'll post something about it soon.