# 823 HW2 -Candice Li
## Number theory and a Google recruitment puzzle

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


In order to find the first 10-digit prime in the decimal expansion of 17π, three functions were defined. 


### Import libraries going to be used


```python
import math
import decimal
try:
    from sympy.mpmath import mp
except ImportError:
    from mpmath import mp
```

The function *expansion_generater* is used to get n places after the decimal point for irrational number. First the decimal places after the decimal point is defined to be 1000 so that it is long enough to find the target segment. Then, the actual expression being used is genrated based on the input parameters. In this program, only e and π are being considered. Then, the part after the decimal point of the expression with desired length is being extracted and returned.


```python
def expansion_generater(n, symbol, time):
    """Get n places after the decimal point for irrational number.
    
    n : int
    The length of the wanted number after decimal places.
    """
    mp.dps = 1000
    if symbol == 'pi':
        a = mp.pi
    elif symbol == 'e':
        a = mp.e
    
    exp = a*time

    before_dec, after_dec = int(exp), exp - int(exp)
        
    return str(after_dec)[2:n+2]
```

The function *is_prime* is used to check if an integer is a prime number. First, special cases like 0, 1, and 2 are being accounted for. 0, 1 are hard-coded to be not prime and 2 is hard-coded to be prime. Secondly, all the even numbers are coded to be not prime. Then we check if the square root of the number can be diviide by any number smaller than itself. If there is one, then this number is not prime. Otherwise, it is a prime number.


```python
def is_prime(n):
    """Check if an integer is a prime number.
    
    n : int
    The integer we want to check if it is prime.
    """
    if n == 0 or n == 1:
        return False
    elif n == 2:
        return True
    elif (n > 2 and n % 2 == 0):
        return False
    else:
        for i in range (3, 1 + math.floor(math.sqrt(n)), 2):
            if n % i == 0:
                return False
    return True
```

The function *get_window* is used to get all the integers with desired length in an expression. First, the expression is converted from integer to string. Secondly, a list is created to store the integers. Then, we start from the first index take out every integer segment with desired length.


```python
def get_window(n, expression):
    """Get the integers of length n in an expression.
    
    n : int
    The length of the wanted intger in the expression.
    """
    expression = str(expression)
    result = []
    for i in range(0, len(expression)):
        if len(expression[i:i+n]) == n:
            result.append(expression[i:i+n])
    return result
```

The function *find_n_digit_prime* is the function that calls all of the functions written above and return the first value that satisfy the requirement. First, we get the segments of desried length using the function *get_window* and *expansion_generator*. *expansion_generator* returns the expression based on input and *get_window* get the segments with certain lenth in the expression. The, we store the segments if it has the same length with the desired length (the length may be shorter when reaching the end of the expression). Fianlly, we return the first segment in this list. This interger will be the final answer from this program. 


```python
def find_n_digit_prime(total_len, symbol, time, seg_len):
    segments = get_window(seg_len, expansion_generater(total_len, symbol, time))
    found = []
    for j in range (0, len(segments)):
        if is_prime(int(segments[j])):
            found.append(int(segments[j]))
    return found[0]
            
```

### Run the code and get the answer for the first 10-digit prime in the decimal expansion of 17π.


```python
answer = find_n_digit_prime(1000, "pi", 17, 10)

print("The first 10-digit prime in the decimal expansion of 17π is "+ str(answer) +".")
```

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


## Unit tests

### Test for funtion *expansion_generater*


```python
import unittest
```


```python
class TestNotebook(unittest.TestCase):
    
    def expansion_generater(self):
        self.assertEqual(expansion_generater(10, 'pi', 1), 1415926535)
        self.assertEqual(expansion_generater(11, '2', 2), 43656365692)
        

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

    
    ----------------------------------------------------------------------
    Ran 0 tests in 0.000s
    
    OK





    <unittest.main.TestProgram at 0x7fe6ee1b1210>



### Test for funtion *expansion_generater*


```python
class TestNotebook(unittest.TestCase):
    
    def is_prime(self):
        self.assertEqual(is_prime(150), False)
        self.assertEqual(is_prime(11), True)
        self.assertEqual(is_prime(2), True)
        

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

    
    ----------------------------------------------------------------------
    Ran 0 tests in 0.000s
    
    OK





    <unittest.main.TestProgram at 0x7fe6ee24f210>



### Test for funtion *get_window*


```python
class TestNotebook(unittest.TestCase):
    
    def get_window(self):
        self.assertEqual(get_window(1, 12345), ['1', '2', '3', '4', '5'])
        self.assertEqual(get_window(2, 12345), ['12', '23', '34', '45'])
        self.assertEqual(get_window(3, 12345), ['123', '234', '345'])
        

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

    
    ----------------------------------------------------------------------
    Ran 0 tests in 0.000s
    
    OK





    <unittest.main.TestProgram at 0x7fe6ee1d4050>



### Test for funtion *find_first_ten_digit_prime*


```python
class TestNotebook(unittest.TestCase):
    
    def test_n_ten_digit_prime(self):
        self.assertEqual(find_first_ten_digit_prime(1000, 'e', 1, 10), 7427466391)
        

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

    test_n_ten_digit_prime (__main__.TestNotebook) ... ok
    
    ----------------------------------------------------------------------
    Ran 1 test in 0.175s
    
    OK





    <unittest.main.TestProgram at 0x7fe6ee223390>



2336345d6b7d77ab0c2898e7f3e12ee75c573769
ipynb
Jupyter Notebook
_notebooks/2021-09-17-823HW2_Li_Candice.ipynb
sl679/Candice_Li_823_blog
98f81bb7803de819555d13f5352c474558b0fcdf
Apache-2.0
_notebooks/2021-09-17-823HW2_Li_Candice.ipynb
sl679/Candice_Li_823_blog
98f81bb7803de819555d13f5352c474558b0fcdf
Apache-2.0
_notebooks/2021-09-17-823HW2_Li_Candice.ipynb
sl679/Candice_Li_823_blog
98f81bb7803de819555d13f5352c474558b0fcdf
Apache-2.0
Qwen/Qwen-72B
1. YES
2. YES