Number Theory and A Google Recruitment Puzzle

Google 2004 recruitment puzzle solved! And a demonstration of unit testing in Python using unittest.

In 2004, Google put on mysterious billboards around subway stops near major universities. Google’s name was nowhere to be found on the billboard. It simply read:

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

Since 2004, there are many different approaches online. The solution to this problem is 7427466391. Instead of solving the problem, in this post, I generalize the solution by demonstrating my approach to a different but similar problem. Here is the problem statement:

Find the first 10-digit prime in the decimal expansion of 17π.

My approach to this problem breaks down into three smaller steps:

• Step 1: a function to generate an arbitrary large expansion of a mathematical expression like π
• Step 2: a function to check if a number is prime
• Step 3: a function to generate sliding windows of a specified width from a long iterable.

Step 1

To generate an arbitrarily large decimal expansion for a mathematical expression, we need to use a Python package that can support high decimal precision. Here, I use the open-sourceSymPy package. It support exact mathematical expression such as π and e. Since we are interested in the decimal expansion of 17π, here is how to get the exact SymPy expression for π.

import sympy as sym

sym.pi
# the exact SymPy expression for π

After getting the exact expression for π, we need to evaluate it to a specified precision. The function that achieves this in SymPy is evalf(). As the name implies, evalf() evaluate an SymPy expression as a floating point number. We can pass the precision we want in evalf() as an argument. Like this,

n = sym.pi # math expression
p = 10 # precision desired
n.evalf(p) 
# output: 3.141592654

To get the decimals, we can treat the float as a string, then split the number at ., and takes everything after the period.

Notice that the number of digits after the period in the example is only 9. This is because of the one digit to the left of the period. To make the number of digits equals to the precision desired, I make an adjustment to precision so that the output has the same number of digits as precision desired.

Here is the code to implement this:

Step 2

To check whether a number is prime, we can loop through all integer between 2 and that number. In the loop, we try to find a divisor that can divide that number without having a remainder. If we do, then that number is not a prime. For example, if we are interested in checking whether n is a prime number,

for i in range(1, n):
  if (n % i) == 0:
    print(Not a prime!)
    break 

This is feasible for small numbers. However, as the numbers get larger, it becomes inefficient to loop through a large amount of numbers. Since we want to check the primality of 10-digit number, it would be extremely computationally inefficient. A more efficient way to check a prime number is to only loop through 2 to the square root of the number. This is because a composite number must have a factor less than the square root of that number.

Here is how to implement this in Python:

Step 3

The third step is a function that generates a list of all possible numbers for a specified window size. For this problem, we want this function for generate all possible consecutive 10-digit numbers for 17π. This is done by sliding a window of size 10 to the number with stride 1.

Here is the code in Python:

Putting Everything Together

Now that we have all three helper functions, we are ready to put them together to produce the final solution. We call the first function to generate the decimal expansion for 17π with 200 precision. Then we call the sliding_window() function to generate a list of all consecutive 10-digit numbers in the decimal expansion. After this, we loop through the list to check whether the current number is prime. We break out the loop once we have found one.

Here is the code:

Unit Testing with unittest

To ensure the code works as expected, I use the Pythonunittest module to conduct unit tests on each smaller function. To use unittest, we write a class for each function we want to test. And we write the test cases as methods within the class. Then, we use assert to test whether the function produce the expected results. For example to test whether the gen_expansion() function product 14 for the 2 precison decimal expansion. We do

import unittest
import sympy as sym

from find_first_prime import *
# import the functions we wrote

class TestGenExpansion(unittest.TestCase):
    def test_numbers(self):
        """
        Test for gen_expansion function.
        """
       
        result = gen_expansion(sym.pi, 2)
        self.assertEqual(result, '14')

We can also check whether output raise errors for incorrect input. For example, for the is_prime() function, the function should raise ValueError if a user inputs a negative. We can check whether the function handles this situation correctly by doing this:

class TestIsPrime(unittest.TestCase):
   def test_input_value(self):
        self.assertRaises(TypeError, is_prime, -3)

Refer to the complete code and notebook here!