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
        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)):

count = 0   

for i in nums:
    if 89 in chain(i,[])[1]: 
        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.


source to share

1 answer

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.

General notes about your code:

  • 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.


All Articles