# Number theory and a Google recruitment puzzle

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

Description: The first 5 digits in the decimal expansion of π are 14159. The first 4-digit prime in the decimal expansion of π are 4159. You are asked to find the first 10-digit prime in the decimal expansion of 17π. 

There are three main steps to this question.   
    1) Generate an arbitrary large expansion of a mathematical expression  
    2) Check if a number is prime  
    3) Generate sliding windows of a specified width from a long iterable  
  
We will start with the first step. The goal is to return an arbitrary expansion (expansion after the decimal) of a mathematical expression. The user inputs will be the mathematical expression along with the multiplier (can be 1) and the number of digits of the expansion.
  
I first tried using the decimal library to expand the mathematical expression "pi", but I realized I was approximating pi by using the expression "355/113" and I could not find a more accurate way to expand pi, so I opted to use the sympy library. I used the decimal library to expand "e".  
  
One important thing to note is that a multiplier of the mathematical expression can be an input like "2e" or "3pi". The multiplier must be a separate input from the expression. 


```python
from decimal import *
from sympy import *

def expansion(multiplier, expression, n):
    """
    Input: mathematical expression, a multiplier of the expression, and number of digits of prime number
    Behavior: expands mathematical expression
    Output: an arbitrary expansion (specified by user) of a mathematical expressions pi or e 
    """
    if expression == "pi":
        # N function captures number of digits, so use log formula to capture number of specified digits after decimal
        x = N(multiplier*pi, n + log(multiplier*pi, 10) + 1)
        # obtain digits after decimal and return as integer 
        # integers that start with 0 will not capture the 0
        before, after = str(x).split('.')
        return int(after)
    
    if expression == "e":
        # set number of digits for expansion
        getcontext().prec = n
        x = (Decimal(1).exp())*multiplier
        before, after = str(x).split('.')
        return int(after)
    
    # can only generate expansions of pi and e
    else:
        return "Can not solve"
```

The next step is to determine if a number is prime. To make this function efficient, we can loop through divisors in the range from 2 to the square root of the number rounded up using the ceiling function from the math module and check whether that number is a factor. The mathematical intution behind this is that a number that is not prime will have at least one factor that is less than its square root (and one factor greater). So, if a number has no factors less than its square root, it must be prime. For example, let's take the number 11. The square root of 11 rounded up is 4, so the loop will run from 2 to 4. If there are no factors in that range, that 11 is prime, which is the case. I used this mathematical intuition because looping through all numbers in the range to the specified number is very inefficient, especially because we are working with such large numbers in this question. 


```python
from math import sqrt, ceil

def prime_num(n):
    """
    Input: number
    Behavior: returns true if number is prime
    Output: true or false
    """
    # prime numbers have to be greater than 1
    if n > 1:
        # loop through numbers in range 2 to the ceiling of the square root of the specified number
        for number in range(2, ceil(sqrt(n))):
            # return to outer for loop and increment by one if input number is not divisible by number
            if (n % number) == 0:
                # number is not prime (divisible by a number other than one and itself)
                return False
        else:
            # number is prime, so return true
            return True
    else: 
        # return false if number is not greater than 1
        return False
```

The next step is to write the final helper function. The goal is to generate sliding windows of a specified width from a long iterable.

I tried a lot of different things to generate sliding windows including using itertools, but decided that using list comprehensions would be equally succinct in accomplishing this task.   
  
First, we will make the iterable (input number) into a list of its digits as strings. For example, 1234 becomes ['1','2','3','4']. Then, we will create a window of a specified size for each element (digit) in the range of the number until a window of the specified size cannot be made. For example, if we want a window of size 3, we will loop through all the elements in range of the length of the list of digits minus the size of the window plus one. So, using our example, the loop will run from '1' to '2'. For each iteration, the window will be appeneded as a list to a list of windows. So, from our example, [['1','2','3'],['2','3','4']] will be the output from the loop. Next, we want to return a list of integers, so we will combine the digits into one number and convert to an integer. From our example, the output would be [123, 234].


