Project Euler #92: Square digit chains

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