Post Reply 
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. Big Grin

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.
Visit this user's website Find all posts by this user
Quote this message in a reply
Post Reply 


Messages In This Thread
RE: Challenge: sum of squares. Let's break 299 - Thomas Okken - 01-21-2018 05:41 AM



User(s) browsing this thread: 1 Guest(s)