```python
def sliding_window(iterable, size):
    """
    Input: integer and size of window 
    Behavior: generates sliding windows of a specified width from a long iterable
    Output: list of windows
    """
    window_list = []
    
    # length of number has to be greater than the window size
    if len(str(iterable)) >= size:
        # make iterable into list of its digits
        it_list = [str(x) for x in str(iterable)]
        
        # create window as a list by grabbing elements in range of current element through the elements in the window size
        windows = [it_list[x:x+size] for x in range(len(it_list) - size + 1)]
        
        # convert list of digits in window to a single integer and append to list
        for window in windows:
            a_string = "".join(window)
            an_integer = int(a_string)
            window_list.append(an_integer)
            
        # returns list of integers
        return window_list
    else:
        return "Size of window bigger than iterable"
```

The final step is to create a function with these helper functions to return a specified digit-length prime in the decimal expansion of a mathematical expression like "pi". First, we will create the decimal expansion using the expansion helper function. Then, we will create the list of sliding windows given the size of the prime number we want using the sliding windows helper function. Finally, we will check whether each number in each window is prime using the prime helper function and return the first prime number. 


```python
def prime_expanded_expression(size, multiplier, expression, digits):
    """
    Input: size of window, multiplier of expression, mathematical expression, and number of digits to expand
    Behavior: returns a specified digit-length prime in the decimal expansion of a mathematical expression
    Output: number
    """
    # create decimal expansion of mathematical expression
    expanded = expansion(multiplier, expression, digits)
    # create list of sliding windows of decimal expansion given size of window
    expansion_window = sliding_window(expanded, size)
    # check whether each window (number) is a prime and if it is, return that number
    for number in expansion_window:
        # numbers that are less than a length of 10 start with 0, so cannot be prime
        if len(str(number)) == 10:
            # check whether number is prime
            if prime_num(number):
                return number
```

Now, we will write unit tests for each function to assert that they are returning the correct values and to check edge cases. Two tests are written for each function.


```python
import unittest

class TestNotebook(unittest.TestCase):
    
    def test_expansion(self):
        """test expansion."""
        self.assertEqual(expansion(1, "pi", 5), 14159)
        self.assertEqual(expansion(17, "pi", 9), 407075111)
        
    def test_prime_num(self):
        """test prime_num."""
        self.assertFalse(prime_num(1))
        self.assertTrue(prime_num(4159))
        
    def test_sliding_window(self):
        """test sliding_window."""
        self.assertEqual(sliding_window(407075111, 4), [4070, 707, 7075, 751, 7511, 5111])
        self.assertEqual(sliding_window(1234, 5), "Size of window bigger than iterable")
        
    def prime_expanded_expression(self):
        """test prime_expanded_expression."""
        self.assertEqual(prime_expanded_expression(10, 1, "e", 110), 7427466391)
        self.assertEqual(prime_expanded_expression(4, 1, "pi", 110), 4159)

unittest.main(argv=[''], verbosity=2, exit=False)
```

    test_expansion (__main__.TestNotebook)
    test expansion. ... ok
    test_prime_num (__main__.TestNotebook)
    test prime_num. ... ok
    test_sliding_window (__main__.TestNotebook)
    test sliding_window. ... ok
    
    ----------------------------------------------------------------------
    Ran 3 tests in 0.015s
    
    OK





    <unittest.main.TestProgram at 0x7f210dc81650>



Finally, let's solve the problem! The first 10-digit prime in the decimal expansion of 17π is 8649375157.


```python
print(prime_expanded_expression(10, 17, "pi", 110))
```

    8649375157


cc7ff3c27365a4be579c01f5fcee40e23109d881
ipynb
Jupyter Notebook
_notebooks/2021-09-17-numbertheory.ipynb
saahithirao/bios-823-blog
23644cb773a0bdea3810cc807fb15b40387ce625
Apache-2.0
_notebooks/2021-09-17-numbertheory.ipynb
saahithirao/bios-823-blog
23644cb773a0bdea3810cc807fb15b40387ce625
Apache-2.0
_notebooks/2021-09-17-numbertheory.ipynb
saahithirao/bios-823-blog
23644cb773a0bdea3810cc807fb15b40387ce625
Apache-2.0
Qwen/Qwen-72B
1. YES
2. YES