# Number Theory and a Google Recruitment Puzzle

The main goal of this project is to find the first 10-digit prime in the decimal expansion of 17$\pi$.  

This blog post is going to solve this question by using three helper functions.  

This blog can be retrieved in here: [Pu's Blog](https://puzeng.github.io/BIOSTAT823_Blog_PuZeng/).  

In addition, this notebook is kept in here: [Pu's Repo](https://github.com/puzeng/BIOSTAT823_Blog_PuZeng) under the folder `_notebooks`.

Let's load all the required packages first.  


```python
import math
import numpy as np
import re
import sympy
```

## Expand the mathematical expreesion

First, we are going to generate an arbitrary large expression of a mathematical expression like $\pi$. For that, a helper function called `expansion_expression` will help to do that.  

As the input will be a string that contains the mathematical expression and its coefficient if has, we are going to use regular expression to extract the coefficient of the mathematical expression if there is one.  

Next, we will expand the mathematical expression first to have a number of self-defined digits before generate the multiple of the mathematical expression.  

Then, the multiple of the mathematical expression is generated by multiplying the coefficient with the mathematical expression.  

The following is how the helper function is programmed.


```python
def expansion_mathematical_expression(math_expression, num_digits):
    """Genearate an arbitrary expression of mathematical expression."""
    #Coefficient are the any digits in numeric before the mathematical expression.
    pattern = re.compile(r'[0-9]+')

    if "pi" in math_expression:
        #Generate the mathematical expression in self-defined digits
        expanded_expression = sympy.N(sympy.pi, num_digits)
        if len(pattern.findall(math_expression)) == 1:
            times = float(pattern.match(math_expression)[0])
            expanded_expression = str(expanded_expression * times)

        else:
            expanded_expression = str(expanded_expression)


    if "e" in math_expression:
        #Generate the mathematical expression in self-defined digits
        expanded_expression = sympy.N(sympy.E, num_digits)
        if len(pattern.findall(math_expression)) == 1:
            times = float(pattern.match(math_expression)[0])
            expanded_expression = str(expanded_expression * times)

        else:
            expanded_expression = str(expanded_expression)

    #Ignore the period
    expanded_expression = re.sub(r'\.' , "" ,expanded_expression)
    return expanded_expression
```

## Check prime number

The second helper function that we are going to implement is the function to check whether the number is a prime or not, called `is_prime`.  

We are not going to solve by brute force method which is to use all numbers from 2 to itself to divide that number. However, we can analyze this problem first and solve with the analytical method.  

The product combinations of a number can be divided into two halves where they are mirroring to each other. For example, number 36 has the following combinations:  
1. 1 * 36
2. 2 * 18
3. 3 * 12
4. 4 * 9
5. 6 * 6
6. 9 * 4
7. 12 * 3
8. 18 * 2
9. 36 * 1  

We can notice that the first 4 pairs are mirroring with the last 4 pairs while the fifth pair is the mirroring line. Thus, we can generalize this question by checking whether the number can be divided by the factors up to its square root so that we don't need to check all the factors.

The codes below show how the analytical method is implemented:  


```python
def is_prime(check_window):
    """Check whether the number is a prime or not."""
    check_window = int(check_window)
    # Check whether this number can be divided by any factors up to its sqrt(check_window)
    for i in range(2, int(math.sqrt(check_window))+1):
        if check_window % i == 0:
            return False
        
    return True
```

## Slide window

The third helper function is to generate all the sliding windows on the mathematical expression through looping through the expression. The length of the window is depending on the number of digits that the user is trying to check for the prime.   

This is accomplished by appending all the sliding windows to the other list while sliding down the string.  

Below shows how the above arguments are implemented:  


```python
def slide_window(width, input_text):
    """Generate all sliding windows for a mathematical expression based on the customized length."""
    slide_windows = list()
    while len(input_text) >= width:
        slide_windows.append(input_text[:width])
        input_text = input_text[1:]
        
    return slide_windows
```

## Assemble to answer the question

As we go through all the helper functions that are used in answering the question, we now can assemble them as in one function to help solve the puzzle.  

The main function will take two arguments:  
1. `num_digits`: an integer for defining the number of digits to expand on the mathematical expression.  
2. `math_expression`: a string that are going to be expanded based on which mathematical expression is input.
3. `width_side_window`: an integer for indicating how many digits that the prime is going to be.  

Within the big function called `ten_digits_primes_in_expression`, we will first generate an arbitrary large expression of the corresponding mathematical expression by self definition through the function, `expansion_mathematical_expression`.  

Then, we are generating all the sliding windows based on a self-defined length which is also equivalent to the number of digits in the prime, by calling the function `slide_window`.

To tell whether the slide window is a prime a not, we need to call function `is_prime`. If it is a prime, this function will return True and otherwise.  

Once, we detect that if the slide window is the prime, we will immediatelly return as the digits in the slide window. If not, we will go to the next slide window.  

Below shows how the above arguments are implemented and how to use the function:  


```python
def ten_digits_primes_in_expression(num_digits, math_expression, width_slide_window):
    """Extrat first 10 prime digits in a mathematical expression."""
    #Expand the expression in self-defined digits
    expanded_expression = expansion_mathematical_expression(math_expression, num_digits)
    
    #Generate all the slide windows by self-defined width
    all_slide_windows = slide_window(10, expanded_expression)
    
    #Check whether the current window is prime or not
    for ele in all_slide_windows:
        if is_prime(ele) == True:
            return ele
```


```python
first_prime = ten_digits_primes_in_expression(300, "17pi", 10)

print(f"The first 10-digit prime in the decimal expansion of 17\u03C0 is {first_prime}.")
```

    The first 10-digit prime in the decimal expansion of 17π is 8649375157.


## For contributors: Testing


```python
import unittest

class TestNotebook(unittest.TestCase):
    def test_expansion_mathematical_expression(self):
        self.assertEqual(expansion_mathematical_expression("pi", 10), '3141592654')
        self.assertEqual(expansion_mathematical_expression("e", 10), '2718281828')

    def test_is_prime(self):
        self.assertEqual(is_prime(2), True)
        self.assertEqual(is_prime(111), False)
        self.assertEqual(is_prime(5), True)
        self.assertEqual(is_prime(596), False)

    def test_slide_window(self):
        self.assertEqual(slide_window(5, "12345"), ["12345"])
        self.assertEqual(slide_window(1, "12345"), ['1', '2', '3', '4', '5'])

    def test_ten_digits_primes_in_expression(self):
        self.assertEqual(ten_digits_primes_in_expression(300, "e", 10),
                        '7427466391')

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

    test_expansion_mathematical_expression (__main__.TestNotebook) ... ok
    test_is_prime (__main__.TestNotebook) ... ok
    test_slide_window (__main__.TestNotebook) ... ok
    test_ten_digits_primes_in_expression (__main__.TestNotebook) ... ok
    
    ----------------------------------------------------------------------
    Ran 4 tests in 0.015s
    
    OK





    <unittest.main.TestProgram at 0x7fd1e715e850>



## Supplementary materials

Besides to check whether a number is a prime or not by the above analytical method, we can also solve this question by another analytical approach, Sieve of Eratosthenes.  

In general, the mechanism follows that within a range of number, the multiples of 2, 3, 4, and all the way up to the square root of the number will be crossed out.  

The implementation then will follow:
1. Initially, generate a boolean list to cast those primes by the length of that number.
2. We will then cross out the multiples of 2 at the beginning and stop untill the multiples of 2 is greater that number.
3. Then, cross out the multiples of 3.
4. Cross out the multiples of factors that are all the way up till the square root of that number.
5. Generate an array contains a range of that number.
6. Map the boolean list to the array to get all the primes of the range.  
7. If that number itself is within the list, then return True or otherwise.  

This method based on Siev of Eratosthene is much faster than the method used above since the complexity is O(N* log(log(N))) compared to O(sqrt(N)).  


```python
def is_prime_sieve_eratosthenes(check_window):
    """Check whether the number is a prime or not based on Sieve Of Eratosthenes."""
    #Create a list of True initially
    #Once find the multiples, update True as False
    check_window = int(check_window)
    prime_list = [True for num in range(check_window+1)]
    iterate_num = 2

    while iterate_num * iterate_num <= check_window:
        if prime_list[iterate_num] == True:
            for i in range(iterate_num * iterate_num, check_window+1, 2):
                prime_list[i] = False
        iterate_num += 1
    
    target_list = np.array(range(0, check_window+1))
    target_list = target_list[prime_list]
    return check_window in target_list

print(f"5 is a prime? {is_prime_sieve_eratosthenes(5)}")
```

    5 is a prime? True


2253045c1a1badf6825b245fb4596350b78b46f5
ipynb
Jupyter Notebook
_notebooks/2021-09-17-Assignment2_PuZeng.ipynb
puzeng/BIOSTAT823_Blog_PuZeng
a4dd7f2928f5b1c03011e7eaf323ddc5ffc62727
Apache-2.0
_notebooks/2021-09-17-Assignment2_PuZeng.ipynb
puzeng/BIOSTAT823_Blog_PuZeng
a4dd7f2928f5b1c03011e7eaf323ddc5ffc62727
Apache-2.0
_notebooks/2021-09-17-Assignment2_PuZeng.ipynb
puzeng/BIOSTAT823_Blog_PuZeng
a4dd7f2928f5b1c03011e7eaf323ddc5ffc62727
Apache-2.0
Qwen/Qwen-72B
1. YES
2. YES