# Python Number Theory 02 - Sequences
This tutorial demonstrate the generation of <br>
- Aliquot Sequence, <br>
- Fibonacci Sequence, and <br>
- Hailstone Sequence

## Example 01 - Aliquot Sequence

### Part (a)
Write a function for summing the proper divisor (excluding the number itself) of the input.


```python
def division_sum(r):
    x = 0
    for i in range(1,r):
        if (r % i == 0):
            x = i + x
    return x
```


```python
# Testing Cell
division_sum(6)
```




    6



### Part (b)

Let $\sigma(x)$ be a function which returns the sum of proper divisor of $x$. (Note: $\sigma(0) = 0$) The Aliquot Sequence $(s_n)$ with positive integer $k$ is defined as followed:
- $s_0 = k$
- $s_{n+1} = \sigma(s_n)$ for all $n \geq 0$.

Write an aliquot sequence function that returns intermediate values, and terminates either when 'max_iterations' has been reached or when it encounters a value that has occurred before.


```python
def aliquot(r,max_iteration):
    rlist = [r]
    for i in range(max_iteration):
        r = division_sum(r)
        if r in rlist:
            break
        else:
            rlist.append(r)
    return rlist
```


```python
# Test
aliquot(24,20)
```




    [24, 36, 55, 17, 1, 0]



## Example 02 - Fibonacci Sequence
The Fibonacci Sequence $F_n$ is defined as followed:
- $F_1 = F_2 = 1$
- $F_{n+2} = F_{n+1} + F_n$ for $n \geq 1$

### Part (a)
Write a iterative version of 'fibonacci' function which inputs positive integers $r$ and outputs a list of $F_1, F_2, ... F_r$.


```python
def fibonacci1(r):
    if r == 1: # Base Case 1
        xlist = [1]
    elif r == 2: # Base Case 2
            xlist = [1,1]
    else:
            #Initialization
            xnminus1 = 1
            xnminus2 = 1
            xlist = [1,1]
            
            #Loop
            for i in range(r-2):
                x = xnminus1 + xnminus2
                xlist.append(x)
                xnminus2 = xnminus1
                xnminus1 = x
    return xlist
```

### Part (b)
Write a recursive function called 'fibonacci_recpair' that, given a positive integer $r$, returns the tuple $(F_{r-1}, F_r)$.
Hence write a version of 'fibonacci' function which calls 'fibonacci_recpair' and return $F_r$.


```python
# Fibonacci Number (Recursion with List)
def fibonacci_recpair(r):
    # Base case
    if r==1:
        return (0,1)
    elif r==2:
        return (1,1)
    
    # Recursive Step
    else:
        pair = fibonacci_recpair(r-1)
        return (pair[1], pair[0]+pair[1])
```


```python
# Fibonacci Function
def fibonaccir(r):
    return fibonacci_recpair(r) [1]
```

### Part (c)
Using same idea, Write a recursive version of 'fibonacci' function which inputs positive integers $r$ and output $F_1, ..., F_r$.


```python
# Recursion
def fibonacci2(r):
    # Base Case
    if r==1:
        return [1]
    elif r==2:
        return [1,1]
    
    # Recursive Step
    else:
        xlist = fibonacci2(r-1)
        xlist.append(xlist[(r-1)-1] + xlist[(r-2)-1])
        return xlist
```

### Part (d)
In fact we can use sympy module to solve the recurrence relation. Using the solution of recurrence relation we could find a list of $F_1, ..., F_r$ given $r$. 


```python
# Setup
from sympy import symbols, Function, rsolve
n, k = symbols('n k') # For defining variables 'n' and 'k'
f = Function('f') # For defining functions
```


```python
# Defining recurrence relation and solve it
relation = f(n) - f(n-1) - f(n-2)  # Write the recurrence relation as '...' = 0 and let the input be '...'
sol = rsolve(relation, f(n), {f(1):1, f(2):1}) # Initial Condition is given as dictionary with key 'f(n)'
print(sol)
```

    sqrt(5)*(1/2 + sqrt(5)/2)**n/5 - sqrt(5)*(-sqrt(5)/2 + 1/2)**n/5



```python
# Fibonacci Function
def fibonacci3(r):
    xlist = [int(sol.evalf(subs={n:i})) for i in range(1,r+1)]
    return xlist
```

