Can You Build The Longest Ladder?

Riddler Classic

From Michael Branicky comes puzzle of primes and their connections:

As you may know, a word ladder is a sequence of words in which exactly one letter changes from one word to the next. And an optimal word ladder is a word ladder that gets you from the initial word to the final word using as few other words as possible. For example, to go from DOG to CAT, an optimal word ladder has just four total words (including DOG and CAT): DOG, DOT, COT and CAT.

For this puzzle, Michael similarly defines optimal prime ladders. Every number in the ladder must be prime, with exactly one digit changing from one number to the next. For example, here is an optimal prime ladder that goes from 97 to 53 with just four total numbers: 97, 17, 13 and 53.

This is tied for the longest optimal prime ladder consisting of two-digit primes. What is the longest optimal prime ladder for three-digit primes? Four-digit primes? Five-digit primes?

Extra credit: What is the longest optimal prime ladder for six-digit primes?

Solution

I ran some code:

• First I determined all the primes within a range.
• I then created a pxp array of the primes.
• If the row and column were the same, the cell was set to 1 (Getting from a prime to itself is a ladder of 1).
• If the row and column differ by one digit, the cell was set to 2.
• From there I ran a loop to combine ladders p1<->p2 and p2<->p3 to determine the value of ladder p1<->p3.
• This was continued until no cell had a missing value.
• The distribution of all optimal prime ladders was determined. Here is that of Two-Digit.
• I was able to determine the first and last primes in the longest optimal ladders.

Answers

Three-Digit

</li>

The only longest optimal prime ladder is from 389 to 761 (or vice versa), and is of length 7.

Four-Digit

</li>

$1061^2 = 1125721$ prime pairs (loose count including reflexive pairs and reversed order pairs). However, note that the sum of the distribution above is only 125,693, or about 11% of the total. This is because there does not exist two four digit primes differing only by their thousands' digit.

For four digit prime ladders, all primes in the ladder will have the same thousands' digit.

The longest optimal prime ladders are of length 9:

• 6841 to 6983
• 7019 to 7433
• 7039 to 7433
• 7039 to 7963
• 9323 to 9547

Five-Digit & Six-Digit

My code was not efficient enough to determine five- or six-digit prime ladders in a reasonable amount of time.

However, similar to four-digit primes, I was able to determine that there does not exist two five digit primes differing only by their ten thousands' digit.

And there does not exist two six digit primes differing only by their hundred thousands' digit.

So the longest optimal four, five, and six digit prime ladders could be...undefined‽ ¯|( ͡° ͜ʖ ͡°)|¯

Rohan Lewis

2022.05.09

Code can be found here.