The New Sudoku Players' Forum

by **Leren** » Thu Oct 03, 2013 8:06 am

Smythe Dakota wrote:Let's do it with numbers. Somebody come up with two 5-digit prime numbers, and ask for a path between them, changing one digit at a time, such that every intermediate 5-digit number is prime.

Bill Smythe

As far as I can tell there are 8363 five digit prime numbers ranging from 10007 - 99991. Any two such primes can be connected via a minimum path of at most 10 steps (from the first prime). There is only 1 pair of five digit primes, 88259 and 99721 where a 10 step connection path is required, one such path being:

Code: Select all: 88259 1 78259 2 79259 3 79159 4 79151 5 79181 6 39181 7 39161 8 39761 9 99761 10 99721

A minimum connection path between the lowest and highest 5 digit primes (10007 and 99991) requires only 5 steps, one such path being:

Code: Select all: 10007 1 90007 2 90001 3 90901 4 99901 5 99991

What else would you like to know ?

Leren

<Edit> Corrected error in first path and improved presentation to be more consistent with previous discussions on word ladders.

Leren

by **JPF** » Thu Oct 03, 2013 9:53 am

Leren wrote: This is only required for 1 set of five digit primes, 88259 and 99761

What do you mean?

JPF

by **Leren** » Thu Oct 03, 2013 11:04 am

JPF wrote:
Leren wrote: This is only required for 1 set of five digit primes, 88259 and 99761

What do you mean?

JPF

What I mean is that my results indicate that if you pick any other pair of 5 digit primes then it is possible to construct a prime number ladder between then with less than 10 numbers
(or 9 steps from the first number in word ladder speak). The other example I gave was 10007 <-> 99991 for which a minimum ladder would have 6 numbers (5 steps from the first number).

Leren

by **JPF** » Thu Oct 03, 2013 12:23 pm

How do you go from 10111 to 65563 ?

JPF

by **Leren** » Thu Oct 03, 2013 9:43 pm

JPF wrote:How do you go from 10111 to 65563 ?

JPF

A minimum connection path from 10111 to 65563 is as follows:

Code: Select all: 10111 1 10211 2 12211 3 12251 4 32251 5 32261 6 32561 7 32563 8 62563 9 65563

I've corrected an error in the longest minimum path which now goes from 88259 <--> 99721. I've edited my original post to reflect this and make the presentation consistent with the style we've been using for word ladders.

Leren

by **Leren** » Thu Oct 03, 2013 10:54 pm

My results for connection ladders for 5 digit primes indicate that every prime is connected to every other prime via a minimum sized ladder of at most 10 steps (from the given prime).

The following table shows the number of primes with a given minimum ladder size.

Code: Select all: Ladder Size No of Primes 7 3 8 7650 9 708 10 2 ----- 8363

This shows that every 5 digit prime can be connected to every other 5 digit prime. This is not the case with word ladders - there are lots of words that can't be turned into other words by changing one letter.

So you can obviously produce a ladder that includes all 5 digit primes by changing one digit at each step. What's not obvious is whether you have to repeat a number in the ladder. So the question arises:

Code: Select all: What is the longest ladder of 5 digit primes that can be made by changing one digit at each step without repeating a number ?

At the moment I can't answer this question (my code is designed to find shortest paths, not longest paths). I'll give it some thought but in the meantime if anyone can answer this question please fee free to post the answer.

Leren

by **David P Bird** » Fri Oct 04, 2013 9:59 am

Leren, I have little idea about how your code works, but if you are looping through possible exchange digits it's possible to reduce the candidates to test using the following:

All prime numbers must be either 1 or 2 mod 3
So for example for a 1 mod 3 prime, any 1, 4, or 7 can't be replaced by 0, 3, 6, or 9.
This reduces 9 possible exchanges to 5 or 6
As the options are tested it should therefore be worthwhile to monitor the modulus of the current prime and loop through the candidates in a look-up table to avoid testing non-starters.
Of course for the final digit, the choice is even more restricted.

The only other thought of any merit that I've had is:

Using letters, this family of words provides a very versatile method of extending a ladder
Pat
Pet
Pit
Pot
Put
If any of the words is needed elsewhere it can easily be taken out with no ill effects, and there are also multiple opportunities for managing detours between any two of them.
For the prime ladders it may therefore be worth specifically looking for these and noting the most promising ones.

When checking for a repeated prime a sorted list of those already used may be the way to go. This could include a tag system showing if the prime is necessary or an optional family member.

David

by **Leren** » Fri Oct 04, 2013 12:13 pm

Here's my first attempt, a ladder sequence of 3624 5 digit primes - no doubt good bed time reading.

Hidden Text: Show

Leren

by **JPF** » Fri Oct 04, 2013 7:02 pm

Here is a list of 6500 five digit primes.

Some issues to resolve to get the full list.

JPF

by **Leren** » Fri Oct 04, 2013 10:18 pm

It appears that there are 5 five digit primes that are "connected" to only one other five digit prime (by a single digit difference). These are the primes in the first column
of the following table. The primes in the second column are the only ones to which they are "connected".

Code: Select all: 46769 96769 97039 37039 97919 27919 98519 98419 99721 99761

All of the primes in the second column appear in JPF's 6500 prime list and none of the primes in the first column appear in it.

I think this means that, unfortunately, the holy grail of a ladder list of all 8363 five digit primes is impossible - the best you can do would be something like:

46769 96769 .... [ ladder of 8356 primes ... ] .... 99721 99761 - a total ladder of 8360 primes. I have no idea if even this is possible.

Still, it would be nice to find a maximal ladder and demonstrate in some way that it is maximal. Another really cool objective would be to find a maximal cyclic ladder
ie where the last prime in the ladder is 1 digit different from the first prime - so you could start the list from any point along it.

Leren

by **JPF** » Sat Oct 05, 2013 10:28 am

Leren wrote:I think this means that, unfortunately, the holy grail of a ladder list of all 8363 five digit primes is impossible - the best you can do would be something like:
46769 96769 .... [ ladder of 8356 primes ... ] .... 99721 99761 - a total ladder of 8360 primes.
..................

That's a good point.

JPF

by **Leren** » Sat Oct 05, 2013 12:19 pm

I've found that JPF's 6500 prime ladder starts with 87491 and has 17491 at position 6409.

That would make a cyclic ladder of length 6409. There will certainly be other cyclic ladders in that list but it will take a while to check all possibilities to see whether one exceeds a length of 6409.

Leren

<Edit> Now had a chance to check for longer cyclic ladders. 69691 is in position 5 and 79691 is in position 6493 for a longest cyclic ladder length of 6489.

Leren

by **Smythe Dakota** » Sat Oct 05, 2013 1:06 pm

Leren wrote: .... [ a whole bunch of stuff ] ....

In response, JPF and David P Bird wrote: .... [ a lot of other stuff ] ....

I can't believe you guys actually took me up on this. Your next task, should you decide to accept it, is to do the same thing in hexadecimal. Of course, there are m-a-n-y more hexadecimal 5-digit primes than decimal 5-digit primes.

Bill Smythe

by **Leren** » Sun Oct 06, 2013 2:55 am

Here is a 5 digit prime ladder with 7021 numbers starting from the lowest 5 digit prime.

<Edit> Added new file with a 7536 prime number ladder from the same start prime.

Leren

by **JPF** » Sun Oct 06, 2013 5:02 pm

Waiting for 8000

edit:
here is a 8154 primes.
There is a cycle 23599 ->33599 with 8139 elements.

JPF

The New Sudoku Players' Forum

A Sobering Problem

Re: A Sobering Problem

Re: A Sobering Problem

Re: A Sobering Problem

Re: A Sobering Problem

Re: A Sobering Problem

Re: A Sobering Problem

Re: A Sobering Problem

Re: A Sobering Problem

Re: A Sobering Problem

Re: A Sobering Problem

Re: A Sobering Problem

Re: A Sobering Problem

Re: A Sobering Problem

Re: A Sobering Problem

Re: A Sobering Problem