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
Content is available under GNU Free Documentation License 1.2.