It’s a bit late, but I solved it nevertheless. Just last week, I was catching up on my RSS feeds after being away for so long and found that google had a challenge issued on July 12th. Supposedly, this challenge was a publicity stunt and a method to recruit the best minds in the computing field. The challenge was a cross between mathematics and computer science, and I decided to give it a try. After all, the challenge seemed fun and interesting—keeping my brain thinking.
The first clue was straightforward: “{first 10 digit prime found in consecutive digits of e }.com�
WARNING!!! CHALLENGE SPOILERS BELOW. IF YOU WANT A CHALLENGE BY SOLVING IT YOURSELF, DO NOT READ ON!!!
To solve this, I knew that I would have to take every 10 digit blocks of e, Euler’s constant, and test them for primality. When I find the first block of 10 digits that are prime, I would craft those numbers into a url (add the .com) and that should take me somewhere.
My first problem was finding enough digits of e. In day-to-day programming, built in constants to programming languages do not have the precision to handle or calculate e to many digits. For instance, in Java, calling Math.E results in only 15 or so decimal places, hardly enough to solve this challenge.
On the other hand, during my brief dip into the Maple math software at CMU, I learned a method to calculate e to any precision with the expression:
evalf(exp(1), [insert number of decimal places here]);
So initially, I was planning to write a program in Maple to solve the problem. However, programming in Maple was less than satisfactory. The language didn’t strike my fancy. Not wanting to work against something, I turned to alternative solutions.
I decided to try my hand at Python. Much hyped these days and used by many big names, Python has a good reputation of being easy to write and very powerful. Even Eric S. Raymond himself converted! Hm, that must be something.
After downloading Python, I looked for a way of generating the digits of e. I found the promising gmpy library, but no matter how much I searched, gmpy just didn’t seem to have a way of generating e. It could generate Pi easily however: gmpy.pi([number of decimal places here]). You’d think they would have: gmpy.e() or gmpy.exp(), but no, they don’t.
So hours of grueling work ensued until I finally found a library called real for python (I’m hosting it on this site because of its hard to find nature). Although outdated and very slow, real did what I wanted with an intuitive command: real.e([number of digits]). From here, I wrote two Python programs: PrimeCheck and Google01. PrimeCheck was an exercise for me in getting up to speed with Python. I could have used a pre-existing prime check library if I wanted to. Google01 was my attempt at solving the first google challenge:
# Solve google challenge 01
# Find first 10 digit prime from the digits of e
import real
from PrimeCheck import isPrime
digits = 1000
e = real.e(digits) #compute e to n digits
strDigitsOfE = str(e)[2:-3] #Omit first 2 “2.” and last 3 “+-2″
#Take every 10 digits and check for prime
for startDigitPlace in range(digits-10): #can’t select 10 digits from n-9th place
#select blocks of every 10 digits and check for prime
if isPrime(int(strDigitsOfE[startDigitPlace:startDigitPlace+10])):
print strDigitsOfE[startDigitPlace:startDigitPlace+10],” | Position: “,startDigitPlace
Only 17 lines of code that did the trick:
7427466391 | Position: 98
7413596629 | Position: 122
6059563073 | Position: 148
...
...
4563549061 | Position: 920
0510115747 | Position: 947
The position part isn’t really necessary, but I added it in there to see if there were any patterns (hey, you never know!). The code executed quickly, and I had my answer.
Excited, I entered in the url: http://7427466391.com. The site featured a regular white page with another problem centered on the page. I felt like the Batman going after the Riddler!:
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)= __________
Hidden inside the source code of the page was an interesting “no help here” comment. But anyway, this second part was a lot harder than the first part. Again, the question seemed straightforward. To me, it said: “Here are a few inputs and outputs of a function. Figure out f(5) or else we’ll post your biggest secret on our main page!” Okay, okay, maybe not the last part, but I had to find f(5).
Normally, when encountering a problem like this, one might try to reverse engineer the function based on its inputs and outputs. This was what I tried at first, using excel and maple to calculate best fit lines, but I did not have any success. The points plotted on a graph did resemble the top of a bell curve however. This threw me off track as I tried to best fit a gaussian plot to the points! Bad idea!
So exhausted from my failed attempts. I sought some hints using google’s own search engine. I stumbled on another page with full write ups, but since I wanted to solve this myself, I only read a small portion of the page for my hint: “all of the outputs of f() are digits of e”. Why, of course! How could I have not seen that! In my haste, I didn’t realize that the url I found was part of the outputs to f(). I made a mental note to be more careful in the future.
But then, what’s the correlation from input to output? What’s the pattern here? I tried finding the position where each output began in the digits of e and tried to discern a pattern there, but with no success. Finally, on a whim, I decided to add up the digits in each output: 49. Bingo. That’s it. So simple, yet so elusive.
From here, all the coding required was slight modifications of Google01. Essentially, I needed a function that summed the digits in a number, and instead of checking for prime, I check to see if the sum of the digits of 10-block numbers of e equaled 49. Google02 is as follows:
# Solve google challenge 02
# Sum of ten digit blocks from e that equal 49
import real
def sumOfDigits(inNumber):
#convert to string
strNum = str(inNumber)
sum = 0 #sum of all digits
for digit in strNum[:]:
sum = sum + int(digit)
return sum
digits = 1000
e = real.e(digits) #compute e to n digits
strDigitsOfE = str(e)[2:-3] #Omit first 2 “2.” and last 3 “+-2″
#Take every 10 digits and check for sum of 49
for startDigitPlace in range(digits-10): #can’t select 10 digits from n-9th place
#select blocks of every 10 digits and check for sum of 49
if (sumOfDigits(int(strDigitsOfE[startDigitPlace:startDigitPlace+10]))==49):
print strDigitsOfE[startDigitPlace:startDigitPlace+10],” | Position: “,startDigitPlace
Around 31 lines this time. Not too bad. The output:
7182818284 | Position: 0
8182845904 | Position: 4
8747135266 | Position: 22
7427466391 | Position: 98
5966290435 | Position: 126
2952605956 | Position: 144
...
...
5209618369 | Position: 880
6965521267 | Position: 974
The first four outputs corresponded with the givens in part 2. Now, I had f(5) which equals 5966290435. Coolness. A quick trip to Linux.org entering in the login information dropped me at the end of the Google challenge–a recruiting page. Darn. I wanted to do more!
And thus, my google journey end. I hope you tried the challenge.