# -*- coding: utf-8 -*-
# ---
# jupyter:
#   jupytext:
#     text_representation:
#       extension: .py
#       format_name: light
#       format_version: '1.5'
#       jupytext_version: 1.14.4
#   kernelspec:
#     display_name: SageMath 9.4
#     language: sage
#     name: sagemath-9.4
# ---

# <!--<img src="./images/aims-za-logo.jpeg" alt="drawing" style="width:400px;"/> -->
# <h1 style="text-align: center;"><a title="EMS-AIMS-ZA-2021-22" href="https://sites.google.com/aims.ac.za/sage-2021-22/">Experimental Mathematics Using SageMath — AIMS-ZA-2021-22</a></h1>
#
#
# ## Instructors: 
#
# * **<NAME>**
#
# * **<NAME>**

# ## Homework Assignment (due Saturday 6th of November 2021 at 21:00 GMT+2)  <a class="anchor" id="homework-assignment-01"></a>
#
#
# Instructions for homework assignments: 
# - You must answer all the exercises in this notebook. Make sure to rename this notebook by deleting the word `your_name` and put putting your name there. So for example, if my name is `Evans`, then I will rename this notebook to be `ems_2021-22_assignment_01_evans`.  
# - ALL CODE MUST BE EXPLAINED. That means you should have at least one English sentence to explain each line of code that you write. This may be in a form of a comments or in a paragraph after each computation in your Jupyter notebook. 
# - Similarly, do not simply write your explorations as lists of numbers, but write explanations of what you tried, what didn't work and what worked.
# - Do NOT use internet resources for the exploration; for help with _SageMath_ or _Python_ you may search the internet, of course. You are also welcome to ask the lectures or any of the tutors.
# - The starred (*) exercises are more important; you should be working on them early and often. To pass the course you should try to do all the starred exercises.
#
# The outline of this notebook is as follows:
#
# ## Table of Contents: <a class="anchor" id="assignment-01-toc"></a>
# * [<font color=#AAFF00>Exercise 01</font>](#exercise-01)
# * [<font color=#AAFF00>Exercise 02</font>](#exercise-02)
# * [<font color=#AAFF00>Exercise 03</font>](#exercise-03)
# * [<font color=#AAFF00>Exercise 04</font>](#exercise-04)
# * [<font color=#AAFF00>Exercise 05</font>](#exercise-05)
# * [<font color=#AAFF00>Exercise 06</font>](#exercise-06)
# * [<font color=#AAFF00>Exercise 07</font>](#exercise-07)
# * [<font color=#AAFF00>Exercise 08</font>](#exercise-08)
# * [<font color=#AAFF00>Exercise 09</font>](#exercise-09)
# * [<font color=#AAFF00>Exercise 10</font>](#exercise-10)
# * [<font color=#AAFF00>Exercise 11</font>](#exercise-11)
# * [<font color=#AAFF00>Exercise 12</font>](#exercise-12)
# * [<font color=#AAFF00>Exercise 13</font>](#exercise-13)
# * [<font color=#AAFF00>Exercise 14</font>](#exercise-14)
# * [<font color=#AAFF00>Exercise 15</font>](#exercise-15)

# ## <font color=#AAFF00>Exercise 01</font> <a class = "anchor" id="exercise-01"></a>
#
# Plot `sin(x)` from $0$ to $\pi$ along with its third derivative on the same set of axes, in a different color.  Make the vertical axes range from $-4$ to $+4$.

P = plot(sin(x) ,(0,pi), color = 'red', legend_label =["Graph of sin(x)"]) + plot(-1*cos(x),(0,pi), color='blue', axes_labels =["x-axis","y-axis"],legend_label =["Graph of third derivative of sin(x)"])#This creates a plot for sin(x) + third derivate
P.show(ymin=-4, ymax=4) #This shows the graphs and thier vertical axes range

