Challenge: sum of squares. Let's break 299

01252018, 02:17 AM
Post: #41




RE: Challenge: sum of squares. Let's break 299
(01192018 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. I haven't read through the git lab code or the youtube comments.. do you know what the maximum is now? 17bii  32s  32sii  41c  41cv  41cx  42s  48g  48g+  48gx  50g  30b 

01252018, 03:25 AM
(This post was last modified: 01252018 10:10 AM by Allen.)
Post: #42




RE: Challenge: sum of squares. Let's break 299
I believe there are multiple solutions to each graph walk. For example the 999 run above returned 3 unique solutions. For the first 888 items, the graphs walks are the same, but from there on, there are slightly different cycles in the 3 found solutions.
Here are the position numbers and the values for the last 122 steps for each of the 3 solutions. Code:
Edit to add: Note part of the multiple solutions has to do with "skeleton key" cycles like (6,19,30) that can appear in any order together. Mathematically these are the solutions occur when all permutations of a given numbers are subsets of the 3node graph. On the N=1000 graph there are only 828 such wonders (*6 if you include the permutations) out of 300300 valid combinations of 3 nodes. Each of these strings is an opportunity to create a new cycle in the graph. Since the smallest pair of these is: (6, 19, 30) and (5, 20, 44), If at least one solution exists for N>=44, there could be multiple solutions, since any solution could contain a pair of these special strings (one to depart the main thread and the other to come back). A more thorough proof would prove that there are no isolated parts of the a particular graph (i.e. closed cycle), and that it contained one of these "skeleton keys". Here are the most frequent nodes in the N=1000 graph super nodes with their associated counts: Code:
an interesting pattern.. 17bii  32s  32sii  41c  41cv  41cx  42s  48g  48g+  48gx  50g  30b 

01252018, 04:19 AM
(This post was last modified: 01252018 05:04 AM by Allen.)
Post: #43




RE: Challenge: sum of squares. Let's break 299
Code to find these super nodes:
Code:
17bii  32s  32sii  41c  41cv  41cx  42s  48g  48g+  48gx  50g  30b 

01252018, 09:33 AM
Post: #44




RE: Challenge: sum of squares. Let's break 299
@Allen: impressive work, really appreciated
Software Failure: Guru Meditation  Antonio IU2KIY 

01252018, 10:53 AM
(This post was last modified: 01252018 10:54 AM by Allen.)
Post: #45




RE: Challenge: sum of squares. Let's break 299
number of unique solutions found for each round (includes reversals):
(this is not exhaustive, just how many were left after 1 run) Unique solutions found for len 15: 2 Unique solutions found for len 16: 2 Unique solutions found for len 17: 2 Unique solutions found for len 23: 6 Unique solutions found for len 25: 20 Unique solutions found for len 26: 24 Unique solutions found for len 27: 58 Unique solutions found for len 28: 56 Unique solutions found for len 29: 20 Unique solutions found for len 30: 22 Unique solutions found for len 31: 142 Unique solutions found for len 32: 124 Unique solutions found for len 33: 44 Unique solutions found for len 34: 40 Unique solutions found for len 35: 88 Unique solutions found for len 36: 40 Unique solutions found for len 37: 46 Unique solutions found for len 38: 28 Unique solutions found for len 39: 18 Unique solutions found for len 40: 18 Unique solutions found for len 41: 24 Unique solutions found for len 42: 20 Unique solutions found for len 43: 30 Unique solutions found for len 44: 6 Unique solutions found for len 45: 24 Unique solutions found for len 46: 6 Unique solutions found for len 47: 2 Unique solutions found for len 48: 4 Unique solutions found for len 49: 12 Unique solutions found for len 50: 22 Unique solutions found for len 51: 8 Unique solutions found for len 52: 8 Unique solutions found for len 53: 18 Unique solutions found for len 54: 4 Unique solutions found for len 57: 8 Unique solutions found for len 60: 4 Unique solutions found for len 61: 4 Unique solutions found for len 63: 20 Unique solutions found for len 64: 12 Unique solutions found for len 65: 4 Unique solutions found for len 66: 8 Unique solutions found for len 67: 4 Unique solutions found for len 69: 2 Unique solutions found for len 71: 6 Unique solutions found for len 72: 36 Unique solutions found for len 73: 24 Unique solutions found for len 74: 22 Unique solutions found for len 76: 8 Unique solutions found for len 78: 14 Unique solutions found for len 80: 16 Unique solutions found for len 84: 14 Unique solutions found for len 85: 18 Unique solutions found for len 86: 6 Unique solutions found for len 87: 10 Unique solutions found for len 88: 26 Unique solutions found for len 89: 40 Unique solutions found for len 90: 16 Unique solutions found for len 91: 2 Unique solutions found for len 92: 10 Unique solutions found for len 93: 10 Unique solutions found for len 96: 6 Unique solutions found for len 97: 18 Unique solutions found for len 98: 8 17bii  32s  32sii  41c  41cv  41cx  42s  48g  48g+  48gx  50g  30b 

01252018, 05:54 PM
(This post was last modified: 01252018 05:56 PM by pier4r.)
Post: #46




RE: Challenge: sum of squares. Let's break 299
(01242018 10:29 PM)Allen Wrote: Thomas, Really nice. I have my ideas on the problem. Yes I know that it falls in a general problem that is NP hard, but special cases of a problem could be not necessary that hard. I encourage you to contact numberphile/matt parker (standupmaths on youtube) for the solution. Also I skimmed quickly what you wrote because I don't want to be influenced before attempting the problem myself (if I ever find time). What is making me happy is that I knew that this forum has really enthusiastic members. edit: oh and ultra thanks for sharing! It is always a bit meh when people find a not easy solutions and they don't share it (even on a paper). So you did great. Wikis are great, Contribute :) 

