Project Euler 14

problem

Define a sequence of numbers that is repeatedly generated by the following formula for positive integers.

n → n / 2 (n is an even number)

n → 3n + 1 (n is odd)

Starting from 13, this sequence looks like this:

13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1 There are 10 terms from 13 to 1. This sequence is thought to end up at 1 no matter what number you start with, but that has not yet been proven (Collatz problem).

Now, which of the numbers less than 1 million should be started to generate the longest sequence?

Note: May be over 1 million in the middle of the sequence http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2014

Answer policy

13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

In terms of the sequence of, the length of the sequence generated by 13 is the length of the sequence generated by 40 plus one. In other words, the length of the sequence generated in 13 is recursively calculated. In addition, the amount of calculation can be reduced by storing the result in the middle.

code

def next(n):
  if n % 2:
    return n*3 + 1
  else:
    return n / 2

def add(dict,n1):
  n2 = next(n1)
  if not n2 in dict:
    dict = add(dict,n2)
  dict[n1] = dict[n2]+1
  return dict

def main():
  dict = {1:1}
  (max_i,max) = (1,1)
  for i in range(2,10**6):
    if not i in dict:
      dict = add(dict,i)
    if dict[i] > max:
      (max_i,max) = (i,dict[i])
  print  (max_i,max)

result

The result was 2.87sec, which was as slow as a demon. When I searched the net, I found a code that improved the speed by not remembering numbers larger than a certain number (1 million).