# ## <font color=#AAFF00>Exercise 02</font> <a class = "anchor" id="exercise-02"></a>  
#
# Create a nontrivial $5 \times 5$ diagonal matrix in _SageMath_ using a special command for it, and verify that the diagonal entries are the same as the eigenvalues of the matrix.  Confirm that the eigenvectors are just the elementary basis vectors.

matrix_5_by_5 = diagonal_matrix((2,5,9,3,7)); #This code creates a nontrivial  5×5 
matrix_5_by_5

matrix_5_by_5.diagonal()==matrix_5_by_5.eigenvalues() #This code verifies that the diagonal entries are the same as the eigenvalues of the matrix

# ## <font color=#AAFF00>Exercise 03</font> <a class = "anchor" id="exercise-03"></a>  
#
# For each of the numbers $n=10, 100, 1000, 10000, 100000, 1000000, 10000000$ and $100000000$ compare the number of primes less than n to the value of `n/log(n)`.  You just need to make a table or write some sentences on what your observe.  (Here, `log` is the natural logarithm and you may want to read the documentation on the _SageMath_ function `table` in order to tabulate your results.)

# +


def compare(n) : #defining the function for numbers of prime and values of nlog(n)
    prime_number=[i for i in range (n) if is_prime(i)] # number of integers n which are prime
    primes_lens = len(prime_number) #counting the length of prime numbers less that list n
    log_value = n/log(n) #computing the value of n/log(n)


    return primes_lens, log_value #return the computed value of n/log(n) and the length of prime number 
# -

n_list = [10, 100, 1000, 10000,100000,1000000] 
for k in n_list :
    print("{}\t \t{}".format(k, compare(k))) 



# ## <font color=#AAFF00>Exercise 04</font> <a class = "anchor" id="exercise-04"></a>  
# Solve any differential equation using _SageMath_. (Hint: Read the documentation [here](https://doc.sagemath.org/html/en/reference/calculus/sage/calculus/desolvers.html), but you are <strong>NOT</strong> allowed to use the examples in the documentation, try to formulate your own.)

# The differential equation I am to solve is $ \frac{dx}{dy} = \frac{xy^{2}-cos(x)sin(x)}{y(1-x^{2})}$

x = var('x') #This code creates a variable of x to use in the differential equation
y = function('y')(x) #This code creates a function f(x) to solove the differential
show(diff (y , x ) ==( x * y ^2 - cos ( x ) * sin ( x ) ) /( y *(1 - x ^2) ))
sol = desolve ( diff (y , x ) ==( x * y ^2 - cos ( x ) * sin ( x ) ) /( y *(1 - x ^2) ) ,y ) #desolve is use to solve the differental declare as diff inside it.
print("The solution for the differential equation is:",show(sol)) #This just show the output of the solution of the differential equation


# ## <font color=#AAFF00>Exercise 05</font> <a class = "anchor" id="exercise-05"></a>  
# (*) Write a formal proof for the following statements: 
#    - Suppose $a, b, c$ are real numbers and $a > b$. Prove that if $a\,c \leq b\,c$ then $c \leq 0$. 
#    - Prove that for every natural number $n$, $3$ divides $(-n + n^3)$.

# For the proof $a, b, c$ are real numbers and $a > b$. Prove that if $a\,c \leq b\,c$ then $c \leq 0$. \
# We are given the information that $a, b, c$ are real numbers and $a > b$. \
# We can rewrite the following proof in the following form $P: a\,c \leq b\,c \\ Q: c \leq 0$ \
# $P \implies Q ~,~ a\,c \leq b\,c \implies c \leq 0$ \
# I will solve this by using contrapositive which states $\lnot Q \implies \lnot P \\ c > 0 \implies ac > bc$ \
# Since $c>0$ which literally means it is a positive number so we are going to use the given information $a > b$ without changing the inequality sign. I am going to multiply both sides of $a > b$ with $c$. \
# It will give us $ac > bc$ which proves  $~~ \lnot Q \implies \lnot P \\ \therefore P \implies Q~ \text{is true,} ~ a\,c \leq b\,c \implies c \leq 0 ~ \blacksquare$

