Project Euler

Problem 28: 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?

The Catch

Discover the pattern that generates the numbers that lay on the 2 diagonals.

The Light

Take a look at a smaller square: This is a 3 x 3 square with side equals 3. Notice that the top-right corner number a can be computed using the formula a = (2*i + 1)² where i >= 1. Starting with i = 1, a = (2*1 + 1)² = 9.
Then, notice that the top-left corner number b can be computed using the formula b = a - 2*i with the same i that formulated a. So b = 9 - 2*1 = 7.
Similarly, bottom-left corner number c can be computed using c = b - 2*i with the same i that formulated b. So c = 7 - 2*1 = 5.
Lastly, bottom-right corner number d can be computed using d = c - 2*i with the same i that formulated c. So d = 5 - 2*1 = 3.
With the 3 x 3 square, i increments to 1. If you repeat this pattern for the 5 x 5 square the number i increments to 2. Due to the spiral nature of these n x n squares, n cannot be even. Thus i only increments to n/2, dropping all decimals.

The Code

public class Problem28
{
  public static void main(String[] args)
  {
    int total = 1;                     //Sequence starts with 1, the ring number
    int width = 1001/2;                  
    for(int i = 1; i <= width; i++)
    {
      int tmp = (2*i + 1) * (2*i + 1);
      total += tmp;

      //Moving counter clockwise
      tmp = tmp - 2*i;
      total += tmp;

      tmp = tmp - 2*i;
      total += tmp;

      tmp = tmp - 2*i;
      total += tmp;
    }
    System.out.println(total);
  }
}