HiveBrain v1.2.0
Get Started
← Back to all entries
patternpythonMinor

Efficiency of Project Euler 28 - number spiral diagonals

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
numberdiagonalsprojecteulerspiralefficiency

Problem

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 ms
print ("Found in %r ms." % (elapsed_time))

Solution

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.

Context

StackExchange Code Review Q#58423, answer score: 6

Revisions (0)

No revisions yet.