Number Spiral Diagonals

Starting with the number \(1\) and moving to the right in a clockwise direction a \(5\) by \(5\) spiral is formed as follows:

It can be verified that the sum of the numbers on the diagonals is \(101\).

What is the sum of the numbers on the diagonals in a \(1001\) by \(1001\) spiral formed in the same way?

Solution

In that kind of problems I usually try to figure out the formula of how the numbers increase. We could try to draw the whole array, but Project Euler problems aren’t about brute strength. Let’s try it!

The first fact: all sums of the diagonals will eventually end up in the middle, where we have 1. So, we’ll always need to add 1 to our result.

Each “layer” of the array grows proportionally. They always have 4 numbers on each diagonal.

On the first “layer”, the outermost numbers of the 3x3 spiral, we have: \(3, 5, 7, 9\).

On the next one, for a 5x5 spiral: \(13, 17, 21, 25\). Is there any pattern they follow?

There are always 4 numbers, and they increase linearly.

In the 3x3 spiral, they increase by 2.

In a 5x5 spiral, they increase by 4.

If you draw a 7x7 spiral, you could see that they increase by 6. It’s kind of logical, that the increase depends on the length of the spiral: it’s just length - 1.

What about the initial number? What I noticed is that for a 3x3 spiral, the biggest number is 9. For a 5x5 spiral it’s 25. That looks like a square. So, if we use n for the length of the spiral, the numbers that it’s composed of are as follows:

• n * n
• n * n - (n - 1)
• n * n - 2 * (n - 1)
• n * n - 3 * (n - 1)

All we need to do is to substitute the n with the spiral length, starting from 3. We increase n by two until we hit 1001. And don’t forget about the initial 1.

object Euler028 extends EulerApp {

  override def execute(): Long = {
    1 + Iterator
      .from(3, 2)
      .takeWhile(_ <= 1001)
      .map(sumForDiagonal)
      .sum
  }

  private def sumForDiagonal(n: Int): Int = {
    n * n +
      n * n - (n - 1) +
      n * n - 2 * (n - 1) +
      n * n - 3 * (n - 1)
  }
}

That’s all. The solution is pretty neat, it does exactly what we did in a pen and paper approach.