A353738 Length of longest n-digit optimal prime ladder (base 2).

0, 2, 2, 1, 5, 3, 7, 5, 15, 15, 19, 24, 39, 48, 35, 64, 57, 51, 59, 61, 67, 61, 61

Offset

1,2

Comments

A prime ladder (in base b) starts with a prime, ends with a prime, and each step produces a new prime by changing exactly one base-b digit.

A shortest such construct between two given primes is optimal.

Analogous to a word ladder (see Wikipedia link).

Here, n-digit primes do not allow leading 0 digits.

If all n-digit primes are disconnected, a(n) = 1; if there are no n-digit primes, a(n) = 0.

Links

Table of n, a(n) for n=1..23.

Wikipedia, Word Ladder

Zach Wissner-Gross, Can You Build The Longest Ladder?, Riddler Classic, May 06 2022.

Formula

a(n) is the number of vertices of a longest shortest path in the graph G = (V, E), where V = {n-digit base-2 primes} and E = {(v, w) | H_2(v, w) = 1}, where H_b is the Hamming distance in base b.

Example

There are no 1-digit primes in base 2, so a(1) = 0.
The 2-digit optimal prime ladder 10 - 11 is tied for the longest amongst 2-digit primes in binary, so a(2) = 2.
The 3-digit optimal prime ladder 101 - 111 is tied for the longest amongst 3-digit primes in binary, so a(3) = 2.
The only 4-digit primes in binary, 1011 and 1101, are disconnected, so a(3) = 1.
The 5-digit optimal prime ladder 10001 - 10011 - 10111 - 11111 - 11101 is tied for the longest amongst 5-digit primes in binary, so a(5) = 5.

Crossrefs

Cf. A000040, A004676, A104080, A014234, A145667, A353737.

Sequence in context: A367094 A324798 A226059 * A127742 A110438 A184051

Adjacent sequences: A353735 A353736 A353737 * A353739 A353740 A353741

Keyword

nonn,base,more

Author

Michael S. Branicky, May 09 2022

Extensions

a(23) from Michael S. Branicky, May 21 2022

Status

approved