Related Tags

euler
c++
pyhton

# How to solve the 'number spiral diagonals' problem

A spiral diagonal is formed when you take a number, 1, and increase that number as you move to the right and below. This forms a spiral.

The following slides show how a number spiral is formed for a 4x4 matrix.

1 of 9

The sum of the diagonals in a 3x3 number spiral is $25$.

In the number spirals diagonal problem, the sum of diagonals for nxn needs to be found.

If one looks closely, one can find a pattern. Consider the following matrix.

The values in each diagonal correspond to:

$a_{n} = (9, 25, 49, 81 ...)$ $b_{n} = (7, 21, 43, 73 ...)$ $c_{n} = (5, 17, 37, 65 ...)$ $d_{n} = (3, 13, 31, 57 ...)$

These correspond to the following sequence:

$a_{n} = 4n^2+4n+1$ $b_{n} = 4n^2+2n+1$
$c_{n} = 4n^2+1$
$d_{n} = 4n^2-2n+1$

The sum of all the terms includes the one in the center; therefore, it becomes:

Sum(n) = $1+ \sum_{k=1}^n (a_i + b_i + c_i + d_i)$
Sum(n) = $1+\sum_{k=1}^n (16i^2 + 4i +4)$
Sum(n) = $1+\sum_{k=1}^n 16i^2 + \sum_{k=1}^n 4i + \sum_{k=1}^n4$

Using summation rules we can reduce it to:

Sum(n) = $\frac{3+2n(8n^2 + 15n +13)}{3}$

This simple formula can then be used to calculate the sum of the diagonal for the matrix of any dimension.

Remember: Here, n equals 1/2 the number of elements in a diagonal, excluding the center term.

n = $\frac{dim-1}{2}$

Where dim is the dimension of the matrix.

## Code

The following code shows how to find the sum of the diagonal in a number spiral for an nxn matrix.

#include <iostream>
using namespace std;
// declare function sum
int sum(int dim)
{
int n = (dim - 1) /2;//find n
// use the formula defined above
int x = (3 + 2 * n * ( 8 * n * n + 15 * n +13)) /3;

return x;
}
int main() {
// call the function and print the value
int diagonal = sum(5);
cout << diagonal << endl;
return 0;
}

RELATED TAGS

euler
c++
pyhton