Challenge: sum of squares. Let's break 299
01-20-2018, 05:43 PM (This post was last modified: 01-20-2018 05:44 PM by Thomas Okken.)
Post: #14
 Thomas Okken Senior Member Posts: 1,094 Joined: Feb 2014
RE: Challenge: sum of squares. Let's break 299
(01-19-2018 04:29 AM)Paul Dale Wrote:  If you follow the comments and links from the numberphile video, it looks like the maximum has been pushed up very significantly. Assuming the implementation was correct and addressed the problem in question etc.

Baring an inspired approach, the problem comes down to finding a Hamilton path in a graph. This is a NP complete problem.

What's NP-complete is the problem of finding Hamilton paths in graphs in general. For certain specific classes of graphs, that doesn't necessarily apply, like graphs where no node connects to more than two edges. The lady in the video, who wrote the program that checked all cases up to 299, must have found something to exploit, because with the apparently roughly exponential way the CPU time in my algorithm increases, it wouldn't get to 299 in a million years, even if I parallellized the heck out of it and ran it on the GPU clusters at work. (I should let it run a bit longer than I have so far to see how the CPU usage evolves, though.)
 « Next Oldest | Next Newest »

 Messages In This Thread Challenge: sum of squares. Let's break 299 - pier4r - 01-18-2018, 09:32 PM RE: Challenge: sum of squares. Let's break 299 - TheKaneB - 01-18-2018, 10:58 PM RE: Challenge: sum of squares. Let's break 299 - Didier Lachieze - 01-19-2018, 12:08 AM RE: Challenge: sum of squares. Let's break 299 - Didier Lachieze - 01-19-2018, 12:15 PM RE: Challenge: sum of squares. Let's break 299 - Paul Dale - 01-19-2018, 04:29 AM RE: Challenge: sum of squares. Let's break 299 - Thomas Okken - 01-20-2018 05:43 PM RE: Challenge: sum of squares. Let's break 299 - John Keith - 01-20-2018, 08:19 PM RE: Challenge: sum of squares. Let's break 299 - Paul Dale - 01-20-2018, 10:13 PM RE: Challenge: sum of squares. Let's break 299 - Thomas Okken - 01-20-2018, 10:31 PM RE: Challenge: sum of squares. Let's break 299 - Allen - 01-25-2018, 02:17 AM RE: Challenge: sum of squares. Let's break 299 - Thomas Okken - 01-19-2018, 04:29 AM RE: Challenge: sum of squares. Let's break 299 - Paul Dale - 01-19-2018, 06:31 AM RE: Challenge: sum of squares. Let's break 299 - Thomas Okken - 01-19-2018, 06:48 AM RE: Challenge: sum of squares. Let's break 299 - pier4r - 01-19-2018, 12:40 PM RE: Challenge: sum of squares. Let's break 299 - Didier Lachieze - 01-19-2018, 12:47 PM RE: Challenge: sum of squares. Let's break 299 - Didier Lachieze - 01-19-2018, 04:26 PM RE: Challenge: sum of squares. Let's break 299 - Thomas Okken - 01-19-2018, 04:33 PM RE: Challenge: sum of squares. Let's break 299 - Didier Lachieze - 01-19-2018, 04:56 PM RE: Challenge: sum of squares. Let's break 299 - ggauny@live.fr - 01-20-2018, 06:15 PM RE: Challenge: sum of squares. Let's break 299 - Thomas Okken - 01-20-2018, 09:08 PM RE: Challenge: sum of squares. Let's break 299 - Thomas Okken - 01-21-2018, 05:41 AM RE: Challenge: sum of squares. Let's break 299 - Gilles59 - 01-21-2018, 10:44 PM RE: Challenge: sum of squares. Let's break 299 - Thomas Okken - 01-22-2018, 01:40 AM RE: Challenge: sum of squares. Let's break 299 - TheKaneB - 01-22-2018, 11:54 AM RE: Challenge: sum of squares. Let's break 299 - Thomas Okken - 01-22-2018, 01:11 PM RE: Challenge: sum of squares. Let's break 299 - TheKaneB - 01-22-2018, 03:19 PM RE: Challenge: sum of squares. Let's break 299 - Gilles59 - 01-22-2018, 08:49 PM RE: Challenge: sum of squares. Let's break 299 - Allen - 01-24-2018, 09:18 PM RE: Challenge: sum of squares. Let's break 299 - Thomas Okken - 01-24-2018, 09:43 PM RE: Challenge: sum of squares. Let's break 299 - Allen - 01-24-2018, 10:03 PM RE: Challenge: sum of squares. Let's break 299 - Allen - 01-24-2018, 10:08 PM RE: Challenge: sum of squares. Let's break 299 - Allen - 01-24-2018, 10:14 PM RE: Challenge: sum of squares. Let's break 299 - Thomas Okken - 01-24-2018, 10:16 PM RE: Challenge: sum of squares. Let's break 299 - TheKaneB - 01-24-2018, 10:22 PM RE: Challenge: sum of squares. Let's break 299 - Allen - 01-24-2018, 10:29 PM RE: Challenge: sum of squares. Let's break 299 - pier4r - 01-25-2018, 05:54 PM RE: Challenge: sum of squares. Let's break 299 - Allen - 01-24-2018, 10:32 PM RE: Challenge: sum of squares. Let's break 299 - Thomas Okken - 01-24-2018, 10:33 PM RE: Challenge: sum of squares. Let's break 299 - Allen - 01-25-2018, 01:47 AM RE: Challenge: sum of squares. Let's break 299 - Allen - 01-25-2018, 01:49 AM RE: Challenge: sum of squares. Let's break 299 - Allen - 01-25-2018, 01:55 AM RE: Challenge: sum of squares. Let's break 299 - Allen - 01-25-2018, 02:04 AM RE: Challenge: sum of squares. Let's break 299 - Allen - 01-25-2018, 03:25 AM RE: Challenge: sum of squares. Let's break 299 - Allen - 01-25-2018, 04:19 AM RE: Challenge: sum of squares. Let's break 299 - TheKaneB - 01-25-2018, 09:33 AM RE: Challenge: sum of squares. Let's break 299 - Allen - 01-25-2018, 10:53 AM RE: Challenge: sum of squares. Let's break 299 - Allen - 01-25-2018, 11:10 PM RE: Challenge: sum of squares. Let's break 299 - TheKaneB - 01-26-2018, 12:29 AM RE: Challenge: sum of squares. Let's break 299 - pier4r - 01-26-2018, 08:15 PM RE: Challenge: sum of squares. Let's break 299 - Allen - 01-26-2018, 10:01 PM RE: Challenge: sum of squares. Let's break 299 - pier4r - 01-27-2018, 01:23 PM RE: Challenge: sum of squares. Let's break 299 - Massimo Gnerucci - 01-27-2018, 02:14 PM RE: Challenge: sum of squares. Let's break 299 - Allen - 01-28-2018, 04:14 PM RE: Challenge: sum of squares. Let's break 299 - brickviking - 01-29-2018, 07:13 PM RE: Challenge: sum of squares. Let's break 299 - peacecalc - 01-30-2018, 02:51 PM RE: Challenge: sum of squares. Let's break 299 - Allen - 02-01-2018, 03:38 AM RE: Challenge: sum of squares. Let's break 299 - Allen - 02-01-2018, 03:40 AM RE: Challenge: sum of squares. Let's break 299 - TheKaneB - 02-01-2018, 10:54 AM

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