Project Euler p92

Problem description:
-------------------------------------------------------------------
A number chain is created by continuously adding the square of the digits in a number to form a new number until it has been seen before.

For example,

44 -> 32 -> 13 -> 10 -> 1 -> 1
85 -> 89 -> 145 -> 42 -> 20 -> 4 -> 16 -> 37 -> 58 -> 89

Therefore any chain that arrives at 1 or 89 will become stuck in an endless loop. What is most amazing is that EVERY starting number will eventually arrive at 1 or 89.

How many starting numbers below ten million will arrive at 89?
-------------------------------------------------------------------
Semi-bruteforce algorithm based on idea that we don`t need to construct full number chains from starting number until 1 or 89. Instead we will save in memory each starting number final result (1 or 89). And at the next starting number we will construct number chain only until previous calculated number.
Well solution is slow, but fits in "one minute rule" :-). Here it is-

---

import time as t

def nextnum(number):
 n = number
 s = 0
 while n!=0:
  m = n%10
  n = n/10
  s += m*m
 return s

def untilknown(number):
    start = number
    res = []
    while start >= number and start not in (1,89):
        start = nextnum(start)
        res += [start]
    return res

def endswith89(limit):
    seq = {1:1,89:89}
    ret = 0
    for x in range(1,limit):
        if not seq.has_key(x):
            k = untilknown(x)
            if k:
                kk = k[-1]
            else:
                kk = x
            seq[x] = seq[kk]
            if len(k) > 1:
                for i in range(len(k)-1):
                    seq[k[i]] = seq[kk]
        if seq[x] == 89:
            ret += 1
    return ret

t1 = t.time()
ans = endswith89(10000000)
t2 = t.time()

print ans, int(t2-t1),'s'

---

Have fun !!