Project Euler Problem #92

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×9² (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

def answer = 0

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
  if (sum == 89) answer++
}

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 10⁷ 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
}

def answer = 0

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]++ }
    answer += permutations(nn)
  }
}

It’s all a little too verbose for my liking but does run in 0.57 seconds so nicely succeeds in the objective. Expanding out the listops to explicit loops in the gen_digits() generator method reduces the runtime to 0.36 seconds – a substantial saving of 37% but at the expense of a few more lines of code.

Conclusion

Groovy general “slowness” meant that some “cleverness” was required to get this to execute in a reasonable amount of time. If I’d been using C++ or native Java for this I would have just stuck with the simple initial approach.