A Sobering Problem

Anything goes, but keep it seemly...

Re: A Sobering Problem

Postby JPF » Sat Oct 12, 2013 5:28 pm

Here is my last and final proposal: a sequence of 8290 primes out of 8363 candidates.
There is a cycle going from 13597 to 83597 with 8149 elements.

JPF
Attachments
WL8290.txt
(56.67 KiB) Downloaded 90 times
JPF
2017 Supporter
 
Posts: 3752
Joined: 06 December 2005
Location: Paris, France

Re: A Sobering Problem

Postby Leren » Tue Oct 15, 2013 4:34 am

<Edit>

Replaced previous files with new sequence of 8355 five digit primes starting at 15137. The largest cycle is between 99367 and 99767 with 8345 elements.

Leren
Attachments
Primes 5 Digit Ladder 8355 Numbers.txt
(97.95 KiB) Downloaded 97 times
Leren
 
Posts: 2930
Joined: 03 June 2012

Re: A Sobering Problem

Postby Leren » Thu Oct 24, 2013 1:22 am

I've appended 3 files to this post:

1. The longest 5 digit prime ladder I can find. This has 8357 numbers starting at 50857.

2. Three different prime ladder cycles each of length 8345 numbers (the longest such cycles I can find).

3. Results for the start prime 13597. This ladder has length 8328 with a longest cycle of length 8306 going from position 22 (37049) to position 8327 (37039).

Here is a link to the algorithm I used to get these results for this (highly non-trivial) problem. http://www.dharwadker.org/hamilton/

I''m still not sure whether the 8357 ladder or the 8345 cycles are maximal. The maximum possible ladder is 8360 and this must start and end with 2 of the 5 primes 46769, 97039, 97919, 98519, 99721. For a ladder that doesn't start with one of these primes the maximum is 8359. The maximum possible cycle could be up to 8358.

Leren
Attachments
Primes 5 Digit Ladder 13597.txt
(97.63 KiB) Downloaded 97 times
Primes 5 Digit Ladder 8345 Cycles.txt
(195.58 KiB) Downloaded 89 times
Primes 5 Digit Ladder 8357 Numbers.txt
(97.93 KiB) Downloaded 89 times
Leren
 
Posts: 2930
Joined: 03 June 2012

Re: A Sobering Problem

Postby Leren » Fri Oct 25, 2013 3:55 am

I should have thought of this before. Regarding my previous post, any prime that appears in the 8345 prime cycles I found can be used as the start of a ladder of length 8345.

Surprise, surprise, 13597 appears in all three 8345 prime cycles (and in a different sequence in each of the three) from which it is easy to create three different 8345 prime ladders starting with 13597.

I've attached a file containing one of these.

Leren
Attachments
Primes 5 Digit Ladder 13597 - 8345 Cycle.txt
(97.79 KiB) Downloaded 95 times
Leren
 
Posts: 2930
Joined: 03 June 2012

Re: A Sobering Problem

Postby Leren » Tue Oct 29, 2013 5:23 am

I've found a maximal 5 digit prime ladder consisting of 8360 primes starting with the singly connected prime 97039 and ending with the singly connected prime 98519. The only 5 digit primes not included in this ladder are the other three singly connected primes 46769, 97919 & 99721.

Leren

<Edit> I've also found a maximal 5 digit prime cycle consisting of 8358 primes. This includes all 5 digit primes except for the 5 singly connected primes mentioned above. The cycle can start and finish at any point but for convenience I've started it at 13597 and it "ends" at 43597.

Leren
Attachments
Primes 5 Digit Ladder 13597 - 8358 Cycle.txt
(97.94 KiB) Downloaded 94 times
Primes 5 Digit Ladder 8360 Numbers.txt
(97.97 KiB) Downloaded 93 times
Leren
 
Posts: 2930
Joined: 03 June 2012

Re: A Sobering Problem

Postby JPF » Wed Oct 30, 2013 10:12 am

Hi, Leren

Congratulations for your findings!
I admire your perseverance to solve this problem.
Finding a Hamiltonian path in a large graph is challenging, but I must admit I was not really motivated by finding paths among prime numbers :oops:
I have also read the article you mentioned, but I didn't implement all the (complex) algorithm. I only kept the following idea:
"For each unvisited neighbor w of vr, compute η(w), the number of unvisited neighbors of w. Select vr+1 = w such that η(w) is a minimum "
I randomly selected a minimum.
I finally turned off my computer after reaching 8290 because progress was too slow.

JPF

PS: It's funny to see that Guenter Stertenbrink (dukuso in the sudoku's World) is indirectly involved in that paper.
JPF
2017 Supporter
 
Posts: 3752
Joined: 06 December 2005
Location: Paris, France

Re: A Sobering Problem

Postby Leren » Wed Oct 30, 2013 11:37 am

Hi JPF. To say that I'm completely stoked at achieving the results that I have would be an understatement, I'm totally blown away !

I had trouble with some parts of the complex algorithm. I left some out and added some ideas of my own. I can talk more about this if you are interested.

I'm thinking of trying something similar with words as opposed to primes, finding large word ladders and cycles, and I was wondering if you would be interested in this also. I think this will be a somewhat different task than for the primes because words appear to be much less densely interconnected than primes.

