# Project Euler #92: Square digit chains

# Project Euler #92: Square digit chains

+ 0 comments The official Project Euler has K only going up to 7! I'm not mad but this does feel like a significant scale up from the original question. For K = 7 I didn't need dynamic programming as much as I needed to be able to generate the # to add from each permutation, but then I'm generating every combination of digits. With 200 digits...???

Even if all digits werre 9, I know the intermediate steps max out at k* 9^2, but I guess I got to think about how to keep track of intermediate steps and combos.

+ 0 comments can anyone explain me the question what it wants.i didn't understand it

+ 0 comments We should try to think the reverse solution. For eg. we have to get 89 using squares of numbers (1-9). Obtain 89 using 1, 4, 9, 16, 25, 36, 49, 64, 81 once or more than once. eg. 4+4+81=89 (the numbers are permutations of 2,9,2,0,0,0,0,0,0,0) use recursion and count

+ 0 comments It's funny how Pypy can pass in 0.88s while Python 2 could exceed 10s. By the way, very hardcore dynamic programming practice. Recursive DP is not something I've been used to.

**EDIT**: An iterative DP approach considering the number of occurrences of square digit sum within k digits, is in my opinion, much easier to comprehend, without heavy usage of global variables and fear of recursion limit.It can also pass all test cases in Python 2. The last line of this implementation is:

`print sum([a * b for (a, b) in zip(sum_count, unhappy)]) % (int(1e9) + 7)`

. You may want to generate the list of unhappy numbers (those within the loop) from to .

Sort 15 Discussions, By:

Please Login in order to post a comment