Project Euler 92: count sum-squared-digits chains that reach 89 A number chain is created by continuously adding the square of the digits in a number to form a new number until it has been seen before.
For example:
44 → 32 → 13 → 10 → 1 → 1
85 → 89 → 145 → 42 → 20 → 4 → 16 → 37 → 58 → 89
Therefore any chain that arrives at 1 or 89 will become stuck in an endless loop. What is most amazing is that EVERY starting number will eventually arrive at 1 or 89.
How many starting numbers below ten million will arrive at 89?

My solution doesn't finish in under a minute. I'm already caching the results of arrivesAt89, including all permutations. Any help is welcomed.
#include&lt;iostream&gt;
#include&lt;vector&gt;
#include&lt;unordered_map&gt;
#include&lt;algorithm&gt;

int sumOfDigitsSquared(int n) {
    auto digits = std::to_string(n);
    int sum = 0;

    for (auto c : digits) {
        sum = (c - '0') * (c - '0');
    }

    return sum;
}

std::vector&lt;int&gt; permutations(int n) {
    auto digits = std::to_string(n);
    std::vector&lt;int&gt; res;
    res.push_back(n);

    do {
        res.push_back(stoi(digits));
    } while (std::next_permutation(digits.begin(), digits.end()));

    return res;
}

bool arrivesAt89(int n) {
    static auto cache = std::unordered_map&lt;int,bool&gt;();

    int m = n;
    while (m != 1) {
        if(cache.find(m) != cache.end()) {
            return cache.find(m)-&gt;second;
        }
        if (m == 89) {
            auto perms = permutations(m);
            for (auto p : perms) {
                cache.insert({p, true});
            }
            return true;
        }
        m = sumOfDigitsSquared(m);
    }

    auto perms = permutations(n);
    for (auto p : perms) {
        cache.insert({p, false});
    }
    return false;
}

int main() {
    int numberOf89s = 0;

    for (int i = 1; i&lt; 10000000; i++) {
        if (arrivesAt89(i)) numberOf89s++;
    }

    std::cout &lt;&lt; numberOf89s &lt;&lt; std::endl;
}
I guess the idea behind using permutations is that any permutation of the same digits will result in the same squared sum. However... in that case, shouldn't we simply calculate the squared sum and cache that?
It appears that we're only caching the permutations of the digits at the end of the chain. i.e. we'll only ever end up with 1, 89 and 98 in the map! We should probably be caching all the values in the chain up to the final result.
#include &lt;string&gt; for std::to_string.
Converting to and from std::string is probably quite slow. We can use simple integer arithmetic to extract the individual digits.
The implementation of sumOfDigitsSquared is clearly incorrect with basic testing.