# Prove that for every natural number $n$, $3$ divides $(-n + n^3)$. 
#
# If I test for $n = 1~ \text{we get}~ 0 ~\text{which is not divisible with 3} \\ \text{for}~ n = 2 ~ \text{we get}~ -2+2^3 = 6 = 3 \times 2 ~\text{; so it is divisible by}~3$ \
#  $\text{We now know that}~-n + n^3 \text{ for n=1 does not apply so we start at}~ n \geq 2$ \
#  $\text{if}~ -n + n^3 \text{ is divisble by 3 I can rewrite it in a form}~ -n + n^3 = 3d~ \text{ where d is an integer}$ \
# $\text{Since we checked for}~ n=2 \\ \text{We are going to assume that is it true for}~ n=k \text{ ;that is our induction hypothesis i.e } -k + k^3 = 3d$ \
# $\text{for } n = k+1$
#
# \begin{align*}
# -(k+1)+(k+1)^3 & = -(k+1)+k^3+3k^2+3k+1 \\
#                & = (-k+k^3)+3k^2+3k \\
#                & = 3d + 3k^2+3k ~ \text{, using the assumption} \\
#                & = 3(d +k^2 +k) 
# \end{align*}
# $ \therefore \text{Principle of induction implies that for } n \geq 2 ~~ (-n + n^3) \text{ is divisible by 3, for n natural nmbers}$

# ## <font color=#AAFF00>Exercise 06</font> <a class = "anchor" id="exercise-06"></a>  
#
# (*) Suppose $n$ is an integer greater than $1$ and $n$ is not prime. Then $-1 + 2^n$ is not prime.
#    - Identify the hypothesis and conclusion of the theorem. Are the hypothesis true when $n = 6$? What does the theorem tell you in this instance? Is it right?
#    - What can you conclude from the statement in the case $n = 15$? Check directly that this conclusion is correct.
#    - What can you conclude from the statement in the case $n = 29$?
#    
# Hint: Read the PDF document on proof methods that I sent you. You may take a look at <strong>Example 3.1.2</strong> on pages 88 and 80. In that example, what is referred to as <em>Givens</em> and <em>Goal</em> are the <em>hypothesis</em> and <em>conclusion</em> respectively in the statement of this exercise, <a href="#exercise-06"><b><font color=#AAFF00>Exercise 06</font></b></a>.

# We are given a hypothesis $n$ is an integer greater than $1$ and $n$ is not prime. \
# Our conclusion statement is in a form $P \implies Q$, where $P$ is the statement is $n$ is not prime and $Q$ is the statement is $-1 + 2^n$ is not prime. \
#  \
# Given : $n$ is an integer greater than $1$ and $n$ is not prime. \
# Goal  : $-1 + 2^n$ is not prime. \
# We assume $P$ and we try to prove $Q$. 
#
# 1. When we test the hypothesis for $n=6$, $6$ is not prime $\implies ~ -1+2^n ~ = -1+2^6=63$, 63 is a not prime. \
# The theorem is true in this case and it is right. \
# 2. When we test the hypothesis for $n=15$, $15$ is not prime $\implies ~ -1+2^n ~ = -1+2^15=32767$, 32767 is a not prime. \
# The conclusion is true for this case.
# 3. When we test the hypothesis for $n=29$, $29$ is prime $\implies ~ -1+2^n ~ = -1+2^29= 536870911$, 536870911 is a not prime. \
# Since $29$ prime the hypothesis false.

# ## <font color=#AAFF00>Exercise 07</font> <a class = "anchor" id="exercise-07"></a>  
#
# (*) Prove that if $a$ divides $x$ and $a$ divides $y$, then $a$ divides $m\,x+n\,y$ for any integers $m,\,n$.  (Don't copy this from somewhere, actually write in your own words!) You may use any of the proof methods we mentioned in class.

# We are given a hypothesis $a$ divides $x$ and $a$ divides $y$. \
# Our conclusion statement is in a form $P \implies Q$, where $P$ is the statement is $a$ divides $x$ and $a$ divides $y$ and $Q$ is the statement is $a$ divides $m\,x+n\,y$ for any integers $m,\,n$. \
#     \
# Given : $a$ divides $x$ and $a$ divides $y$. \
# Goal  : $a$ divides $m\,x+n\,y$ for any integers $m,\,n$. \
# We assume $P$ and we try to prove $Q$. \
#   \
# From the given hypothesis we know that if $a|x ~ \exists$ some integer $m$ s.t $x=ma$, where $m$ is an integer and $a|y ~ \exists$ some integer $n$ s.t $y=na$, where $n$ is an integer. \
# From this information add up $x$ and $y$ which gives \begin{align*} x+y &= am+an \\ & = a(m+n) \\ \therefore a |(m+n) \text{ we know that } a|(x+y) \text{ from the hypothesis} \end{align*}
# In conclusion $ a$ divides $m\,x+n\,y$ for any integers $m,\,n ~ \blacksquare$

# ## <font color=#AAFF00>Exercise 08</font> <a class = "anchor" id="exercise-08"></a>  
#
# (*) Compute the <b>Conductor</b> and <b>Frobenius number</b> of the following pairs: $\{4,\,7\}$, $\{4,\,6\}$, and $\{7,\,9\}$, if they exist.  How many numbers are not writable in each case?

def Frobenius_cents(a,b,n):
    my_coin =[]          #This code will create a list for my coin values
    for x in [0..n]:    #This will loop through n number of times      
        for y in [0..n]:
            f=a*x+b*y
            if f<=100:      
                my_coin.append(f) # we append the possible cents into a list so we camn get better unserstandeing of our values
    return sorted(my_coin)     # here we return a sorted list( ascending order)   



# +
print("For the case 4 and 7 we have {}".format(Frobenius_cents(4,7,10)))

count=0
y=[]
for i in [0..100]:
    if i not in (Frobenius_cents(4,7,10)):
        y.append(i)
        count+=1
print('Numbers that cannot be written using 10 as the bound are {}'.format(y))
print('Total numbers that cannot be written using 10 as the bound are {}'.format(count))

# +
print("For the case 4 and 6 we have {}".format(Frobenius_cents(4,7,10)))

count=0
y=[]
for i in [0..100]:
    if i not in (Frobenius_cents(4,6,10)):
        y.append(i)
        count+=1
print('Numbers that cannot be written using 10 as the bound are {}'.format(y))
print('Total numbers that cannot be written using 10 as the bound are {}'.format(count))

# +
print("For the case 4 and 7 we have {}".format(Frobenius_cents(7,9,10)))

count=0
y=[]
for i in [0..100]:
    if i not in (Frobenius_cents(7,9,10)):
        y.append(i)
        count+=1
print('Numbers that cannot be written using 10 as the bound are {}'.format(y))
print('Total numbers that cannot be written using 10 as the bound are {}'.format(count))
# -

# ## <font color=#AAFF00> Exercise 09</font> <a class = "anchor" id="exercise-09"></a>
#
# (*) Prove that your computation of the conductor for $\{4,\,7\}$ is correct.  Use your own words!

# |n   |$4x+7y$|
# | :------:| :-------:|



# + [markdown] tags=[]
# ## <font color=#AAFF00>Exercise 10</font><a class="anchor" id="exercise-10"></a>
#
# (*) Write a Python function (a function using `def` keyword) in _SageMath_ to list enough numbers for a general pair $\{a,\, b\}$ where $a$ and $b$ are natural numbers to guess the conductor of $a$ and $b$. (And explain it!)

