最小公倍数

最小公倍数

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

最小公倍数関数の実装

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

LG = ab

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

# PYTHON_MATH_LCM-1

import math

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

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

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

# PYTHON_MATH_LCM-3

import functools

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

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

# PYTHON_MATH_LCM-4

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

print(x)
60

 

リーダブルコード ―より良いコードを書くためのシンプルで実践的なテクニック (Theory in practice)

新品価格
¥2,592から
(2019/8/6 17:55時点)

numpy.lcm()

 numpy.lcm(x1, x2) は x1 と x2 の最小公倍数を返します。

# PYTHON_NUMPY_LCM-1

import numpy as np

# 16と20の最小公倍数
lcm = np.lcm(16, 20)

print(lcm)
80

 x1, x2 には配列を渡すこともできます。x1 と x2 のサイズが同じであれば、同じインデックスの要素同士で最小公倍数を計算します。

# PYTHON_NUMPY_LCM-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 のサイズが異なる場合はブロードキャストして最小公倍数を計算します。

# PYTHON_NUMPY_LCM-3

x2 = [8, 15, 26]

# 4と8,4と15,4と26の最小公倍数
lcm = np.lcm(4, x2)

print(lcm)
[8 60 52]

 3 数以上の最小公倍数を求めるときには、reduce() メソッドで集約演算を実行します。

# PYTHON_NUMPY_LCM-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() が用意されています。

# PYTHON_SYMPY_LCM-1

import sympy

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

print(lcm)
60

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

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

# PYTHON_SYMPY_LCM_03

# 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