login
A353738
Length of longest n-digit optimal prime ladder (base 2).
1
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
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
KEYWORD
nonn,base,more
AUTHOR
Michael S. Branicky, May 09 2022
EXTENSIONS
a(23) from Michael S. Branicky, May 21 2022
STATUS
approved