Post Reply 
Challenge: sum of squares. Let's break 299
01-25-2018, 05:54 PM (This post was last modified: 01-25-2018 05:56 PM by pier4r.)
Post: #46
RE: Challenge: sum of squares. Let's break 299
(01-24-2018 10:29 PM)Allen Wrote:  Thomas,
Thank you for verifying those solutions! It's always nice to have a second set of eyes. I have an important event in less than an hour, but generally speaking, I think the hamiltonian approach is good for random-walk kind of graphs, but these "square" graphs have some interesting properties we can exploit.

Namely, there are bottlenecks in the graph. For N=71 ( and numbers around there) the bottleneck is 50. There is only 1 or 2 ways to include 50 in the string.

By sorting the nodes of the graph according to how many outgoing edges there are, one can write a penalty/reward scoring to promote those strings that contain the most bottlenecks. Make a population of possible strings, and sort them according to their score, decimating to only keeping a portion of the resulting population.

I'm still trying to find the optimal settings for decimation, and growth rates to ensure the population does not collapse, while still finishing reasonably quickly. Will post more as soon as I'm able.

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 :)
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 - pier4r - 01-25-2018 05:54 PM

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