Basic Math in Programming

Fibonacci Sequence

The Fibonacci sequence in math is defined as

\[F_n = F_{n-1} + F_{n-2}\]

In Python, we can easily generate a series of Fibonacci numbers up to a certain number \(N\). One way to do this is with dynamic programming:

1
2
3
4
5
6
7
8
9
10
11
12
13
14

def fibonacci_numbers(N):
  if (N < 3):
    return 1
  p1 = 1
  p2 = 1
  for i in range(3, N+1):
    temp = p1
    p1 = p2
    p2 = temp + p2
  return p2

fibonacci_list = [fibonacci_numbers(x) for x in range(1, 10)]

print(fibonacci_list)

As the numbers get larger, the values of the Fibonacci sequence increases exponentially. What if we want to only get the last digit of the value?

1
2
3
4
5
6
7
8
9
10
11
12
13

def fibonacci_numbers(N):
  if (N < 3):
    return 1
  p1 = 1
  p2 = 1
  for i in range(3, N+1):
    temp = p1
    p1 = p2 % 10
    p2 = (temp + p2) % 10
  return p2


print(fibonacci_numbers(331))

By modding every value by 10, we make sure that we only keep the last digit of the values. This not only saves space, but also speeds up the program.

LCM and GCD

GCD can be found using Euclid’s GCD algorithm.

1
2
3
4
5
6
7
8
9
10
11

def GCD(x, y):
  if (x < y):
    x, y = y, x
  diff = x % y
  while (diff > 0):
    diff = x % y
    x = y
    y = diff
  return x

GCD(120, 200)

LCM can be found with the property that \(GCD * LCM = x * y\).

1
2
3
4
5
6
7
8
9
10
11
12

def LCM(x, y):
  mult = x * y
  if (x < y):
    x, y = y, x
  diff = x % y
  while (diff > 0):
    diff = x % y
    x = y
    y = diff
  return mult//x

LCM(120, 200)