Python 3.9の新機能：最小公倍数を計算する関数math.lcm

mathモジュールは進化を続ける

2020年10月5日にPython 3.9がリリースされた。Python 3.9の大きな変更と言えば辞書の併合や更新の演算子|や|=の追加、接頭辞や接尾辞を削除する文字列メソッド、パーサーがLL(1)からPEGパーサーに変更されたこと、と言えるだろう。3.9の変更履歴はこちらから参照できる。
本稿で着目したいのはmathモジュールに追加された最小公倍数を計算するmath.lcm関数である。

最小公倍数を計算する関数math.lcm

公倍数とは、2つの整数に共通する倍数である。例えば、2の倍数は2, 4, 6,...であり、3の倍数は3, 6, 9,...である。つまり、2と3の公倍数は6となる。公倍数は複数存在するが、その中で最小の公倍数を最小公倍数と呼ぶ。2と3の最小公倍数は6である。なお、倍数は負数や0も含めて考えるが、普通、最小公倍数は正の数の範囲で考えることが多い。
Python 3.9で最小公倍数を計算する関数math.lcmが追加された。

>>> import math
>>> math.lcm(2, 3)
6

整数a, bの積abは公倍数であるが、最小公倍数とは限らない。例えば、2, 4の積8は公倍数であるが、最小公倍数は4である。

>>> math.lcm(2, 4)
4

では、どうやって最小公倍数を計算しているのだろうか。

最小公倍数と最大公約数の関係

整数a, bの公約数とはa, bに共通する約数、割り切れる数である。最大公約数とは公約数の中で最大のものを指す。例えば、15と18の最大公約数は3である。Pythonではmath.gcd関数で最大公約数を計算できる。

>>> math.gcd(15, 18)
3

最大公約数はEuclidの互除法というアルゴリズムで計算できる。CPythonではlongobject.cでに含まれる_PyLong_GCDやmathmodule.cのlong_gcdで定義されている。
2数の最大公約数が計算できると、最小公倍数は簡単に計算することができる。 ab = gcd(a, b) * lcm(a, b)という関係が知られていて（証明は読者の...ではなくて、例えば、算術の基本定理に基づいてa, bの素因数分解とgcdとlcmの関係を比較すればよい。）、lcm = ab / gcd(a, b)とすれば求めることができる。mathmodule.cにあるlong_lcmでも同様の計算方法で計算している。
なお、3つ以上の数の最大公約数、最小公倍数にはabc = gcd(a, b, c) * lcm(a, b, c)のような都合の良い関係は存在しない（例えば、算術の基本定理に基づく証明だと2つというのが重要で3つだと証明が成立しないことが自ずとわかる）。

3つの数の最大公約数、最小公倍数

Python 3.9ではmath.gcdも改良されており、2数だけでなく3つ以上の最大公約数も計算できるようになった。従来は、functools.reduceを使うかfor文を回す、という方法があったが、そのまま引数を渡せばよい設計となった。

>>> math.gcd(2, 6, 15)
1
>>> math.lcm(2, 6, 15)
30
>>> 2 * 6 * 15
180

3つ以上の数の最大公約数、最小公倍数にはabc = gcd(a, b, c) * lcm(a, b, c)なる関係は成立しないこともわかる。

...で、何に使えるの？

日々の業務で具体的に何に使えるのかは私もわからないが、例えば教育の現場で数学の面白さに触れるきっかけになるかもしれない。