オイラーのφ関数 - inamori’s diary

Project Eulerでは、"Euler's totient function"と呼ばれています。
φ(n)は、n以下のnと互いに素な自然数の個数を表します。
例えばφ(6)は、1と5が互いに素なので、2となります。
もうちょっと系統立てて考えてみましょう。6と互いに素であるというのは、2の倍数でなくかつ3の倍数でないと同じことです。6までで2の倍数でない割合は1/2です。3の倍数でない割合は2/3です。よって、

φ(6) = 6 * 1/2 * 2/3 = 2

となります。
一般に、

$n = p_1^{e_1} \cdots p_m^{e_m}$
$\varphi(n) = n(1-\frac{1}{p_1})\cdots(1-\frac{1}{p_m})$

となります。
特に、nが素数なら、

φ(n) = n - 1

となります。



from itertools import takewhile
def gen_prime_candidates():

    yield 2

    yield 3

    n = 0

    while True:

        yield n + 5

        yield n + 7

        n += 6
def calc_exp(n, p):

    e = 0

    while n % p == 0:

        e += 1

        n /= p

    return e, n
# 60 = 2^2*3*5 -> (2, 3, 5)

def factorize(n):

    f = ()

    for p in takewhile(lambda p: p * p <= n, gen_prime_candidates()):

        e, n = calc_exp(n, p)

        if e:

            f = f + (p, )

    if n > 1:

        f = f + (n, )

    return f
def phi(n):

    return reduce(lambda x, p: x * (p - 1) / p, factorize(n), n)