# +
def Frebo_cents(a,b,c):    #This will create a function for our pairs
    s=list()
    for x in [0..c]:         
        for y in [0..c]:
            n=a*x+b*y        # x and y are positive integer numbers
            if n<=100:      
                s.append(n)
    return sorted(s)                #sort the values in order
print(Frebo_cents(7,4,20))     # the values that will be printed all those that are writable which will later 
                            
                                
count=0
w=[]   
#All the numbers that are not writable will be appended in this list. 
# All the numbers that cannot be written will be stored in W and we'll guess our 
# Frobenius number by checking the last number in the list
# Our conductor will be the Frobenius number+1t.
for i in [0..100]:
    if i not in (Frebo_cents(7,4,20)):
        w.append(i)
        count+=1
print('Numbers that cannot be written using {} as the bound are {}'.format(20, w)) # This prints out the the numbers that cannot be written
print('Total numbers that cannot be written using {} as the bound are {}'.format(20, count))
# -

Conductor_Frobenius(3,3,4)

# ## <font color=#AAFF00> Exercise 11 </font> <a class = "anchor" id="exercise-11"></a>  
#
# (*) Make a conjecture for a formula for the conductor and the Frobenius number, given the pair $\{a,\, b\}$.  Also conjecture how many are not writable for the pair $\{a,\,b\}$ in general.  Be sure to write down whatever evidence you have for these conjectures (no code needed).  Just stating a possible formula will not receive full credit, you must actually write about or show your experiments.  You do NOT need a proof.





# ## <font color=#AAFF00>Exercise 12:</font> <a class="anchor" id="exercise-12"></a>
#
# (*) Write a <em>SageMath</em> or a <em>Python</em> procedure with the name `collatz_procedure` using Python's `while` loop construct that implements the [Collatz Problem](https://en.wikipedia.org/wiki/Collatz_conjecture). Your procedure should prints the sequences generated as a list for any positive integer. For example  `collatz_procedure(5)` should print `[5, 16, 8, 4, 2, 1]`.

def collatz_procedure(n):
    '''
    This function takes an arguement of an integer and returns a list of collatz sequence
    '''
    coll_seq = [n] #This creates a list and insert the first element n and the stores the Collatz sequence
    if n < 1:      #Since sequence is trying to approach one it will print out an empty list if 1 is enter but since we store in coll_seq the overall will be 1
       return []   #Since we do not want numbers less than 1 the function will return zero
    while n > 1:        #This creates a while loop with a condition if n is greater than one it will continue with loops.
       if n % 2 == 0:   #This code checks if the n is divisible by 2 without any remainder
         n = n / 2      #As specified in the Collatz function if n is even it will divide it until it gets 1
       else:         
         n = 3 * n + 1  #if n is odd this operation is done until we reach 1
       coll_seq.append(n) #This code appends all the numbers n in the list coll_seq
    return coll_seq       #This return the whole sequence for Collatz
collatz_procedure(3)      #This part test if the code works


# ## <font color=#AAFF00>Exercise 13:</font> <a class="anchor" id="exercise-13"></a>
#
# (*) Write a recursive function with the name `my_fibonacci_number` for the Fibonacci recurrence equation: 
#
# $$F_{n} = F_{n-1} + F_{n-2}, \qquad F_{0} = 1, \quad F_{1} = 1.$$
#
# Your function should return the $n$-th [Fibonacci number](https://en.wikipedia.org/wiki/Fibonacci_number).

# +
def my_fibonacci_number(n):
    """
    This Fibonacci sequence function takes a positive integer argument and
    return an n-th term of the Fibonacci number
    """
    if n <= 1:     #This conditional statement checks if the number n enter is less or equals to 1 then returns 0
        return 0
    elif n ==1:    #In this case if n is 1 the function will return 1 because we do not have f_-1
        return 2
    else:          #This code creates fibonacci start from 1 as specified in the question 
        F_0 = 1
        F_1 = 1
        for i in range(2,n+1): #This code generates a loop  for recussive nature of fibonacci
            F_n = F_0 + F_1    #This updates the value of F_n for every loop
            F_0 = F_1          #This updates F_1 from the previous value
            F_1 = F_n          #This updates F_1 from the previous value
        return F_n             #This returns the n-th term of the Fibonacci number
    
