Efficiency of Project Euler 28 - number spiral diagonals

Question

I have written a solution for Problem 28.

Starting with the number 1 and moving to the right in a clockwise direction a 5 by 5 spiral is formed as follows:

$$\begin{array}{rrrrr} \color{red}{21} &22 &23 &24 &\color{red}{25}\\ 20 & \color{red}{7} & 8 & \color{red}{9} &10\\ 19 & 6 & \color{red}{1} & 2 &11\\ 18 & \color{red}{5} & 4 & \color{red}{3} &12\\ \color{red}{17} &16 &15 &14 &\color{red}{13}\\ \end{array}$$

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?

Since I am a beginner, I am looking for suggestions for improving the efficiency of my program.

from timeit import default_timer as timer
start = timer()
def find_sum(limit):
    limit*=limit
    num=1
    add=2
    result=1
    while num<limit:
        for i in range(4):
            num+=add
            result+=num
        add+=2
    return result
print (find_sum(1001))
elapsed_time = (timer() - start) * 1000 # s --> ms
print ("Found in %r ms." % (elapsed_time))      

Answer 1

It doesn't even need a loop if you simplify:

1. Notice each shell has a top right corner that is an odd number squared... 1,3,5
2. Notice each shell only adds 4 numbers: the square of an odd number (2n-1)^2, the same number with the distance to the previous corner removed, then the same with it removed twice, then three times... (2n-1)^2-(2n-2), (2n-1)^2-2*(2n-2), (2n-1)^2-3*(2n-2). That adds up to 4*(2n-1)^2 - 6*(2n-2), which you can simplify again to a simple quadratic. I'll probably screw it up if I try to do it in my head.
3. The 1001x1001 has n = 501

4. Now the meat of your loop looks like this:

   sum = 1 //innermost shell doesn't obey!
   for int i = 2 to 501
       sum += polynomial(i)
   

5. Since the polynomial is just quadratic, you can even substitute the triangular and pyramidal series in the sigma. sigma(x,n) = n(n+1)/2 and sigma(x^2,n) = n(n+1)(2n+1)/6 or something like that. That would make your program a single, simple polynomial, applicable to any size square.

Answer 2

An ultimate efficiency is in math. It can be shown that the result for \$2n+1\$ by \$2n+1\$ spiral is

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

The formula can be derived by induction. Another method is to realize that it must be a cubic dependency and fit the coefficients. And you can see that it is cubic, because numbers along the diagonals grow quadratically.