### Part (e)
Explore how time module could measure the running time of a process. Use this module to test the performance of 'fibonacci1' to 'fibonacci3' against each other (both consistency and efficiency).


```python
# Input process_time from time module. This is for finding running time of a process
from time import process_time
```


```python
r = 30
```


```python
# Version 1 (Iteration)
start1 = process_time()
a = fibonacci1(r)
end1 = process_time()
print(a)
print(end1 - start1)
```

    [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040]
    0.0



```python
# Version R (Recursion of List)
tuplef = fibonaccir(r)
print(tuplef)
```

    832040



```python
# Version 2 (Recursion)
start2 = process_time()
b = fibonacci2(r)
end2 = process_time()
print(b)
print(end2 - start2)
```

    [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040]
    0.0



```python
# Version 3 (Solution)
start3 = process_time()
c = fibonacci3(r)
end3 = process_time()
print(c)
print(end3 - start3)
```

    [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040]
    0.203125



```python
# Check Consistency
print(a==b and b==c)
```

    True


### Part (f)
Investigate $\frac{F_{r+1}}{F_r}$ as $r$ increases.


```python
def golden(r):
    flist = fibonacci1(r)
    ratio = [flist[i]/flist[i-1] for i in range(1,r)] 
    return ratio
```


```python
print(golden(40))
```

    [1.0, 2.0, 1.5, 1.6666666666666667, 1.6, 1.625, 1.6153846153846154, 1.619047619047619, 1.6176470588235294, 1.6181818181818182, 1.6179775280898876, 1.6180555555555556, 1.6180257510729614, 1.6180371352785146, 1.618032786885246, 1.618034447821682, 1.6180338134001253, 1.618034055727554, 1.6180339631667064, 1.6180339985218033, 1.618033985017358, 1.6180339901755971, 1.618033988205325, 1.618033988957902, 1.6180339886704431, 1.6180339887802426, 1.618033988738303, 1.6180339887543225, 1.6180339887482036, 1.6180339887505408, 1.6180339887496482, 1.618033988749989, 1.618033988749859, 1.6180339887499087, 1.6180339887498896, 1.618033988749897, 1.618033988749894, 1.6180339887498951, 1.6180339887498947]


## Example 03 - Hailstone Sequence

Define a function $f$ for positive integer $n$. If $n$ is even, then $f(n) = \frac{n}{2}$, otherwise $f(n) = 3n + 1$. The hailstone sequence $(a_n)$ for with positive integer $k$ is defined as followed:
- $a_0$ = k
- $a_{n+1} = f(a_n)$ for $n \geq 0$

It is observed that $k = 1$, the sequence will be repeating in the pattern $1, 8, 4, 2, 1, 8, 4, 2, 1, ...$, and thus we can terminate the hailstone sequence when $a_n$ = 1. Write a hailstone sequence function that returns intermediate values, and terminates either when max_iterations has been reached or the value 1 is encountered. (Thinking question: will the sequence always end at 1?)


```python
def hailstone(n, max_iterations):
    thelist = [n]
    for i in range(max_iterations):
        if n%2 == 0:
            n = n//2
        else:
            n = 3*n + 1
        thelist.append(n)
        if n == 1:
            break
    return(thelist)
```


```python
# Test
hailstone(7,20)
```




    [7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]



cfcf7ee58fc3f33a5f8f0d93003cf540b10a4efd
ipynb
Jupyter Notebook
M1C (Python)/M1C-Number-Theory/Python Number Theory 02 - Sequences.ipynb
ImperialCollegeLondon/Random-Stuff
219bc0e26ea6f5ee7548009c849959b268f54821
MIT
2021-05-16T04:08:34.000Z
2021-11-27T12:56:10.000Z
M1C (Python)/M1C-Number-Theory/Python Number Theory 02 - Sequences.ipynb
ImperialCollegeLondon/Random-Stuff
219bc0e26ea6f5ee7548009c849959b268f54821
MIT
M1C (Python)/M1C-Number-Theory/Python Number Theory 02 - Sequences.ipynb
ImperialCollegeLondon/Random-Stuff
219bc0e26ea6f5ee7548009c849959b268f54821
MIT
2020-03-31T00:23:13.000Z
2020-05-13T15:01:46.000Z
Qwen/Qwen-72B
1. YES
2. YES