01252018, 11:10 PM
Post: #47




RE: Challenge: sum of squares. Let's break 299
Thank you! Today on my 7yearoldPC with only 16Gb Ram I calculated 81 unique paths with N=1500. I'd say it's no where near the upper limits of what can be done on a modern PC with multiple cores and larger memory!!
17bii  32s  32sii  41c  41cv  41cx  42s  48g  48g+  48gx  50g  30b 

01262018, 12:29 AM
(This post was last modified: 01262018 12:29 AM by TheKaneB.)
Post: #48




RE: Challenge: sum of squares. Let's break 299
(01252018 11:10 PM)Allen Wrote: Thank you! Today on my 7yearoldPC with only 16Gb Ram I calculated 81 unique paths with N=1500. I'd say it's no where near the upper limits of what can be done on a modern PC with multiple cores and larger memory!! And also, python is not designed for speed. A C or C++ implementation (or even Java or C#) would be much faster! The really nice part is the algorithm that you built, that made the real difference Software Failure: Guru Meditation  Antonio IU2KIY 

01262018, 08:15 PM
Post: #49




RE: Challenge: sum of squares. Let's break 299
(01252018 11:10 PM)Allen Wrote: Thank you! Today on my 7yearoldPC with only 16Gb Ram I calculated 81 unique paths with N=1500. I'd say it's no where near the upper limits of what can be done on a modern PC with multiple cores and larger memory!!16 gb of ram? My pc at work is from 2017 (mabook pro retina 13' with touch bar) and it has less. Appreciate your little monster! Also this means that on a calculator would be extra difficult to reach numbers after 3040 (I am guessing). Wikis are great, Contribute :) 

01262018, 10:01 PM
(This post was last modified: 01262018 10:35 PM by Allen.)
Post: #50




RE: Challenge: sum of squares. Let's break 299
I found a speed up and can now calculate N=1000 solution in under 20 seconds.
N=2000 takes <3 min N=3500 about 16 min 17bii  32s  32sii  41c  41cv  41cx  42s  48g  48g+  48gx  50g  30b 

01272018, 01:23 PM
(This post was last modified: 01272018 01:24 PM by pier4r.)
Post: #51




RE: Challenge: sum of squares. Let's break 299
(01262018 10:01 PM)Allen Wrote: I found a speed up and can now calculate N=1000 solution in under 20 seconds. I hope you share your findings somewhere (git repositories, articles on some magazines or journals, your blog, etc.). If something is new or relatively new, that is few know how to use it, it is a pity to not share it because it may be lost until someone else with same abilities looks into the topic. I always remember the middle square "random" procedure. Discovered in ~1950 and recorded in a journal. It was already recorded in ~1930 and in ~1250 (yes, twelfth hundred fifty) . I wondered how many times it was independently discovered until the knowledge of the procedure was more widespread after 1950. Now reinventing the wheel because one wants to is all ok, reinventing the wheel because all the previous one got lost is a necessity (there are no wheels) but also a pity (no one cares about leaving the wheels survive). Wikis are great, Contribute :) 

01272018, 02:14 PM
Post: #52




RE: Challenge: sum of squares. Let's break 299
(01272018 01:23 PM)pier4r Wrote:(01262018 10:01 PM)Allen Wrote: I found a speed up and can now calculate N=1000 solution in under 20 seconds. Pier, I think you already made your point several times now... ;) Greetings, Massimo +×÷ ↔ left is right and right is wrong 

