Python 3.3 vs. MSDOS Basic

[Serhiy Storchaka]

On 19.02.13 20:31, Ian Kelly wrote:
> On Tue, Feb 19, 2013 at 7:46 AM, Tim Daneliuk <tundra at 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))