# 823 HW2
## https://yiyangzhang2020.github.io/yz628-823-blog/


## Number theory and a Google recruitment puzzle
### Find the first 10-digit prime in the decimal expansion of 17π.
### 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π. First solve sub-problems (divide and conquer):


### -------------------------------------------------------------------------------------------------------
### Write a function to generate an arbitrary large expansion of a mathematical expression like π.
#### (Hint: You can use the standard library `decimal` or the 3rd party library `sympy` to do this)


### For the first function, I used the sympy library (mpmath). Since the function wasn't outputting enough decimal places, I set the mp.dps as 1000. 
### This function has two input conditions to check, either pi(π) or e(euler number). Next, I set a multiplier and multiply them by it. Then I set the precision criterion to get the number of digits after the decimal wanted and turn it into a string. This creates the decimal expansion of a given number. 


```python
import math
try:
    from sympy.mpmath import mp
except ImportError:
    from mpmath import mp
mp.dps=1000

def create_expansion(precision,number,multiplier):
     '''
    this function takes a number with a multiplier and outputs its decimal expansion with a specific number of decimals 
    
    input: 
    precision, number of decimals wanted
    number, number to be expanded('pi' or 'e')
    multiplier, multiplier of the number to be expanded
    
    returns: an string of decimal expansion of the input number
    '''
    #check if number is pi
    if number =='pi':
        #create a string of the number(multiplied by the multiplier) expansion with precision as number of decimals
        str_pi = str(( multiplier*mp.pi)).replace('.','')[0:precision]
        return(str_pi)
    #check if number is e
    elif number =='e':
        str_e = str(( multiplier*mp.e)).replace('.','')[0:precision]
        return(str_e)

#type either 'pi' or 'e' for number in create_expansion function

#print(create_expansion(50,'pi',17))
#print(create_expansion(25,'e',1))
```

### Unit test of create_expansion function:


```python
import unittest

class TestNotebook(unittest.TestCase):
    
    def test_create_expansion(self):
        """test the expansion of the number we want"""
        self.assertEqual(create_expansion(5,'pi',1),str(31415))
       
   
unittest.main(argv=[''], verbosity=2, exit=False)
```

    test_create_expansion (__main__.TestNotebook)
    test the expansion of the number we want ... ok
    
    ----------------------------------------------------------------------
    Ran 1 test in 0.001s
    
    OK





    <unittest.main.TestProgram at 0x7f8427f6b950>



### -------------------------------------------------------------------------------------------------------
### - Write a function to check if a number is prime. Hint: See Sieve of Eratosthenes

### For this function, the first criterion I set is to check if the given number is 1 or not. If it is 1, then it is not a prime number. 
### Next we check if the given number is 2 or not. If it is 2, then it is a prime number.
### Then we check if the given number can be divided by 2, if so, it is an even number, thus it is not a prime number.
### Lastly, we check from 3 to the positive square root of x so that it only iterate a portion of X values. The step is 2 so no even number other than 2 will participate in this iteration. 
### This function reduces the run time complexity dramatically from a function without the above steps. 


```python
import math
def IsPrimeNumber(x):
    '''
    this function takes an input number and test whether it is a prime number or not
    and outputs an answer
    x: int, input to be tested
    returns: an answer (True or False)
    '''
    # exclude 1 which is not prime
    if x == 1:
        return False
    # take out 2 as a base case
    elif x == 2:
        return True
    elif x % 2 == 0:
        return False
    else:
        # iterate through 3 to the positive square root of x to see if x can be divided by any, step is 2 which excludes all even number.
        for y in range(3, int(math.sqrt(x) + 1), 2):
            # if x can be divided, then x is not prime
            if x % y == 0:
                return False
    # if x can not be divided, then x is a prime number
    return True
```

### Unit test of IsPrimeNumber function:


```python
class TestNotebook(unittest.TestCase):
    
    def test_IsPrimeNumber(self):
        """test IsPrimeNumber"""
        self.assertFalse(IsPrimeNumber(1))
        self.assertTrue(IsPrimeNumber(2))
        self.assertFalse(IsPrimeNumber(51))
        self.assertTrue(IsPrimeNumber(1373))
        self.assertFalse(IsPrimeNumber(33333))
        
unittest.main(argv=[''], verbosity=2, exit=False)
```

    test_IsPrimeNumber (__main__.TestNotebook)
    test IsPrimeNumber ... ok
    
    ----------------------------------------------------------------------
    Ran 1 test in 0.001s
    
    OK





    <unittest.main.TestProgram at 0x7f84390c1d10>



### -------------------------------------------------------------------------------------------------------
### - Write a function to generate sliding windows of a specified width from a long iterable (e.g. a string representation of a number)

### Then we have the window function which generates sliding windows of a specified width from a long iterable. This one is pretty straight forward, it returns a list of sliding windows(substrings of the input string). One interesting part I did in this function is that I added a list called 'seen' which records every slinding windows(substrings) we have seen so we will not have repeated slinding windows(substrings) in the output list(non_repeated). This will reduce the run time complexity since a lof of redundant values will be checked later if the specified width is too small. 


