Euler Solution 28

From ProgSoc Wiki

Jump to: navigation, search

Solutions for Problem 28

Find the sum of the diagonals of a 1001 by 1001 spiral formed from the natural numbers 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

Haskell by SanguineV

Runtime: 8.8ms

{- There is a fairly simple formula based on the diagonals moving from the centre to
 - the top right corner.
 - First note that the value of these points is the odd numbers squared, i.e. 1,9,25...
 - Then that the value of the sum of the corners on each "ring" (except the first) is
 - given by:
 - (4 * x) - (6 * (sqrt(x) - 1))
 - Combine these and the sum of the spiral can be easily calculated based on the first
 - 500 (1001/2 - 1) odd numbers after 1 (and adding 1 for the centre). -}

main = print (foldl (\t x -> t + ((x * x * 4) - ((x - 1) * 6))) 1 (map (\x -> (x * 2) +1) [1..500]))

Yes, one line of code!


Python by Althalus

Runtime: 43 ms

import time
start_time = time.time()

#It can be seen in the 5x5 grid, that there are 5 numbers in each diagonal.
# :. in a 1001 by 1001 grid, there will be 101 numbers in the diagonal.
#It can be seen in the 5x5 grid, including the 1, diagonal up to the right are
#odd squares (3x3, 5x5)
#It can be seen that the bottom left diagonal are even squares +1 (2^2+1,4^2+1,6^2+1)
#Top left = (2*3)+1,(4*5)+1,(6*7)+1
#Bottom right = (1*2)+1,(3*4)+1,(5*6)+1,(7*8)+1,(9*10)+1
total = 0
ne_sw = 0
nw_se = 0
counter_1 = 0
counter_2 = 0

for i in range(1,1002,2):
        ne_sw += i**2
        counter_1 += 1
for i in range(2,1001,2):
        ne_sw += (i**2)+1
        counter_1 += 1
for i in range (1,1001,2):
        nw_se += (i*(i+1))+1
        counter_2 += 1
for i in range(2,1001,2):
        nw_se += (i*(i+1))+1
        counter_2 += 1
print(counter_1,', ',counter_2)
print(nw_se+ne_sw)
run_time = time.time() - start_time
print (run_time)
Personal tools