patternpythonMinor
Efficiency of Project Euler 28 - number spiral diagonals
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.
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.
$$(\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.