License Public Domain
Lines 51
Keywords
Euler28 (8)
Permissions
Owner: jsimones
Group Owner: SnortSnort
Viewable by Everyone
Editable by All Siafoo Users
Hide
Free your code from a slow death on your hard drive Join Siafoo Now or Learn More

Project Euler 28 Atom Feed 0

# 's
 1"""
2Number spiral diagonals
3Problem 28
4Starting with the number 1 and moving to the right in a clockwise direction a 5
5by 5 spiral is formed as follows:
6
721 22 23 24 25
820 7 8 9 10
919 6 1 2 11
1018 5 4 3 12
1117 16 15 14 13
12
13It can be verified that the sum of the numbers on the diagonals is 101.
14
15What is the sum of the numbers on the diagonals in a 1001 by 1001 spiral formed
16in the same way?
17
18"""
19import numpy as np
20
21def spiral_diagonal_sum1(N):
22 """
23 Step through each corner number in the NxN spiral pattern, using the fact
24 that the side length of each concentric box grows by 2.
25
26 """
27 term, diagonal_sum = 1, 1
28 step, i = 2, 1 # dist b/w adjacent corners and the corner index (1 - 4)
29 while step <= N - 1:
30 term += step
31 diagonal_sum += term
32 i += 1
33 if i > 4:
34 step += 2
35 i = 1
36 return diagonal_sum
37
38def spiral_diagonal_sum2(N):
39 """
40 In a box of side length n, the number in the upper-right corner is n^2 and
41 the other corners are n^2 minus 1-, 2-, and 3-times n-1 (thanks, Mike!).
42 This is way faster than spiral_diagonal_sum1.
43
44 """
45 diagonal_sum = 1
46 for n in range(3, N + 1, 2):
47 diagonal_sum += 4 * n**2 - 6 * n + 6
48 return diagonal_sum
49
50def spiral_diagonal_sum3(N):
51 """
52 Numpy version of spiral_diagonal_sum2. Faster than spiral_diagonal_sum2.
53
54 """
55 n = np.arange(3, N + 1, 2)
56 box_sum = 4 * n**2 - 6 * n + 6
57 return np.sum(box_sum) + 1
58
59def main():
60 print spiral_diagonal_sum3(1001)
61
62if __name__ == '__main__':
63 main()