my_fibonacci_number(4)         #This tests out if the code works
# -

# (*) Test your fuction with the following inputs: $n=10,\,50,\,100$. Use the Python function `time` or `timeit` to check the real time or best computing time respectively. You may want to read the help documentation for `time` and `timeit` so you will know how they are used or you can also refer to notebook for the first day.

# +
#for n = 10

timeit("my_fibonacci_number(10)")
# -

#for n=50
timeit("my_fibonacci_number(50)")

# for n = 100
timeit("my_fibonacci_number(100)")

# ## <font color=#AAFF00>Exercise 14:</font> <a class="anchor" id="exercise-14"></a>
#
# 1. (*) Use the _SageMath_ documentation on `Graph` to construct a simple vertex labelled graph and give it the name `my_graph`.
# 2. (*) Apply as at least five methods to the `Graph` object, `my_graph` that you created in part 1.

#Graph
my_graph = Graph({'a':[1,2,8], 'b':[2,4],'c':[1,4]}); #This just creates a simple vertex graph with name my_graph
my_graph

my_graph.add_clique(range(4)); #This method only adds edges in the already made my_graph.
my_graph

my_graph.add_edges( [ (1,6, 5) ]); #This method adds edges 1,6,5 in already made my_graph
my_graph

my_graph.add_vertices([1,6,2]); #This code adds vertices in our graph
my_graph

my_graph.add_cycle(list(range(10, 2))); #This adds a cycle to the my_graph with the given vertices
show(my_graph)

my_graph.add_edge((1, 2), label="label"); #Add an edge from u to v
my_graph.edges(sort=False)


# ## <font color=#AAFF00>Exercise 15: Random walk on graphs</font> <a class="anchor" id="exercise-15"></a> 
#
# (*) Suppose there is a robot standing on one of the vertices of the graph, `my_graph`, that you defined in <a href="#exercise-14"><b><font color=#AAFF00>Exercise 14</font></b></a>. This position can be chosen randomly. Write a python function or a procedure with the name `random_walk_on_graph` that takes a positive integer as input, `number_of_walks` — which is the number of walks made by the robot on the vertices of your graph — and returns a table that records the number of times the robot visited each vertex in your graph. What do you observe about the movement of the robot when `number_of_walks` takes on the values: $100, 1000, 5000$.
#
#
# __Hint__: Read the help documentation on the _SageMath_ functions `choice` and `table`. You may need them in your code. What did you observe from the tabulated data?

# #This code was done with the help of Tebogo Doctor Malatsi who is one of the January intakes

def random_walk_on_graph(my_graph,number_of_walks): #This was with the help of Tebogo who is one of the January intakes
    Dictionary=my_graph.to_dictionary()
    Keys=list(Dictionary.keys()) # Convert the dictionary keys into a list
    start=choice(Keys)      # name will be picked randomly
    List=[start]
    for i in range(number_of_walks):
        y=choice(Dictionary[start])
        if y in Keys:
            List.append(y)
        start=y
        
    Destination_of_robot=[]
    Number_of_visits=[]
    for k in set(List):
        c=List.count(k)
        Destination_of_robot.append(k)
        Number_of_visits.append(c)
    W=table([Destination_of_robot,Number_of_visits],header_column=['Verices','Number of visits'])
    return W
    pass


my_graph = Graph({'a':[1,2,8], 'b':[2,4],'c':[1,4]}); #This just creates a simple vertex graph with name my_graph
my_graph

random_walk_on_graph(my_graph,100)



StarcoderdataJupyterScriptsDedupFiltered