3
\$\begingroup\$

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))      
\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
6
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.