# Project Euler #92: Square digit chains

# Project Euler #92: Square digit chains

FranckV + 1 comment Not that easy.

I have one idea in mind that would lower the complexity, but I don't think it'll lower it enough.

I am thinking to reformulate numbers under the following forms:

(number) = a*1 + b*2 + ... i*9

In other words, what really matters is the number of times each digit is repeated. So every number between 1 - 10^K can be reformulated as such. Many numbers in there will in fact be just reformulation of the same pattern (e.g. 227788, 728827, etc are identical "paths" to 89 or to 1).

So the problems then becomes about elaborating each combinaisons (keeping in mind we have at most: a + b + ... i <= 200), figuring out if it leads to 89 or 1. This is still a lot (around 22^9, or 1.2 trillions) though...

There has to be a mathematical pattern, but can't find it yet....

Deciph3r + 0 comments see i get one interesting thing, that if we generate all numbers which is <16400 or 1e6 into a set S than for higher numbers say 1e50 we have to just check sum of sq. of digits using your method, if its falling into the set or not;

but i think thats too a time consuming job or not? :(

droidian + 3 comments I am getting time out after three test cases? any help.Is there any specific pattern in happy numbers and unhappy numbers(two types of numbers mentioned in the problem)

advancedxy + 0 comments You shouldn't check every number under 10^k, when k >= 8, It's almost certain you program will time out. Think about another way to solve this problem, something dp....

popo + 0 comments same here!!

welcometors + 0 comments Try a different approach. You can compute for K=1000 in a blink of an eye with correct approach.

vb6101993 + 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

kitchent + 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 .

padeff + 0 comments Would it not be better to explain that : f(n)= sum(sqirt(i) for i in string(n)) is an injection from 10**x space to x*81 space. so for K=200 it means 16281 in term of space. going from 10*

*x to 10**(x+1) is adding a square (1,4,9,16..81) to {f(10**x)}, so for every cycle it costs at mosts 162810 additions. you get 5*10**7 ops, instead of 10**200; Well good luck to anyone

SunilkumarDSK + 1 comment Please explain me the example test case. The Test Case 0. How input=1 and output=7?

Ufush + 0 comments Input indicates number K. When input is 1, you need to check all numbers under 10^1. So there are 7 numbers match the defined criteria among [1, 2, ... 10]

FranckV + 1 comment Is it possible to access the test cases? For other exercises we could, is it possible here? My program gets runtime error only for the last 3 or 4 cases, the others are passing... Difficult to debug without knowing more.

amazinghacker + 0 comments The contest is infinitely long. So, you can never access the solutions or even test cases.

MrAsimov + 2 comments very large numbers are involved. can this be done in C language

NiakTheWizard + 0 comments A proper algo for this problem doesn't require handling big integers (32-bit int are sufficient). This can be done in any language.

ASHWIN_18 + 0 comments TBH anything and everything can be done in C. period

mj123 + 1 comment can someone please explain me the question ??.....what does it meant by print modulo(10^9 +7).....also please explain the first test case!!!!

sudheesh001Asked to answer + 0 comments Hi mj123, Lets take the following example 85â†’89â†’145â†’42â†’20â†’4â†’16â†’37â†’58â†’89

The number 85 has 8

^{2}+5^{2}= 64+25 = 89

Similarly 89 has 8^{2}+9^{2}=64+81=145

In the same way 145 gives 1^{2}+4^{2}+5^{2}= 42

Then 4^{2}+2^{2}=20

Using 20, 2^{2}+0^{2}=4

4^{2}= 16

and so on.I hope you can solve it now. printing the modulo means, if the answer you get is N print the value of N%1000000007

eg. 20%1000000007 = 20

1000000047%1000000007=40

Sort 12 Discussions, By:

Please Login in order to post a comment