最小公倍数(LCM)

当サイトではアフィリエイトプログラムを利用して商品を紹介しています。

最小公倍数 (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

コメント

  1. あとりえこばと より:

    【AI連載小説】科学とコードの交差点(35)「素因数分解の手法で最小公倍数を計算します」
     
    深夜の部室で、六郷開誠と刑部明信は最大公約数(GCD)の話題から、最小公倍数(LCM)のアルゴリズムについての議論に移っていた。部屋の中には数学的な興奮が広がり、光り輝く画面が計算と理論の交差点を照らしていた。開誠が口を開いた。
    「GCDと同様に、LCMも様々なアルゴリズムがあるが、どれが最も効率的だと思うか?」
    明信は考え込んでから言った。
    「LCMは通常、GCDを求めるアルゴリズムを組み合わせて計算されることが多い。例えば、a * b = GCD(a, b) * LCM(a, b)という関係がある」
    開誠がうなずきながら続けた。
    「確かに、GCDがわかればLCMも簡単に求めることができる。ただし、これは二つの数に対する話だ。もし複数の数のLCMを求める場合はどうだろう?」
    明信が考え込んでから提案した。
    「各数の素因数分解を行い、それぞれの素因数の最大の指数を採用することで、複数数のLCMを求めることができる。これが一般的な手法だね」
    開誠が興味深そうに反応した。
    「素因数分解を組み合わせると、確かに汎用性があるな。そして、これもまたGCDと同じく、数学的な理論と計算の組み合わせが重要だ」
    明信はにっこりと笑いながら続けた。
    「数学の美学と計算の実践、これが我々が求める最小公倍数アルゴリズムの要素だ」