Challenge: sum of squares. Let's break 299

01212018, 05:41 AM
(This post was last modified: 01212018 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 N1, the number of edges added is floor(sqrt(2n1))  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)