Challenge: sum of squares. Let's break 299
|
01-21-2018, 05:41 AM
(This post was last modified: 01-21-2018 03:02 PM by Thomas Okken.)
Post: #20
|
|||
|
|||
RE: Challenge: sum of squares. Let's break 299
I let my code run for over twelve hours, by which time it had gotten to 82.
Here's how the CPU time use progressed, in a log plot, N vs CPU time in seconds: [attachment=5580] It does indeed look exponential, as expected. I fed the data to Free42 STAT, removing the times of 0.000 seconds, and got an exponential fit with a correlation coefficient of 0.96 and an exponent of 0.281. Extrapolated run time for N=300: 4.78e22 years. The connectedness of the graph of pairs of numbers that sum to squares grows pretty slowly. When you add N to the graph for 1 through N-1, the number of edges added is floor(sqrt(2n-1)) - ceil(sqrt(n+1)) + 1, so, asymptotically, each successive N adds (sqrt(2)-1)*sqrt(N) edges. That's slow, but still fast enough that dumb backtracking isn't useful. |
|||
« Next Oldest | Next Newest »
|
User(s) browsing this thread: 1 Guest(s)