The New Sudoku Players' Forum

[JPF]

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

[Leren]

<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

[Leren]

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

[Leren]

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

[Leren]

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

[JPF]

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
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.

[Leren]

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

[JPF]

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

[Smythe Dakota]

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

[Leren]

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

[dukuso2]

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

------------------------------------------------------------------------------------------------------------

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
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.