## Project Euler Problem #92

### September 11, 2010

Read the details of the problem here

Summary

Investigating a square digits number chain with a surprising property.

Solution

Simple and straight-forward non-mathematical problem to solve. I coded up the following program – note that after one pass the value of the sum of the squares will reduce to 7×92 (or 567) at most so the cache is relatively small for the entire range of numbers.

```def LIMIT = 10000000
def CACHE_SIZE = 9 * 9 * 7
def sumsOfSquares = new int[CACHE_SIZE+1]

Arrays.fill(sumsOfSquares,0)
sumsOfSquares[1] = 1
sumsOfSquares[89] = 89

for (i in 2..LIMIT) {

def sum = i

while ((sum != 1) && (sum != 89)) {
def n = sum
sum = 0

for (c in n.toString()) {
def v = c.toInteger()
sum += v * v
}

if (sumsOfSquares[sum] != 0) sum = sumsOfSquares[sum]
}
if (i <= CACHE_SIZE) sumsOfSquares[i] = sum
}
```

This ran in 36.14 seconds so it was well outside my 15 second target. I did some tweaks to the code converting it into to a recursive function and trying some extra cache lookups at the beginning of the calculation but only managed to reduce the runtime down to 31.81 seconds. (Using Groovy listops rather than the explicit loops for calculating the sum pushes the time out to over 2 minutes.) Although a straight Java conversion would probably run in a second or two I felt that some improvement could be made to the algorithm as the curent solution didn’t really use much of one to speak of.

The obvious observation is that the sum of squares function is being performed many times for numbers that are fundamentally the same as the sum will be the same for all permutations of a given set of digits i.e. the number 3241218, is the same as 2314821 or 1122348. A quick experiment revealed that there are only 11,440 such unique permutations – that would reduce the number of times the expensive summing operation had to be called by a factor of around 870.

In order to maintain the count it would be necessary to know many times a given set of digits can occur in the full 107 range. This is simply the factorial of the total number of elements divided by the product of the factorials of the counts of the unique elements.

As there were only a total of 7 digits I could have just coded nested loops to construct the numbers but I already had a generator for such a purpose built as part of the solution to Problem #110. This generates the digits in descending order and is general purpose but would do the job easily though, as it uses Groovy listops, isn’t the fastest means.

So it was just a case of pre-populating the cache, generating the unique digit sequences, calculating the initial sum of squares, pulling the terminal result from the cache and, for those that resulted in 89 getting the multiples of that to add to the total.

```def sumOfSquares(n) {
def sum = 0
for (c in n.toString()) {
def v = c.toInteger()
sum += v * v
}
return sum
}

def permutations(n) {
def factorials = [ 1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880 ]
def s = 1
for (i in n) {
s *= factorials[i]
}
return factorials[7].intdiv(s)
}

def gen_digits(range, maxlen, yield) {
gen_digits(range, maxlen, [], yield)
}

def gen_digits(range, maxlen, digits, yield) {
if (digits.size() == maxlen)
yield(digits)
else if (digits.size() == 0)
range.each { gen_digits(range, maxlen, [it], yield) }
else
range.findAll { it >= digits[0] }
.each { gen_digits(range, maxlen, [it]+digits, yield) }
}

def MAX = 9 * 9 * 7
def sumsOfSquares = new int[MAX+1]

Arrays.fill(sumsOfSquares,0)
sumsOfSquares[1] = 1
sumsOfSquares[89] = 89

for (i in 2..MAX) {
def sum = i
while ((sum != 1) && (sum != 89)) {
sum = sumOfSquares(sum)
if (sumsOfSquares[sum] != 0) sum = sumsOfSquares[sum]
}
sumsOfSquares[i] = sum
}

gen_digits((0..9), 7) { digits ->
def sum = sumsOfSquares[sumOfSquares(digits.join().toInteger())]
if (sum == 89) {
def nn = new int[10]
digits.each { nn[it]++ }