I'm preparing a "dictionary" of five letter words that I downloaded from the Zyzzyva site and I'm bowdlerizing it (I won't be using any bad language or other offensive terms on this or any other forum - for those unfamiliar with the Scrabble world
all swear words and other offensive terms such as racial epithets are allowed in Scrabble tournaments and so are included in Scrabble word lists). That way the results won't depend on who's been clever enough to find the right dictionary.

If you are interested in participating in this project please let me know and I'll upload the dictionary.

Leren
Leren
 
Posts: 2930
Joined: 03 June 2012

Re: A Sobering Problem

Postby JPF » Wed Oct 30, 2013 4:52 pm

I'm preparing a "dictionary" of five letter words that I downloaded from the Zyzzyva site and I'm bowdlerizing it (I won't be using any bad language or other offensive terms on this or any other forum - for those unfamiliar with the Scrabble world
all swear words and other offensive terms such as racial epithets are allowed in Scrabble tournaments and so are included in Scrabble word lists). That way the results won't depend on who's been clever enough to find the right dictionary.

If you are interested in participating in this project please let me know and I'll upload the dictionary.

Why not... but finding the longest SHORTEST word ladder doesn't not require an elaborate algorithm. It's just a question of computational time.
See here or here for example.
I am actually working on a different idea with six letter words.
I am not ready yet but will be in a while. In the meantime, my computer may be busy.

JPF
JPF
2017 Supporter
 
Posts: 3752
Joined: 06 December 2005
Location: Paris, France

Re: A Sobering Problem

Postby Smythe Dakota » Thu Oct 31, 2013 2:07 am

When it comes to words instead of numbers, why not a bell-curve type puzzle?

At each step, instead of changing one letter, you'd add one letter. Eventually, you'd start subtracting one letter. You'd end up with a different word than you started with, although the words at both ends would have the same number of letters.

Bill Smythe
Smythe Dakota
 
Posts: 534
Joined: 11 February 2006

Re: A Sobering Problem

Postby Leren » Tue Nov 05, 2013 11:06 am

As promised (or threatened) I've uploaded a bowlderised 5 letter word "dictionary"". It's in 2 parts to keep within the max allowed file size.

As for longest SHORTEST word ladders go I am satisfied that we have found d5 = 27 and d6 = 44. I am not seeking to improve on these.

I am currently looking for the longest LONGEST five letter word ladder - D5. The dictionary contains 12571 words of which 803 have no neighbours and 1162 have only 1 neighbour.

In theory this might allow for a maximal longest LONGEST word ladder of 10608 words and cyclic word ladder of 10606 words.

From my investigations to date I don't believe these figures can be approached. The longest word ladder I've found to date has 8690 words and the longest cyclic word ladder has 8620 words.

It will take a few more days to complete my investigations.

Leren

<Edit>

After checking all start words the longest 5 letter Word ladder I found has 8699 elements ie D5 = 8699. I found 2 cyclic word ladders of length 8690.

Leren
Attachments
Scrabble 5 Letter Full Word List Bowdlerised - Part 2.txt
(238.24 KiB) Downloaded 101 times
Scrabble 5 Letter Full Word List Bowdlerised - Part 1.txt
(236 KiB) Downloaded 98 times
Leren
 
Posts: 2930
Joined: 03 June 2012

Re: A Sobering Problem

Postby dukuso2 » Mon Dec 02, 2013 11:29 am

I don't remember having worked on such problems.
knight tours, hamilton paths was my hobby in ~2003, there should be
hampath.exe somewhere on magictour.free.fr
-----------------------------
OK, I found it here: http://magictour.free.fr/HAMPATH.C5
uploaded probably 2004/08/11

it takes ~20sec on the Hajo1-3 graph from here:
http://www.aya.or.jp/~babalabo/Ariadne/ ... chor260046

0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0
1 0 1 1 0 0 1 0 1 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0
0 1 0 1 0 0 1 0 0 0 0 0 0 0 0 1 0 0 1 1 0 1 0 0 1
0 1 1 0 0 0 1 0 0 0 0 1 0 0 1 1 0 0 0 1 0 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 0 0 0 0 1 0 0 1
0 1 1 1 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 1 0 1 0
0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0
1 1 0 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1
0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 1 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0
0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 0
0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0 1 0 0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 1 0 1 0 0
0 0 1 0 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 1
0 1 1 1 0 0 1 0 0 0 0 0 0 0 0 1 0 1 0 0 1 1 0 0 0
0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 1 0 1 0 0 0 0 0
0 1 1 1 0 1 1 0 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 0
1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 1 1 0 0 0 0 0 0 0 0
0 0 1 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 1 0 0 0 0 0 0

------------------------------------------------------------------------------------------------------------
JPF wrote:Hi, Leren

Congratulations for your findings!
I admire your perseverance to solve this problem.
Finding a Hamiltonian path in a large graph is challenging, but I must admit I was not really motivated by finding paths among prime numbers :oops:
I have also read the article you mentioned, but I didn't implement all the (complex) algorithm. I only kept the following idea:
"For each unvisited neighbor w of vr, compute η(w), the number of unvisited neighbors of w. Select vr+1 = w such that η(w) is a minimum "
I randomly selected a minimum.
I finally turned off my computer after reaching 8290 because progress was too slow.

JPF

PS: It's funny to see that Guenter Stertenbrink (dukuso in the sudoku's World) is indirectly involved in that paper.
dukuso2
 
Posts: 13
Joined: 28 November 2013

Previous

Return to Coffee bar