Home
> Programming > Project euler 28: Number spiral diagonals

## Project euler 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:

**21** 22 23 24 **25**

20 **7** 8 **9** 10

19 6 **1** 2 11

18 **5** 4 **3** 12

**17** 16 15 14 **13**

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?

def diag(n): sum = 0 for i in range(0, int(n / 2) + 1): sum += (2 * i + 1) * (2 * i + 1) sum += (4 * i * i + 1) sum += (2 * i + 1) * (2 * i + 1) - 2 * i sum += (2 * i + 1) * (2 * i + 1) - 6 * i return sum - 3 print (diag(1001))

Answer: 669171001

Time complexity: O(4 * n / 2) ~ O(n)

Space complexity: O(1)

Advertisements

Categories: Programming
project euler

Comments (0)
Trackbacks (0)
Leave a comment
Trackback