Rで最小公倍数

R

2数について求める時

最小公倍数(Least Common Multiple: 以下LCMと略す)を2数から求めるには、最大公約数(Greatest Common Divisor: 以下GCD)との間に成り立つ以下の関係、

を利用して、

として求めれば良い。GCDはユークリッドの互除法により簡単に求められる。RではGCD、LCMを求める関数を持つパッケージがいくつかある(例えばgmpパッケージのgcd、lcm.bigz)ので関心のある数が2つであればこれらのパッケージを利用するのが手軽。

3つ以上の数について求めるとき

パッケージに含まれる関数は基本的に引数として2つまでしか数を受け付けない。また、上述の関係は対象とする数が3つ以上になると成立しない(cf.最小公倍数 - Wikipedia)。
3つ以上の整数についてGCD、LCMを求める場合を考えよう。
証明はしないが、GCDとLCMは結合法則を満たす。つまり、

そこで、関心のある数のリストから2つずつ選んで順番に関数を適用していけば良い。

Reduce

RにはReduceという関数がある。Lispに馴染みのある人なら分かるだろうが(私は馴染みがないので分からないが)、このような動作をする関数である。

> Reduce("+", 1:5)
[1] 15

"+"は演算子や文字列ではなく、2つの引数をとる関数として見てもらいたい(Rでは「1+2」は「"+"(1, 2)」と同じであり、要するに「演算子」というのは特殊な書き方が許された関数である。)。
Reduceは要するに、

> "+"("+"("+"("+"(1, 2), 3), 4), 5)
[1] 15

という感じで順次関数を適用していく関数である。
Reduceを使えば、複数の数についてGCDやLCMを求められる。

> Reduce(gcd, c(3, 9, 300))
[1] 3
> Reduce(lcm.bigz, c(2, 6, 15))
Big Integer ('bigz') :
[1] 30

指数の形で欲しいとき

最大公約数は対象としている数より小さい値となるのでそのまま出てきても別に大した問題は無いのだが、最小公倍数は対象としている数がそんなに大きくなくても、個数が多いとかなり大きな数になる場合がある。なので、指数表現で欲しいという場合があるだろう多分。
対象とする数各々について素因数分解したとき、それぞれの素因子の指数を比べ、大きい方を採用したのがLCM、小さいほうがGCDである。例えば、

であるが、

といった具合である。
適当に書くと、

library(gmp)
get.prime <- function(n){ ## 適当注意
  (1:n)[isprime(1:n) != 0]
}
LCMcnt <- function(N){
  prime <- get.prime(max(N))
  count <- numeric(length(prime))
  names(count) <- prime
  for(n in N){
    tmp <- table(as.numeric(factorize(n)))
    for(name in names(tmp)){
      if(count[name] < tmp[name]) count[name] <- tmp[name]
    }
  }
  count[count != 0]
}

といった感じである。

> LCMcnt(c(36, 68))
 2  3 17 
 2  2  1
> LCMcnt(1:50)
 2  3  5  7 11 13 17 19 23 29 31 37 41 43 47 
 5  3  2  2  1  1  1  1  1  1  1  1  1  1  1

ちなみに説明のために適当に書いただけで、あんまりお手軽でも安心でもないので、実用上はlcmの結果をgmpのfactorizeに突っ込んでしまうのが良いと思う。

> factorize(Reduce(lcm.bigz, 1:50))
Big Integer ('bigz') object of length 23:
 [1] 2  2  2  2  2  3  3  3  5  5  7  7  11 13 17 19 23 29 31 37 41 43 47
> table(as.numeric(factorize(Reduce(lcm.bigz, 1:50))))

 2  3  5  7 11 13 17 19 23 29 31 37 41 43 47 
 5  3  2  2  1  1  1  1  1  1  1  1  1  1  1

gmpパッケージについて

上の例で気付いたかもしれないが、bigzクラスはそのままtableに突っ込めないので、as.numericでnumericに戻してやる必要がある。
gmpパッケージのbigzやbigqなどは何も考えずに色々な計算ができて便利なのだが、集合演算など対応していない関数も多い。
tableの場合はエラーが出るのでまだいいのだが、uniqueなどではエラーもでない。いつもの調子でいつもの関数を使っていると思わぬバグが紛れ込むので、gmpパッケージを使う場合は普段以上に型に注意する必要がある。

> unique(factorize(Reduce(lcm.bigz, 1:50)))
 [1] 17 00 01 02 03 05 07 0b 0d 11 13 1d 1f 25 29 2b 2f