Project Euler #70

70.py

#!/usr/bin/python

from operator import mul
from multiprocessing import Pool, Manager


manager = Manager()
primes_cache = manager.list()


def primes(n):
    if n == 2:
        return [2]
    elif n < 2:
        return []
    s = range(3, n + 1, 2)
    mroot = n ** 0.5
    half = (n + 1) / 2 - 1
    i = 0
    m = 3
    while m <= mroot:
        if s[i]:
            j = (m * m - 3) / 2
            s[j] = 0
            while j < half:
                s[j] = 0
                j += m
        i = i + 1
        m = 2 * i + 3
    return [2] + [x for x in s if x]

primes_cache = primes(10000000)


def factorize(n):
    for prime in primes_cache:
        if prime > n:
            return
        exponent = 0
        while n % prime == 0:
            exponent, n = exponent + 1, n / prime
        if exponent != 0:
            yield prime, exponent


def totient(n):
    return reduce(
        mul,
        ((p - 1) * p ** (exp - 1)
         for p, exp in factorize(n)),
        1)


def euler70(n):
    t = totient(n)
    if sorted(str(n)) == sorted(str(t)):
        return (n, t, float(n) / t)
    else:
        return (n, t, 1e7)


if __name__ == '__main__':
    pool = Pool(processes=8)
    print sorted(
        pool.map(
            euler70,
            xrange(2, 10000000)),
        key=lambda n: n[2])[0]