Math functions

A few functions that aren’t contained in the math module – I’ll continue to add to these as time permits.

A recursive implementation of Euclid’s algorithm to find the greatest common divisor of two numbers:

def gcd(a,b):
  """
  pre: a, b +ve integers
  calcalates gcd by Euclid
  """
  c = max(a, b)
  d = min(a, b) 
  if c%d == 0:
    return d
  else:
    return gcd(d, c%d)

Using the gcd function to return the least common multiple:

def lcm(a, b):
  """
  pre: a, b +ve integers
  returns least common multiple of a and b
  """
  return a*b/gcd(a, b)

A function to return the product of all numbers in a list:

def product(aList):
  """
  pre: aList a list of integers
  returns: a product of all terms in the list
  """
  prod = 1
  for x in aList:
    prod *= x
  return prod

Using the product function to calculate the number of combinations of n items from a set of size m:

def choose(m, n):
  """
  pre: m, n +ve integers
  pre: m > n
  returns: m choose n
  """
  return product(range(max(n, m-n) + 1, m + 1))/product(range(1, min(n, m-n) + 1))

A recursive factorial function:

def fact(n):
  """
  pre: n +ve integer
  returns: n!
  """
  if n > 1:
    return n * fact(n - 1)
  else:
    return 1

A generator for the Fibonacci sequence:

def gen_Fib():
  """pre: a, b, below +ve integers
  returns: generator with an iterator to obtain the Fibonacci sequence
  """
  a = 0
  b = 1
  while True:
    yield b
    a, b = b, a + b

A one-liner to find a digital sum:

def sum_digits(n):
  """
  pre: n +ve integer
  returns: sum of digits in n
  """
  return sum([int(digit) for digit in str(n)])

A prime test:

def is_prime(n):
  """
  pre: n +ve integer
  returns: true if n is prime, else false
  """
  import math
  for i in range(2, int(math.sqrt(n)) + 1):
    if n % i == 0:
      return False
  return True

A function to return the list of all divisors of a number:

def divisors(n):
  """
  pre: n +ve integer
  returns: a list of all divisors of n
  """
  import math
  result = []
  for i in range(1, int(math.sqrt(n)) + 1):
    if n % i == 0:
      result.append(i)
      if i != n/i:
        result.append(n/i)
  return len(result)