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

Author

Michael S. Branicky, May 09 2022

Keywords

• nonn
• base
• more

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.

Examples

			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.
		

Links

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

Crossrefs

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

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.

Extensions

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