Square Digit Chains
The problem
Repeatedly replace a number with the sum of the squares of its digits. Every chain ends up at either 1 or 89. Count the starting numbers below ten million that reach 89.
My solution
Brute force. For each start from 1 to 9,999,999, I follow the chain while recording every value in a fresh TreeSet. The loop stops when add returns false, meaning a value repeated. If 89 showed up along the way, the start is counted:
while(chain.add(num)) {
if(num == 89)
count++;
sum = 0;
while(num != 0) {
sum += (num % 10)*(num % 10);
num /= 10;
}
num = sum;
}
Since 89 can only be added to the set once, each start is counted at most once. Chains reaching 1 stop when 1 repeats, and chains reaching 89 go around the 89 → 145 → … → 89 cycle once and stop. That’s ten million chains of up to about 20 values each.
Notes
The numbers collapse fast: after a single step, every start below 10⁷ is at most 7 × 9² = 567, so all ten million chains funnel into the chains of those 567 values.