On 19.02.13 20:31, Ian Kelly wrote:
On Tue, Feb 19, 2013 at 7:46 AM, Tim Daneliuk <tun...@tundraware.com> wrote:
Are you sure you wouldn't like to share with the class? I'd be interested
in seeing your approach...
Very well:
def collatz(n, memo):
if n not in memo:
if n % 2 == 0:
next_n = n // 2
else:
next_n = 3 * n + 1
memo[n] = collatz(next_n, memo) + 1
return memo[n]
def run_collatz(upper):
table = {1: 0}
max_n = max(range(1, upper), key=lambda n: collatz(n, table))
return max_n, table[max_n]
run_collatz(1000000)
(837799, 524)
It could certainly be optimized further, but at about 4 seconds it's
already fast enough for most purposes.
10-15% faster:
def f(M):
def g(n, cache = {1: 0}):
if n in cache:
return cache[n]
if n % 2:
m = 3 * n + 1
else:
m = n // 2
cache[n] = count = g(m) + 1
return count
num = max(range(2, M + 1), key=g)
return num, g(num)
print(*f(1000000))
--
http://mail.python.org/mailman/listinfo/python-list
