## Tuesday, November 11, 2008

### 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 tdef nextnum(number): n = number s = 0 while n!=0:  m = n%10  n = n/10  s += m*m return sdef untilknown(number):    start = number    res = []    while start >= number and start not in (1,89):        start = nextnum(start)        res += [start]    return resdef 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 rett1 = t.time()ans = endswith89(10000000)t2 = t.time()print ans, int(t2-t1),'s'`

Have fun !!