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.

Because I got frustrated with the problem, I made a dictionary of all digits whose chain of square of digits reaches 1 which can be found in this OEIS link for numbers upto 200 and then return:

print((10**k-(d[k]%MOD))%MOD)

You can also read about happy numbers on wikipedia

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

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

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 .