最小公倍数

最小公倍数

最小公倍数 (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 は最小公倍数です。

最小公倍数関数 lcm()

 2数 a, b の最小公倍数 L と最大公約数 G の積 LG は、a と b の積 ab に等しいことが知られています:

LG = ab

 最大公約数 G は math.gcd()関数を使って計算できるので、最小公倍数 を求める関数 lcm() を以下のように定義することができます。

# リストLC01-1

import math

# 2数を受け取って最小公倍数を返す関数
def lcm(a, b):
    y = a*b / math.gcd(a, b)
    return int(y)

 lcm()を使って 8 と 12 の最小公倍数を求めてみます。

# リストLC01-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() は次のように定義できます。

# リストLC01-3

import functools

# 可変引数を受け取って最小公倍数を返す関数
def lcm_2(*vals):
    return functools.reduce(lcm, vals)

 lcm_2() を使って 10, 12, 15, 30 の最小公倍数を求めてみます。

# リストLC01-4

# (10,12,15,30)の最小公倍数
x = lcm_2(10, 12, 15, 30)

print(x)
60

 

SymPyによる最小公倍数の計算

 SymPy には 2 数 a, b を受け取って a と b の 最小公倍数 を返す sympy.lcm() が用意されています。

# リストLC02-1

import sympy

# 12と20の最小公倍数
lcm = sympy.lcm(12, 20)

print(lcm)
60

 引数 a, b には数式を渡すこともできます。

# リストLC02-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 の最小公倍数を計算させます。

# リストLC03

# 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