最小公倍数 (least common multiple)
2 数 a, b について、それぞれの倍数からなる無限集合
A = {a, 2a, 3a, …}
B = {b, 2b, 3b, …}
をつくったとき、A と B に共通する元 (要素) を公倍数とよび、その中の最小数を最小公倍数といいます。たとえば 4 と 6 について、それぞれの倍数からなる集合
A = {4, 8, 12, 16, 20, 24, 28, 32, 36, …}
B = {6, 12, 18, 24, 30, 36, 42, 48, 54, …}
をつくったとき、12, 36, … は A, B に共通する元なので公倍数であり、その中の最小数 12 は最小公倍数です。
Pythonで最小公倍数関数を実装する
2 数 a, b の最小公倍数 L と最大公約数 G の積 LG は、a と b の積 ab に等しいことが知られています（LG = ab）。
最大公約数 G は math.gcd()関数を使って計算できるので、最小公倍数 を求める関数 lcm() を以下のように定義できます（lcm は least common multiple の略）。
# PYTHON_MATH_LCM
# In[1]
import math
# 2数を受け取って最小公倍数を返す関数
def lcm(a, b):
y = a*b / math.gcd(a, b)
return int(y)
lcm()を使って 8 と 12 の最小公倍数を求めてみます。
# In[2] # 8と12の最小公倍数 x = lcm(8, 12) print(x) # 24
3 数 a, b, c の最小公倍数は、lcm(a, b) と c の最小公倍数です。
4 数 a, b, c, d の最小公倍数は、lcm(a, b, c) と d の最小公倍数です。
同様にして任意の個数の数の最小公倍数は再帰的に計算できます。
functoolsモジュールの reduce()関数 に二項演算関数とイテラブルオブジェクトを渡すと、このような再帰計算 (集約) を実行してくれます。可変引数を受け取って最小公倍数を返す関数 lcm_2() は次のように定義できます。
# In[3]
import functools
# 可変引数を受け取って最小公倍数を返す関数
def lcm_2(*vals):
return functools.reduce(lcm, vals)
lcm_2() を使って 10, 12, 15, 30 の最小公倍数を求めてみます。
# In[4] # (10,12,15,30)の最小公倍数 x = lcm_2(10, 12, 15, 30) print(x) # 60
numpy.lcm()
numpy.lcm(x1, x2) は x1 と x2 の最小公倍数を返します。
# NUMPY_LCM # In[1] import numpy as np # 16と20の最小公倍数 lcm = np.lcm(16, 20) print(lcm) # 80
x1, x2 には配列を渡すこともできます。x1 と x2 のサイズが同じであれば、同じインデックスの要素同士で最小公倍数を計算します。
# In[2] x1 = [3, 8, 10] x2 = [5, 12, 24] # 3と5,8と12,10と24の最小公倍数 lcm = np.lcm(x1, x2) print(lcm) # [10 12 24]
x1 と x2 のサイズが異なる場合はブロードキャストして最小公倍数を計算します。
# In[3] x2 = [8, 15, 26] # 4と8,4と15,4と26の最小公倍数 lcm = np.lcm(4, x2) print(lcm) # [8 60 52]
3 数以上の最小公倍数を求めるときには、reduce() メソッドで集約演算を実行します。
# In[4] x = np.array([2, 5, 8, 10, 19]) # [2,5,8,10,19]の最小公倍数 lcm = np.lcm.reduce(x) print(lcm) # 760
sympy.lcm()
SymPy には 2 数 a, b を受け取って a と b の 最小公倍数 を返す sympy.lcm() が用意されています。
# SYMPY_LCM # In[1] import sympy # 12と20の最小公倍数 lcm = sympy.lcm(12, 20) print(lcm) # 60
引数 a, b には数式を渡すこともできます。
# In[2]
# 記号xを定義
sympy.var('x')
# 数式f,gを定義
f = x**3 + 3*x**2 -x -3
g = 2*x**3 + x**2 - 2*x - 1
# fとgの最小公倍数
lcm = sympy.lcm(f, g)
print(lcm)
# 2*x**4 + 7*x**3 + x**2 - 7*x - 3
sympy.lcm() には引数を 3 つ以上渡せないので、3 つの数 a, b, c の最小公倍数を求めたい場合は、lcm(a, b) と c の最小公倍数を計算させます。
# In[3]
# 3数の最小公倍数を求める関数
def triple_lcm(a, b, c):
from sympy import lcm
return lcm(lcm(a,b), c)
# 15,,20,40の最小公倍数
x = triple_lcm(15, 20, 40)
print(x)
# 120
コメント