Problem 92
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?
C++(Faster):
#include#include #include using namespace std;const int MAXN = 10000000;int arrive[MAXN], chainno[MAXN];int no;int nextval(int n){ int sum, v; sum = 0; while(n) { v = n % 10; sum += v * v; n /= 10; } return sum;}void makechain(int n){ no++; while(n != 1 && n != 89) { if(chainno[n] > 0) { n = arrive[chainno[n]]; break; } chainno[n] = no; n = nextval(n); } arrive[no] = n;}int main(){ int n; while(cin >> n && n <= MAXN) { memset(arrive, 0, sizeof(arrive)); memset(chainno, 0, sizeof(chainno)); chainno[1] = 1; arrive[1] = 1; chainno[89] = 2; arrive[2] = 89; no = 2; for(int i=1; i
C++:
#include#include #include using namespace std;const int MAXN = 10000000;int arrive[MAXN];int nextval(int n){ int sum, v; sum = 0; while(n) { v = n % 10; sum += v * v; n /= 10; } return sum;}void makechain(int n){ stack s; while(n != 1 && n != 89) { if(arrive[n] > 0) { n = arrive[n]; break; } s.push(n); n = nextval(n); } while(!s.empty()) { int val = s.top(); s.pop(); arrive[val] = n; }}int main(){ int n; while(cin >> n && n <= MAXN) { memset(arrive, 0, sizeof(arrive)); arrive[1] = 1; arrive[89] = 89; for(int i=1; i