The Google Test

Eemcd@aol.com

{first 10-digit prime found in consecutive digits of e}.com

Google apparently trusted that some among those passing the poster would understand it, and of these some might be intrigued enough by it to see if they could find that prime, and perhaps some of them might use it to go to the resulting web address. Those who did go the whole route would then find themselves with this message:

Congratulations. You have made it to level 2. Go to www.linux.org and enterThose who find the value of F(5), and go to the site shown, would get this message from Google Labs:Bobsyouruncleas the login and the answer to this equation as the password.F(1)= 7182818284 F(2)= 8182845094 F(3)= 8747135266 F(4)= 7427466391 F(5)=__________

Congratulations. Nice work. Well done. Mazel tov. You've made it to Google Labs and we are glad you are here.One thing we learned while building Google is that it's easier to find what you're looking for if it comes looking for you. What we're looking for are the best engineers in the world. And here you are.

As you can imagine, we get many, many resumes every day, so we developed this little process to increase the signal to noise ratio. We apologize for taking so much of your time just to ask you to consider working with us. We hope you'll feel it was worthwhile when you look at some of the interesting projects we're developing right now. You'll find links to more information about our efforts below, but before you get immersed in machine learning and genetic algorithms, please send your resume to us at problem-solver@google.com.

We're tackling a lot of engineering challenges that may not actually be solvable. If they are, they'll change a lot of things. If they're not, well, it will be fun to try anyway. We could use your big, magnificent brain to help us find out.

You now have all you need to know to dazzle Google with your magnificent brain. I haven't spoiled it for you, so you can legitimately do it on your own. I will, however, give you a similar puzzle, in two parts, and will solve it for you. It uses the digits of pi.

**Problem 1: Finding 10-digit primes**

The first problem is to find among the digits of pi a ten-digit sequence that, when evaluated in base ten, is a prime number, and is the eighth such. Your first problem, then, is to obtain the first few hundred or so digits of pi. We're in luck! The great Indian mathematician Ramanujan used the theory of complex multiplication of elliptic curves to give a number of beautiful formulas for pi's digits, and a variation of this technique was discovered by the ingenious Chudnovsky brothers, from New York City by way of Kiev. A J function for their method is:

Bigpi =: 3 : 0 a=. 545140134x b=. 640320x ^ 3 c=. 13591409x d=. 6541681608x n=. i. >: x: y. s=. (! 6 *n) * c + a * n e=. (! 3 * n) * ((! n) ^ 3) * b^n m=. {: e f=. d * - / (s * m) % e k=. (a * m) * <. @ %: b * 10x ^ 28 * y. k <. @ % f )Given an integer argument n it finds 1+14*n places of pi. To solve the problem you should use a hundred or so digits, so 15 would give about the right number.

q =: bigpi 15To work with the individual digits it is convenient to work with the character form of q.

w =: ": q # w 211Here are the first 210 digits:

7 30 $ w 314159265358979323846264338327 950288419716939937510582097494 459230781640628620899862803482 534211706798214808651328230664 709384460955058223172535940812 848111745028410270193852110555 964462294895493038196442881097We need these ten at a time:

