Functions
A huge portion of coding involves writing concise, thoughtful, self-contained functions. Functions are reusable program structures that function semiautonomously. If I find a function particularly useful, then I might abstract out of a program entirely and place it in a library.
We write functions for a variety of reasons. They almost like algebraic objects that we factor out of code. We will explore a variety of functions in this section and start thinking about what it means to design thoughtful, well-written code. A big portion of the answer to this is to create very precise functions with a limited scope that takes specific variables and that hands off exactly what is expected.
1. A GCD function
The GCD or greatest common divisor is the largest common factor shared by a pair of integers. It has a host of applications across many areas of mathematics and computer science. Here, we will write a function extract the GCD from a list of integers. We will use a built in GCD function to extract the GCD of two numbers and apply that to our list of numbers in order to obtain the GCD of the entire list. We will consider several different methods in which we could accomplish this tast:
import math
def GCD(integers):
length_of_list = len(integers)
counter = 0
list_of_gcds = []
while (counter < length_of_list):
for i in range(len(integers)):
if(i != counter): list_of_gcds.append(math.gcd(integers[counter], integers[i]))
counter = counter + 1
print("The GCD of", integers, " is", min(list_of_gcds))
GCD([4235, 49, 539])
GCD([10000, 20, 3000, 40, 500, 100, 1000])
GCD([48, 49, 50, 51, 52])
2. A Function that Explores Formatting and Towers
Here, we construct a program that creates summation towers of height x. Each row will contain 2x – 1 elements and the first row contains a zero in all places except the middle place where it contains a 1. Each subsequent row contains elements such that they are the sum of the elements above them with the element directly above multiplied by m. In other words, $a_{i,j} = a_{i-1,j-1} + ma_{i-1,j} + a_{i-1,j+1}$. The elements are then equispaced to line up ones, tens, ect. in a column.
def tos(x, m):
rows, cols = (x, 2*x-1)
arr = [[0 for i in range(cols)] for j in range(rows)]
arr[0][x-1] = 1
arr[x-1][0] = 1
arr[x-1][cols-1] = 1
for i in range(1,rows):
for j in range(1, cols - 1):
arr[i][j] = arr[i-1][j-1] + m*arr[i-1][j] + arr[i-1][j+1]
for i in range(rows):
for j in range(cols):
if arr[i][j] == 0:
arr[i][j] = ' '
print_list = list()
for i in range(rows-1):
row = ""
for j in range(cols):
digit_length = len(str(arr[rows-1][j]))-len(str(arr[i][j]))
for k in range(digit_length):
row = row + ' '
row = row + str(arr[i][j]) + ' '
print_list.append(row)
row = ""
for j in range(cols):
row = row + str(arr[x-1][j]) + ' '
print_list.append(row)
for x in range(len(print_list)):
print(print_list[x])
print()
tos(4,1)
print()
tos(5,3)
print()
tos(6,4)
3. Write a function that efficiently determines if n is prime and returns a boolean.
def isPrime(n) :
if (n < 2) :
return False
bound = int(n**.5) + 1
for i in range(2, bound) :
if (n % i == 0) :
return False
return True4. Using the Function you wrote in Prompt 3, write a function that yields the mobius function, $\mu(n)$ applied to n.
The blue code below would be the portion you would have written in section 3. The red code checks the numbers 1 to 25 and introduces a useful feature of python 3: print formatting statements. Variables will replace the curly braces {} in the order listed in the format command. Modular division is very fast in most computer programming languages and the program below leverages that. Notice too, that I do my best never to invoke unnecessary libraries.
def isPrime(n) :
if (n < 2) :
return False
bound = int(n**.5) + 1
for i in range(2, bound) :
if (n % i == 0) :
return False
return True
def mobius(N) :
if (N == 1) :
return 1
p = 0
for i in range(1, N + 1) :
if (N % i == 0 and isPrime(i)) :
if (N % (i * i) == 0) : return 0
else : p = p + 1
if(p % 2 != 0) : return -1
else : return 1
for N in range(1, 26):
print ("Mobius defs M(N) at N = {} is: {}" . format(N, mobius(N)));5. $\Sigma_{i=1}^N \mu(i) = M(N)$ is typically referred to as the Mertens function. Now, leverage the code you have written to create an array of data of values of $M(N)$ where the $N^{th}$ element is the value of $M(N)$..
def isPrime(n) :
if (n < 2) :
return False
bound = int(n**.5) + 1
for i in range(2, bound) :
if (n % i == 0) :
return False
return True
def mobius(N) :
if (N == 1) :
return 1
p = 0
for i in range(1, N + 1) :
if (N % i == 0 and isPrime(i)) :
if (N % (i * i) == 0) : return 0
else : p = p + 1
if(p % 2 != 0) : return -1
else : return 1
def mertens(N):
sum = list()
sum.append(mobius(1))
for i in range(0, int(N)):
value = int(sum[i]) + int(mobius(i+2))
sum.append(value)
return sum
sum = mertens(100)
print(sum)We can see the progress of our program denoted in the coloring of the blocks of code. Blue is our first function, orange our next, and black our newest function. The code in red is used just to test that our is performing as expect.
Output:
[1, 0, -1, -1, -2, -1, -2, -2, -2, -1, -2, -2, -3, -2, -1, -1, -2, -2, -3, -3, -2, -1, -2, -2, -2, -1, -1, -1, -2, -3, -4, -4, -3, -2, -1, -1, -2, -1, 0, 0, -1, -2, -3, -3, -3, -2, -3, -3, -3, -3, -2, -2, -3, -3, -2, -2, -1, 0, -1, -1, -2, -1, -1, -1, 0, -1, -2, -2, -1, -2, -3, -3, -4, -3, -3, -3, -2, -3, -4, -4, -4, -3, -4, -4, -3, -2, -1, -1, -2, -2, -1, -1, 0, 1, 2, 2, 1, 1, 1, 1, 0]
6. Use plotly (import matplotlib.pyplot as plt) to plot the first 10,000 values of .
import matplotlib.pyplot as plt
def isPrime(n) :
if (n < 2) :
return False
bound = int(n**.5) + 1
for i in range(2, bound) :
if (n % i == 0) :
return False
return True
def mobius(N) :
if (N == 1) :
return 1
p = 0
for i in range(1, N + 1) :
if (N % i == 0 and isPrime(i)) :
if (N % (i * i) == 0) : return 0
else : p = p + 1
if(p % 2 != 0) : return -1
else : return 1
def mertens(N):
sum = list()
sum.append(mobius(1))
for i in range(0, int(N-1)):
value = int(sum[i]) + int(mobius(i+2))
sum.append(value)
return sum
N = 10000
x = range(1,N+1)
y: List[int] = mertens(N)
plt.scatter(x, y, s = .5)
plt.show()
