Euler #64

All square roots are periodic when written as continued fractions and can be written in the form...

Method for calculation of square root continued fraction is taken from  http://web.math.princeton.edu/mathlab/jr02fall/Periodicity/mariusjp.pdf

	#!/usr/bin/env python
	def period(n):
	a_0 = int(n ** 0.5)
	if a_0 * a_0 == n:
	return 0
	b, b_0 = a_0, a_0
	c, c_0 = n - a_0*a_0, n - a_0*a_0
	res = 0
	while True:
	a = (a_0 + b) / c
	b = a * c - b
	c = (n - b * b) / c
	res += 1
	if b == b_0 and c == c_0:
	break
	return res
	if __name__ == '__main__':
	print sum(
	map(lambda n: period(n) % 2,
	xrange(2, 10001)))

view raw 64.py hosted with ❤ by GitHub

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