fbpx

C++: Iterated Digits Squaring

Bjarne-stroustrup
 


If you add the square of the digits of a Natural number (an integer bigger than zero), you always end with either 1 or 89:

15 -> 26 -> 40 -> 16 -> 37 -> 58 -> 89
7 -> 49 -> 97 -> 130 -> 10 -> 1

An example in Python:

>>> step = lambda x: sum(int(d) ** 2 for d in str(x))
>>> iterate = lambda x: x if x in [1, 89] else iterate(step(x))
>>> [iterate(x) for x in xrange(1, 20)]
[1, 89, 89, 89, 89, 89, 1, 89, 89, 1, 89, 89, 1, 89, 89, 89, 89, 89, 1]
Task
Count how many number chains for integers 1 <= n < 100_000_000 end with a value 89.

Or, for much less credit – (showing that your algorithm and/or language is slow):

Count how many number chains for integers 1 <= n < 1_000_000 end with a value 89.
Slow (~10 seconds on my machine) brute force C++ implementation:
#include <iostream>
 
// returns sum of squares of digits of n
unsigned int sum_square_digits(unsigned int n) {
        int i,num=n,sum=0;
        // process digits one at a time until there are none left
        while (num > 0) {
                // peal off the last digit from the number
                int digit=num % 10;
                num=(num - digit)/10;
                // add it's square to the sum
                sum+=digit*digit;
        }
        return sum;
}
int main(void) {
        unsigned int i=0,result=0, count=0;
        for (i=1; i<=100000000; i++) {
                // if not 1 or 89, start the iteration
                if ((i != 1) || (i != 89)) {
                        result = sum_square_digits(i);
                }
                // otherwise we're done already
                else {
                        result = i;
                }
                // while we haven't reached 1 or 89, keep iterating
                while ((result != 1) && (result != 89)) {
                        result = sum_square_digits(result);
                }
                if (result == 89) {
                        count++;
                }
        }
        std::cout << count << std::endl;
        return 0;
}
Output:
85744333

SOURCE

Content is available under GNU Free Documentation License 1.2.