# Euler Project 92

My code for solving problem 92 was correct, but too slow, and so I tried to change it to consider only one number for each possible permutation of that number, effectively reducing the size of the problem to 11439 from the original 10 million. Here's my code

``````import time
from Euler import multCoeff

start = time.time()

def newNum(n):
return sum([int(dig)**2 for dig in str(n)])

def chain(n, l):
if n in l:
return n, l
else:
l.append(n)
return chain(newNum(n), l)

nums = []

for i in range(1,10000000):
if all(str(i)[j] <= str(i)[j+1] for j in range(len(str(i))-1)):
nums.append(i)

count = 0

for i in nums:
if 89 in chain(i,[]):
perms = multCoeff(i)
count += perms

end = time.time() - start

print count, end
```

```

multCoeff is a method I created that is mostly equivalent `len(set(permutations([int(j) for j in str(i)])))`

and works great. Anyway, the problem is that the result I am getting is not correct and it looks like I am ignoring some of the cases, but I cannot figure out which ones. I would be very grateful if someone could point me in the right direction. Thank.

+3

source to share

We are missing the code for `multCoeff`

, so I guess here.

You are trying to filter from 1 to 999 999 999 by excluding numbers that have no digits in ascending order, and then recalculating their permutations after.

Your problem `0`

.

According to your filter, `2, 20, 200, 2000, 20000, 200000, 2000000`

everything is represented `2`

, however you probably don't add back many permutations.

• `item in list`

has `O(n)`

time complexity ; try to avoid this for large lists.
• You are discarding the results of many calculations ; any number in the string that results in `89`

or `1`

will always have that end result.
• Each function call has a time cost; try to keep the number of functions in the loops low.
• Casting `str`

to `int`

a few expensive; try to keep the number of casts to a minimum.
+2

source

All Articles