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<iostream>
#include<vector>
#include<unordered_map>
#include<algorithm>

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<int> permutations(int n) 
 auto digits = std::to_string(n);
 std::vector<int> 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<int,bool>();

 int m = n;
 while (m != 1) 
 if(cache.find(m) != cache.end()) 
 return cache.find(m)->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< 10000000; i++) 
 if (arrivesAt89(i)) numberOf89s++;
 

 std::cout << numberOf89s << 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 <string> 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.

Obviously, the algorithm provided will set up a number of equivalence classes of numbers containing the same ciphers. E. g. 1012, 1210, and all other permutations of are equivalent.

So you might want to sort the numbers by their digits (skipping all zeros), so you'd only have to store 112 for above numbers, or the other way round, only generate the sorted numbers by some appropriate algorithm.

Finally, you can easily generate the number of permutations from these numbers. Example above:

00 000 112

There are 8! but we need to divide by the number of equivalent permutations (due to the five zeros and the two ones), so we get:

8! / 5! / 2!

A mentioned number generator might look like this one:

std::vector<unsigned int> current(1, 2, 3, 4, 5, 6, 7, 8, 9 );
std::vector<unsigned int> previous;

for(unsigned int i = 0; i < 7; ++i)

 using std::swap;
 for(auto n : current)
 std::cout << n << ' ';
 std::cout << std::endl;
 swap(current, previous);
 current.clear();
 for(auto n : previous)
 
 for(unsigned int m = 1; m <= n % 10; ++m)
 
 current.push_back(n * 10 + m);
 
 

producing all sorted numbers up to 7 digits (OK, within numbers, sorting order is invers, but that's not of relevance...).

Plenty of good answers have been given I'll just point out that 10 million is actually not a lot.

The square sum of digits of 9999999 is 7*81=567 and this is the largest sum you can get. So to determine if any up to 7 digit number ends up as 1 or 89 cannot require more than 567 iterations of computing the sum of squared digits.

Meaning that brute force 567*10M=5.67 G iterations of computing sum of digits squared will solve it. Sum of digits squared using the trivial integer division approach is 7 divisions with remainder, 6 additions and 7 multiples, plus loop overhead call it 30 instructions, so in total you'd need 5.67*30~=16G instructions.

For a typical desktop computer with 4 GHz one core turbo and IPC of 2 (which is pessimistic for modern x86 CPUs) that amounts to 8 G instructions per second, which means brute force should take around two seconds if my math isn't completely of the charts wrong.

So you can do a bunch of clever stuff but it won't save you more than two seconds of CPU time over just brute forcing it. And you can do much worse than brute force as OPs solution doesn't complete after a whole minute by computing ineffective sums, allocating a bunch of memory left right and center, generating permutations and what not.

Edit: To prove my point:

I implemented the brute force soloution:

pe.cpp

#include <iostream>

int ssd(int n)
 int ans = 0;
 while(n)
 int d = n%10;
 n = n/10;
 ans += d*d;
 
 return ans;


int main(int, char**)
 int n89 = 0;
 for(int n = 2; n < 10000000; n++)
 int s = ssd(n);
 while(s != 1 && s != 89)
 s = ssd(s);
 
 if(s==89)
 n89++;
 
 
 std::cout<<n89<<std::endl;

And ran it, producing the correct solution in under half a second:

$ g++ -O3 pe.cpp -o pe && time ./pe
8581146

real 0m0.423s
user 0m0.423s
sys 0m0.000s

On my machine:

$ cat /proc/cpuinfo | grep "model name" | tail -n 1
model name : Intel(R) Core(TM) i7-8700K CPU @ 3.70GHz

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

 for (auto c : digits) 
 sum += (c - '0') * (c - '0'); // I corrected the = into +=
 

 return sum;

Conversions come with a performance hit, especially when the conversion implies memory allocation and copy, as here with std::to_string. It would make perfect sense if you had some use for the string, but you don't, since you return another int. And the math behind it is really basic:

constexpr int sum_of_squared_digits(int n) 
 int res = 0;
 while (n) 
 const int digit = n % 10;
 res += digit * digit;
 n /= 10;
 
 return res;

I've marked it constexpr, only to hint that the whole algorithm could be performed at compile-time, but it wouldn't really be fair, so it won't.

bool arrivesAt89(int n) 
 static auto cache = std::unordered_map<int,bool>();

unordered_map might not be necessary in this case. A simple array would suffice, with 0 meaning unexplored, 1 ending with 1 and 89 ending with 89: it's even faster and all the memory allocation is done upfront.

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

Here is I think the main weakness of your algorithm: you only cache the result for the number n and its permutations; all intermediary values are ignored, although they belong on the same path as n and would populate the map much faster.

 

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

Computing the permutations come with another heavy conversion, with memory allocation and copy (std::to_string) and a std::vector you won't use beyond feeding it to the static std::unordered_map inside your master function.

std::vector<int> permutations(int n) 
 auto digits = std::to_string(n);
 std::vector<int> res;
 res.push_back(n);

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

Besides, it won't give you every permutation: if you want to go through all permutations with std::next_permutation, you need to start with a sorted std::string.

 return res;

Anyway, I don't think that permutations are the best way of testing the numbers equivalence: you don't need it if you keep track of intermediary values, because permutations will result in the same squared digits' sum.

Here what I'd find correctly optimized:

auto precompute_results(int n) 
 std::vector<int> results(n, 0); 
 // a vector instead of a map, 
 // elements can be:
 // 0 = unexplored, 1 = ending in 1, 89 = ending in 89
 // n = on the same path as n
 for (int i = 1; i < n; ++i) 
 auto cur = results[i] ? results[i] : i;
 while (true) 
 results[i] = cur;
 
 return results;