```python
def window(seq, width):
    '''
    this function takes an input string and returns all the substrings with the length wanted
    seq: str, input string to be sliced into 'windows'
    width: length of windows wanted
    returns: all the substrings(windows) with the length wanted(width)
    '''
    #exclude the number before the decimal
    seq=seq[1:]
    #create two lists, seen and non_repeated
    seen, non_repeated =[], []
    #iterate through the input string 
    for i in range(0,len(seq)-(width-1)):
        #create windows of given width
        t = seq[i:i+width]
        #excluded repeated windows
        if t not in seen:
            #collect non-repeated windows
            non_repeated.append(t)
        #collect repeated windows as seen windows
        seen.append(t)
    #return a list of non-repeated windows
    return list(non_repeated)

```


```python
print(window(str(12345678), 4))
```

    ['2345', '3456', '4567', '5678']


### Unit test of window function:


```python
class TestNotebook(unittest.TestCase):
    
 def test_window(self):
    """test window."""
    self.assertEqual(window(str(12345678), 4), ['2345', '3456', '4567', '5678'])
        
unittest.main(argv=[''], verbosity=2, exit=False)
```

    test_window (__main__.TestNotebook)
    test window. ... ok
    
    ----------------------------------------------------------------------
    Ran 1 test in 0.001s
    
    OK





    <unittest.main.TestProgram at 0x7f8427f0f710>




### -------------------------------------------------------------------------------------------------------
### Now use these helper functions to write the function that you need.
### Write a unit test for this final function, given that the first 10-digit prime in the expansion e is 7427466391.
### Finally, solve the given problem.


### This function uses all of the helper functions I wrote above. 
### It iterates through the list of numbers generated by the window function from the string of the expansion of the given number generated by the create_expansion function, and then checks whether every number of this list is a prime number using the IsPrimeNumber function. 
### Lastly, it returns the first prime number of the expansion with the wanted length of digits. 


```python
def give_prime_expansion(digits_of_number, input_number, multiplier, length_of_prime):
    '''
    this function takes the digits of number, an input number('pi' or 'e'), a multiplier and the length of prime number we want, returns the first prime number in the expansion.
    digits_of_number: the number of decimal digits
    the input_number: pi or e
    multiplier: a multiplier of the input number
    length_of_prime: the length of the prime number we want 
    returns: the first prime number in the decimal expansion of the input number
    '''
    #iterte through the list of windows of numbers
    for numbers in window(create_expansion(digits_of_number,input_number,multiplier),length_of_prime):
        #check if the number is prime
        if IsPrimeNumber(int(numbers)):
            #output the number we want
            print(f"The first {length_of_prime}-digit prime number in the decimal expansion of {multiplier} {input_number} is: ")
            return(int(numbers))
            break

```

### Thus we can find the first 10-digit prime in the decimal expansion of 17π.


```python
#example
print(give_prime_expansion(99,'pi',17,10))
```

    The first 10-digit prime number in the decimal expansion of 17 pi is: 
    8649375157


### Unit test of give_prime_expansion function:


```python
class TestNotebook(unittest.TestCase):
    def test_give_prime_expansion(self):
        """test test_give_prime_expansion ."""
        self.assertEqual(give_prime_expansion(120,'e',1,10), 7427466391)
        self.assertEqual(give_prime_expansion(99,'pi',1,5), 14159)
   
unittest.main(argv=[''], verbosity=2, exit=False)
```

    test_give_prime_expansion (__main__.TestNotebook)
    test test_give_prime_expansion . ... 

    The first 10-digit prime number in the decimal expansion of 1 e is: 
    The first 5-digit prime number in the decimal expansion of 1 pi is: 


    ok
    
    ----------------------------------------------------------------------
    Ran 1 test in 0.008s
    
    OK





    <unittest.main.TestProgram at 0x7f8427f19d90>




```python

```


```python

```

8039d14c6774d3a80550c307fbbf2bc4bf618ace
ipynb
Jupyter Notebook
_notebooks/2021-09-17-Yiyang-Zhang-823-HW2.ipynb
yiyangzhang2020/yz628-823-blog
12ea3947c3e2f0fb0eb5d5acc4c1baf8e4954aec
Apache-2.0
_notebooks/2021-09-17-Yiyang-Zhang-823-HW2.ipynb
yiyangzhang2020/yz628-823-blog
12ea3947c3e2f0fb0eb5d5acc4c1baf8e4954aec
Apache-2.0
_notebooks/2021-09-17-Yiyang-Zhang-823-HW2.ipynb
yiyangzhang2020/yz628-823-blog
12ea3947c3e2f0fb0eb5d5acc4c1baf8e4954aec
Apache-2.0
Qwen/Qwen-72B
1. YES
2. YES