t =: 10 [ \ w $ t 202 10 5 {. t 3141592653 1415926535 4159265358 1592653589 5926535897To determine which of these are prime we have to convert each row into a number.

p =: ". t $p 202 5 {. x: p 3141592653 1415926535 4159265358 1592653589 5926535897Some of these may have had leading zeros, so that they are effectively 9-digits long. We remove them ' some of these may be prime, but they don't qualify as ten-digit primes.

pa =: (p > 999999999) # p $ pa 183A convenient way to determine whether a number is prime is to count how many prime factors it has; if it has just one, the number is prime. We can think of using J's

q: 2004 2 2 3 167 # q: 2004 4 q: 2003 2003 # q: 2003 1So 2003 is prime, and 2004 isn't. Here is an is prime function ip:

ip =: 13 : '1 = # q: y.' ip 2003 1 ip 2004 0 ip 2000000000 0 ip 2100000000 0 ip 2200000000 |domain error: ip | ip 2.2e9 2200000000 = * / 11 5 5 5 5 5 5 5 5 2 2 2 2 2 2 2 2 2 1At this writing, the q: function will yield a domain error for many integers with ten or more digits, even when it is obvious the number isn't prime. To circumvent this, we can use J's adverse conjunction, defined as "The result of u :: v is that of u, provided that u completes without error; otherwise the result is the result of v." We can write a

sip =: ip :: _1: sip 2200000000 _1We use sip on pa to let us know which are known composites (0), which are known primes (1), and which are not determined yet (_1).

pb =: sip " 0 pa ~. pb _1 0 1 # /. ~ pb NB. how many of each 159 23 1We can remove the known composites, leaving us with just the known primes and the suspects.

pc =: (pb ~: 0) # pa $ pc 160Now comes the hard part: determining which of these are prime without the use of q: .

A number is composite if it has two or more prime factors. Twenty-five is composite since it has the two factors 5 and 5. The larger number 9999399973 is also composite, with the two factors 99991 and 100003.

A prime number z has only one prime factor, namely z. A composite number w must have one or more prime factors less than its square root r. It can only have one prime factor s larger than its square root r. It It may be that all of its prime factors are less than r. In any case, to find whether a number is prime or not it suffices to see whether any of the primes less than its square root divides it, that is, gives a residue of zero with n. Thus, if we have a list pf of all of the primes less than r we will be able to determine whether a number n is composite by seeing if it has a residue of zero for any of pf. If it doesn't then we know that n is a prime.

We know that the numbers we are interested in will have values from 1000000000 to 9999999999, inclusive. The square root of the largest number we may find is thus less than 100000, so it suffices that pf contain just the primes less than 100000. We can find these easily by using the function inverse to p:, that is, p: ^: _1.

p: ^: _1 [ 100000 9592 p: 9592 100003 p: <: 9592 99991 pf =: p: i. 9592 {: pf 99991We need a function that finds the residues of a number with respect to each prime in pf, and gives 0 if the number is composite and 1 if it is not, that is, if it is prime.

nc =: 13 : '-. 0 e. pf | y.'"0This reads "not 0 in pf residues of y". We apply it to pc:

pd =: nc pcHow many 10-digit primes have we found?

+/pd 9More than enough to solve the puzzle. Which are they?

] pe =: I. pd 2 33 36 43 73 108 128 135 149And what are they?

pg =: x: pc { ~ pe ,. x: pg 5926535897 4197169399 1693993751 7510582097 4825342117 5822317253 2841027019 8521105559 8954930381Just for fun, locate these in the digits of pi:

7 30 $ w 3141Three of them overlap. We want the eighth, 8521105559.59265358979323846264338327 950288419716939937510582097494 459230781640628620899862803482 534211706798214808651328230664 709384460955058223172535940812 848111745028410270193852110555 964462294895493038196442881097

**Problem 2: Finding the fifth in a series**

You are given five 10-digit numbers from the digits of pi, and must find the sixth. Here are the numbers:

4338327950 2795028841 6939937510 3993751058 2110555964Here they are, embedded in pi:

7 30 $ w 31415926535897932384626The first and second overlap, as do the third and fourth.4338327950288419716939937510582097494 459230781640628620899862803482 534211706798214808651328230664 709384460955058223172535940812 848111745028410270193852110555 964462294895493038196442881097

I'll give two hints, the second vacuous:

Hint 1: Primarily, the sixth number has three doublets and overlaps the fifth.Hint 2: Alternately, something for nothing.

If these hints still aren't enough to let you determine the sixth number, you can mail me at eemcd@mac.com, and I'll give you the answer ' but you'll still have to find out why it is.