技術メモ

役に立てる技術的な何か、時々自分用の覚書。幅広く興味があります。

sympyで素因数分解ができるからオイラー関数と約数関数を書いてみた

pythonのライブラリの一つsympyを使えば、簡単に素因数分解ができるということを知った。

import sympy
sympy.factorint(1000)
#{2: 3, 5: 3}

ちなみに、因数分解も簡単にできる(◎.◎)!!
凄い。

import sympy
x = sympy.Symbol('x')

eqn = x**2 - 3*x + 2
print(sympy.factor(eqn))
# (x - 2)*(x - 1)

これを使って、オイラー関数と約数関数を書いてみた。

オイラー関数

自然数nに対して、n未満でnと互いに素な自然数の個数を\varphi(n)で表し、オイラー関数と呼ぶ。
例えば、12未満で12と互いに素な自然数\{1, 5, 7, 11\}なので\varphi(12) = 4

def euler(n):
    factors = sympy.factorint(n)
    rst = 1
    for i,j in factors.iteritems():
        rst *= (pow(i,j) - pow(i,j-1))
    return rst

約数関数

自然数nの約数の和を\sigma(n)と表し、約数関数と呼ぶ。
例えば、12の約数は\{1,2,3,4,6,12\}なので\sigma(12)=28

def divisor(n):
    factors = sympy.factorint(n)
    rst = 1
    for i,j in factors.iteritems():
        rst *= (pow(i,j+1) - 1)/(i-1)
    return rst

コードの説明

コードだけ見てもちんぷんかんぷんだろうけれど、それぞれ関数のこれらの性質を利用している。

n素因数分解が次のように与えられているとき
 \displaystyle n = \prod_{k=1}^d p_k^{e_k}
オイラー関数、約数関数はそれぞれ次のように求まる
 \displaystyle \phi(n) = \prod_{k=1}^d (p_k^{e_k} - p_k^{e_k-1})
 \displaystyle \sigma(n) = \prod_{k=1}^d \frac{p_k^{e_k+1}-1}{p-1}

数え上げ

n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
\phi (n) 1 1 2 2 4 2 6 4 6 4 10 4 12 6 8 8 16 6 18
\sigma (n) 1 3 4 7 6 12 8 15 13 18 12 28 14 24 24 31 18 39 20


参考:
wikipedia:オイラー関数
wikipedia:約数関数
オイラー関数に関して:
RSA暗号を実装してみる(理論編) - 技術メモ

関連記事: