{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 enter Bobsyouruncle as the login and the answer to this equation as the password.Those who find the value of F(5), and go to the site shown, would get this message from Google Labs: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
5926535897
To 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 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 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 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 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
1
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 _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
99991
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.'"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
8954930381
Just for fun, locate these in the digits of pi:
7 30 $ w 314159265358979323846264338327 950288419716939937510582097494 459230781640628620899862803482 534211706798214808651328230664 709384460955058223172535940812 848111745028410270193852110555 964462294895493038196442881097Three 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:
4338327950 2795028841 6939937510 3993751058 2110555964Here they are, embedded in pi:
7 30 $ w 314159265358979323846264338327 950288419716939937510582097494 459230781640628620899862803482 534211706798214808651328230664 709384460955058223172535940812 848111745028410270193852110555 964462294895493038196442881097The 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 eemcd@mac.com, and I'll give you the answer ' but you'll still have to find out why it is.