At Play With J
The Google Test

Eugene McDonnell

Highway 101 in the San Francisco bay area is a busy commuter highway, with employees commuting to work at the headquarters of such companies as Adobe, Apple, Applied Materials, Cisco, eBay, Genentech, Google, Hewlett Packard, Informatics, Intuit, Oracle, Silicon Graphics, Sun Microsystems, Yahoo, and hundreds more high-tech companies. These commuters recently drove past a large poster paid for by Google, reading:
{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 and enter Bobsyouruncle as the login and the answer to this equation as the password.
F(1)= 7182818284
F(2)= 8182845094
F(3)= 8747135266
F(4)= 7427466391
Those who find the value of F(5), and go to the site shown, would get this message from Google Labs:
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

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 15
To work with the individual digits it is convenient to work with the character form of q.
   w =: ": q
   # w
Here are the first 210 digits:
   7 30 $ w
We need these ten at a time:
   t =: 10 [ \ w
   $ t
202 10
   5 {. t
To determine which of these are prime we have to convert each row into a number.
   p =: ". t
   5 {. x: p
3141592653 1415926535 4159265358 1592653589 5926535897
Some 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
A 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 prime factors primitive q: to obtain the factors of the numbers in p, but will find that this is not always possible; many of the numbers are outside its domain.
   q: 2004
2 2 3 167
   # q: 2004
   q: 2003
   # q: 2003
So 2003 is prime, and 2004 isn't. Here is an is prime function ip:
   ip =: 13 : '1 = # q: y.'

   ip 2003
   ip 2004
   ip 2000000000
   ip 2100000000
      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 
At 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 special is prime function sip to return _1 as result if otherwise a domain error would be reported:
   sip =: ip :: _1:
   sip 2200000000
We 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 1
We can remove the known composites, leaving us with just the known primes and the suspects.
   pc =: (pb ~: 0) # pa
   $ pc
Now 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
   p: 9592
      p: <: 9592
   pf =: p: i. 9592
   {: pf
We 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.'"0
This reads "not 0 in pf residues of y". We apply it to pc:
pd =: nc pc
How many 10-digit primes have we found?
More than enough to solve the puzzle. Which are they?
  ] pe =: I. pd
2 33 36 43 73 108 128 135 149
And what are they?
   pg =: x: pc { ~ pe
   ,. x: pg
Just for fun, locate these in the digits of pi:
   7 30 $ w
Three of them overlap. We want the eighth, 8521105559.

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:

Here they are, embedded in pi:
   7 30 $ w
The first and second overlap, as do the third and fourth.

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, and I'll give you the answer ' but you'll still have to find out why it is.