最小公倍数（LCM）

最小公倍数 (least common multiple)

　2 数 a, b について、それぞれの倍数からなる無限集合
　
　　A = {a, 2a, 3a, ...}
　　B = {b, 2b, 3b, ...}
　
をつくったとき、A と B に共通する元 (要素) を 公倍数 とよび、その中の最小数を 最小公倍数 (least common multiple) といいます。たとえば 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() を以下のように定義できます。

# 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