This is the second article discussing the math module from the Python Standard Library. You can find the first about four basic numerical functions here. The articles are organized thematically; functions that are closely related to each other are discussed in the same article.
In this article, we will explore two themes: combinatorics and elementary number theory.
For our purposes, combinatorics is the study of counting the number of ways to rearrange objects. We look at three important ideas:
- combinations,
- permutations, and
- factorials.
Number theory is a subfield of mathematics concerning the properties of integers and rational numbers. Much of elementary number theory studies the divisibility of integers. In this article, we explore two important concepts:
- greatest common divisors, and
- least common multiples.
Combinatorial Functions
The Combination Function math.comb()
math.comb(int n, int k)
The combination function (a.k.a. the binomial coefficient) gives the number of ways of choosing k objects from a collection of n distinct objects, not accounting for different rearrangements of the k objects. For more details on binomial coefficients, see this blog post.
To calculate the number of ways to choose 4 letters from the collection {a,b,c,d,e,f,g,h}, we can use:
import math math.comb(8, 4) # 70
As we see above, the math.comb() function accepts two nonnegative integers parameters. The first parameter is the number of objects in the collection (in the above example, the letters a through h), and the second parameter is the number of objects we choose from the collection.)
The Permutation Function math.perm()
math.perm(int n, int k=None)
A permutation of n elements is the number of ways to rearrange n distinct objects.
For instance, let’s consider the permutation of the letters {a,b,c,d,e}. We will think about putting the five objects in one row.
As a starter, let’s think of how many ways of putting the letters in the pattern edc. In the fourth spot, we can put either a or b. Let’s say we choose a. Then there is only one choice left b in the fifth spot. Thus, there are 2 ways of achieving this pattern.
Let’s try something slightly harder. How many ways can we get the pattern ed_? Well, the third spot has the three options {a,b,c}. Let’s say we choose c. Then there are 2 ways of getting edc from what we said earlier. From the same idea, there are 2 ways of getting eda and edb respectively. Therefore, there are 3*2 = 6 ways of getting the pattern ed_.
How about the pattern e? From the same argument as above, we get 4*3*2 = 24 ways.
Finally, the number of ways of rearranging all five letters is 5*4*3*2 = 120. This is the permutation of five letters.
We can implement this in Python using the following syntax:
import math math.perm(5) # 120
We can do a little more with the math.perm() function. Instead of arranging the letters {a,b,c,d,e} in a row of five letters, how many ways are there to arrange them in a row of three letters (in other words, the pattern _)?
We can use the same argument as before.
- In the first spot, there are five options
{a,b,c,d,e}. Let’s say we choosee. - In the second spot, we are left with four options
{a,b,c,d}. Let’s say we choosec. - The last spot has three options
{a,b,d}.
Therefore, there are 5*4*3 = 60 options in all.
In Python, we can implement this as:
math.perm(5,3) # 60
To elaborate, the integer parameter n is the number of letters to arrange, and the integer k is the number of spots on the row. The default value of k is None, meaning that the number of spots on the row is set to n by default.
See also the discussion on permutations in this blog post.
The Factorial Function math.factorial()
math.factorial(int x)
The function math.factorial takes in an integer argument x, and returns its factorial x! in the mathematical sense. In other words, if x is positive, then math.factorial(x) outputs the product
x! = 1 * 2 * 3* ... * (x-1) * x*For instance, 3! = 1 * 2 * 3 = 6. If x=0, then 0!=1*.
As of version 3.9, math.factorial does not accept negative or non-integer inputs.
The syntax for math.factorial is as follows:
import math math.factorial(3) # 6 math.factorial(0) # 1
For more details on the factorial function, see this blog post.
Number Theoretical Functions
The math.gcd() Function
math.gcd(*integers)
The greatest common divisor (gcd) of a collection of integers n1,…nk is the greatest integer d dividing each of n1,…nk.
- For instance, the gcd of 12 and 18 is 6 because their common divisors are 1,2,3, and 6, of which 6 is the largest.
- Similarly, the gcd of 49, 84, and 168 is 7 because 1 and 7 are the only common divisors, of which 7 is the largest.
In general, when manually finding the gcd as above, it is a good idea to first look for the number with the fewest number of divisors. For instance, in the second example, the divisors of 49 are 1,7, and 49, whereas 84 has sixteen divisors. Since the gcd must be a divisor of 49, it is much easier to find it from the list of divisors of 49 than from the divisors of 84.
The syntax for the math.gcd() function is as follows:
import math math.gcd(12,18) # 6 math.gcd(49,84,168) # 7
The math.gcd() function accepts as many integer arguments as desired. (The is what is meant by “*integers” in the documentation.)
When a collection of integers n1,…nk have gcd equal to 1, they are called relatively prime or coprime. (The most important case is when there are only two integers.) Relatively prime integers are generally easier to work with than numbers with common divisors. See the Wikipedia page for more discussion.
Exercise. What do you expect the outputs are for the following pieces of code?
- a.)
math.gcd(15,20), - b.)
math.gcd(2,3,5), - c.)
math.gcd(14,21,70), - d.)
math.gcd(40,62,84)
To achieve a deeper understanding of elementary number theory, we will briefly mention the Euclidean algorithm, an important algorithm for computing gcd’s for a pair of numbers. (For an extensive discussion, read up on “divisibility” in any good elementary number theory or discrete mathematics textbooks. There is also an encyclopedic overview on the Wikipedia page.)
To avoid using too much mathematical notation (see the Wikipedia page or a textbook, if you are mathematically inclined), we will illustrate the algorithm using an example. Let’s take n1 = 6342 and n2 = 3816. The algorithm is a series of divisions where we only care about the remainder (and not the quotient):
First, we divide n1 by n2:
6342 = 1*3816 + 2526Next, divide 3816 by 2526:
3816 = 1* 2526 + 1290Next, divide 2526 by 1290:
2526 = 1*1290 + 1236Next, divide 1290 by 1236:
1290 = 1* 1236 + 54Next, divide 1236 by 54:
1236 = 22* 54 + 48Next, divide 54 by 48:
54 = 1* 48 + 6Finally, divide 48 by 6:
48 = 8* 6 + 0The algorithm terminates because we have remainder zero. Since 6 is the last nonzero remainder, it is the gcd. (To understand why this works, please see the resources listed above.)
1236 % 54 # 48
Here is one way to implement the algorithm in Python:
def eucl_gcd(n1,n2):
# ensure n1 >= n2
if n1 < n2:
n1,n2 = n2,n1
# initialize
a,b = n1,n2
r = a%b
s=b
# algorithm
while r > 0:
s = r
a,b = b,r
r = a%b
# return remainder
return s
print(eucl_gcd(12,18))
# 6We can extend the Euclidean algorithm to calculate the gcd for three or more integers using the following useful fact:
gcd(n1,n2,n3) = gcd(n1,gcd(n2,n3))In other words, to calculate the gcd of three numbers, we can first calculate the gcd of two of the numbers (call it d), and then calculate the gcd of d and the third number.
We can demonstrate this with some Python code:
math.gcd(14,21,70) == eucl_gcd(14,eucl_gcd(21,70)) # True math.gcd(49,84,168) == eucl_gcd(49,eucl_gcd(84,168)) # True
The math.lcm() Function
math.lcm(*integers)
The least common multiple (lcm) of a collection of integers n1,n2,…,nk is the smallest integer divisible by each number.
- For instance, the
lcmof 12 and 18 is 36, because the first few multiples of 12 are 12, 24, 36, and 48, whereas for 18, it is 18, 36, and 54. - Similarly, the
lcmfor 4, 6, and 15 is 60 because the first few multiples of 15 are 15, 30, 45, and 60, of which the first number divisible by both 4 and 6 is 60.
In general, when manually calculating lcm by looking at the multiples of each number as we did above, it is a good idea to look at the multiples of the largest number since there will be fewer numbers to check.
The lcm of two numbers n1 and n2 is closely related to their gcd:
gcd(n1,n2)\ lcm(n1,n2) = n1*n2*We can calculate lcm(n1,n2) using the above formula by using the Euclidean algorithm to calculate gcd(n1,n2).
The syntax for math.lcm() is as follows:
import math math.lcm(12,18) # 36 math.lcm(14,70,84) # 420