Admin: replace source tag with syntaxhighlight tag (via update-page on MediaWiki MCP Server)

2026-06-24T17:20:54Z

replace source tag with syntaxhighlight tag (via update-page on MediaWiki MCP Server)

← Older revision		Revision as of 17:20, 24 June 2026
Line 1:		Line 1:

	This is problem 92 on Project Euler: https://projecteuler.net/problem=92		This is problem 92 on Project Euler: https://projecteuler.net/problem=92

Line 42:		Line 43:
	: https://git.charlesreid1.com/cs/euler/src/branch/main/java/Problem092.java		: https://git.charlesreid1.com/cs/euler/src/branch/main/java/Problem092.java

	<~~source~~ lang="java">		<syntaxhighlight lang="java">
	public class Problem092 {		public class Problem092 {

Line 76:		Line 77:
	}		}
	}		}
	</~~source~~>		</syntaxhighlight>

	=Flags=		=Flags=

Admin: Create Project Euler/92 page with problem statement, solution approach, and Java solution (via create-page on MediaWiki MCP Server)

2026-06-24T11:29:55Z

Create Project Euler/92 page with problem statement, solution approach, and Java solution (via create-page on MediaWiki MCP Server)

New page

This is problem 92 on Project Euler: https://projecteuler.net/problem=92

=Overview of the Problem=

==Question==

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,

:<math>44 \to 32 \to 13 \to 10 \to \mathbf{1} \to \mathbf{1}</math>
:<math>85 \to \mathbf{89} \to 145 \to 42 \to 20 \to 4 \to 16 \to 37 \to 58 \to \mathbf{89}</math>

Therefore any chain that arrives at <math>1</math> or <math>89</math> will become stuck in an endless loop. What is most amazing is that '''every''' starting number will eventually arrive at <math>1</math> or <math>89</math>.

How many starting numbers below ten million will arrive at <math>89</math>?

=Solution Approach=

The key observation for this problem is that the sum of squared digits for any number below ten million is at most <math>7 \times 9^2 = 567</math>. This means every chain quickly collapses into the small state space <math>1 \dots 567</math>.

We can break the problem into two phases:

==Phase 1: Precompute chain destinations for 1 through 567==

For each integer <math>s</math> from <math>1</math> to <math>567</math>, follow its digit-square-sum chain until it reaches either <math>1</math> or <math>89</math>. Cache the result (a boolean: <code>true</code> if the chain arrives at <math>89</math>) in an array. Walking the chain is cheap because these numbers are small, and once a chain hits a previously cached value, we can short-circuit.

==Phase 2: Count arrivals at 89 for all numbers below ten million==

For each starting number <math>n</math> from <math>1</math> to <math>9,999,999</math>:

# Compute <math>s = \text{sumOfSquaredDigits}(n)</math>. This value is in the range <math>0 \dots 567</math>.
# Look up the cached result for <math>s</math>.
# If the cached result is <code>true</code> (i.e., the chain ultimately reaches <math>89</math>), increment the count.

The <code>sumOfSquaredDigits</code> helper repeatedly extracts the last digit of <math>n</math>, squares it, adds it to a running sum, and divides <math>n</math> by <math>10</math>.

This approach runs in <math>O(N \cdot d)</math> time where <math>N = 10^7</math> and <math>d \approx 7</math> digits, making it fast enough for a single-threaded Java implementation.

=Java Solution=

The full implementation is available in the Euler Git repository:

: https://git.charlesreid1.com/cs/euler/src/branch/main/java/Problem092.java

<source lang="java">
public class Problem092 {

private static int sumOfSquaredDigits(int n) {
int sum = 0;
while (n > 0) {
int d = n % 10;
sum += d * d;
n /= 10;
}
return sum;
}

public static void main(String[] args) {
boolean[] cache = new boolean[568];

for (int i = 1; i <= 567; i++) {
int n = i;
while (n != 1 && n != 89) {
n = sumOfSquaredDigits(n);
}
cache[i] = (n == 89);
}

int count = 0;
for (int i = 1; i < 10_000_000; i++) {
if (cache[sumOfSquaredDigits(i)]) {
count++;
}
}

System.out.println(count);
}
}
</source>

=Flags=

{{ProjectEulerFlag}}

[[Category:Project Euler]]
[[Category:Java]]
[[Category:Number Theory]]

Project Euler/92 - Revision history

Admin: replace source tag with syntaxhighlight tag (via update-page on MediaWiki MCP Server)

Admin: Create Project Euler/92 page with problem statement, solution approach, and Java solution (via create-page on MediaWiki MCP Server)