Brute-forcing Eurler #70

Euler's Totient function, φ(n) [sometimes called the phi function], is used to determine the number of positive numbers less than or equal to n which are relatively prime to n. For example, as 1, 2, 4, 5, 7, and 8, are all less than nine and relatively prime to nine, φ(9)=6....

First I was trying to  brute-force the solution using FT of Euler totient function (http://en.wikipedia.org/wiki/Euler%27s_totient_function#Fourier_transform), than through the definition but all these solutions was too long to wait. In the end finished with product formula.

In the process of solution found quite faster recipe from ActiveState on generating prime numbers (http://code.activestate.com/recipes/366178-a-fast-prime-number-list-generator/).

Also used multiprocessing module to speed up solution.

	#!/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]

view raw 70.py hosted with ❤ by GitHub

And after...

$ time ./70.py 
(8319823, 8313928, 1.0007090511248113)

real    235m23.873s
user    1644m0.217s
sys     0m36.206s