01282018, 04:14 PM
(This post was last modified: 01282018 05:32 PM by Allen.)
Post: #53




RE: Challenge: sum of squares. Let's break 299
(01272018 01:23 PM)pier4r Wrote:(01262018 10:01 PM)Allen Wrote: I found a speed up and can now calculate N=1000 solution in under 20 seconds. I plan to.. I was out of town this weekend, but still working on some optimizations. The N=3500 graph now completes in 2 min 14 sec. I would like to get a little computer time finding the right pruning hyperparameters before putting out more code, but the general solution is still the same.. just the pruning and generation is different. Edit.. now N=3500 finishes in 1.3 seconds 17bii  32s  32sii  41c  41cv  41cx  42s  48g  48g+  48gx  50g  30b 

01292018, 07:13 PM
Post: #54




RE: Challenge: sum of squares. Let's break 299
(01282018 04:14 PM)Allen Wrote:(01272018 01:23 PM)pier4r Wrote: I hope you share your findings somewhere... 16 minutes down to 1.3 seconds. That's ... quite an improvement. I'm no mathematician, but even I can tell you've definitely managed something impressive. (Post 163) Regards, BrickViking HP50g Casio fx9750G+ Casio fx9750GII (SH4a) 

01302018, 02:51 PM
Post: #55




RE: Challenge: sum of squares. Let's break 299
Hello folks,
I don't investigate very much time towards this problem. I beg your pardon if I wrote down a silly idea: If n = 299 then the biggest square number is 24^2 = (299 + 277), other possibilities (298 + 278) and so on. Maybe a initial program can generate all possible pairs of number which results in a square number. Is known wether every square number from 1^2 .. 24^2 appears? The same square number can appear more then one time (can be seen in the examples) and it is logical, too. Because the numbers from 1 to 299 give 298 pairs of sum... 

02012018, 03:38 AM
Post: #56




RE: Challenge: sum of squares. Let's break 299
Finalizing my code for this puzzle. I made some modifications to make it run from the command line, and also slow it down.. The superfast version I had earlier could not guarantee a solution. Takes 3 inputs:
Code:
I had a version that adjusted the results adaptively, but there are SO many possible solutions, it's not necessary. In my fast version, similar to this one, I only take into account the maxclip during the last few steps. I had many many trial runs on the 10,000 or 20,000 node graph that had only a few numbers remaining (always 100<N<1). So my improvement (slower but more accurate) is to update the scoring algorithm for each candidate solution so that it's not rewarded based on the centrality of the starting graph, but the centrality of the _remaining choices_. This made a substantial difference in number of solutions, but made the whole thing slower. So if you want it FAST on the 1000 graph: squares.py 1000 1 1000 (not guaranteed to find a solution..) adjust the 1 to 2 or 5 or 10 if you want lots of solutions for N=50: squares.py 50 100 100000 ( I think there are more than 250,000 unique solutions for N=50) 17bii  32s  32sii  41c  41cv  41cx  42s  48g  48g+  48gx  50g  30b 

02012018, 03:40 AM
Post: #57




RE: Challenge: sum of squares. Let's break 299
Code:
17bii  32s  32sii  41c  41cv  41cx  42s  48g  48g+  48gx  50g  30b 

02012018, 10:54 AM
(This post was last modified: 02012018 11:08 AM by TheKaneB.)
Post: #58




RE: Challenge: sum of squares. Let's break 299
Nice and compact!
There are a lot of Python trickeries, like ranges, zip, array slices, etc... but it should be possible to port it to HPPPL. I think you could cache the "squares" and maybe gain a bit more speed. EDIT: nevermind, I did try it and the difference is negligible. Software Failure: Guru Meditation  Antonio IU2KIY 

« Next Oldest  Next Newest »

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