

A353737


Length of longest ndigit optimal prime ladder (base 10).


1




OFFSET

1,1


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 baseb digit.
A shortest such construct between two given primes is optimal.
Analogous to a word ladder (see Wikipedia link).
Here, ndigit primes do not allow leading 0 digits.
If all ndigit primes are disconnected, a(n) = 1; if there are no ndigit primes, a(n) = 0.
a(7) >= 15.
It follows from Bertrand's postulate that there exist ndigit primes for all n >= 1, so a(n) is never 0.  Pontus von Brömssen, May 11 2022


LINKS



FORMULA

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


EXAMPLE

The 1digit optimal prime ladder 3  5 is tied for the longest amongst 1digit primes, so a(1) = 2.
The 2digit optimal prime ladder 97  17  13  53 is tied for the longest amongst 2digit primes, so a(2) = 4.
The 3digit optimal prime ladder 389  383  283  281  251  751  761 is tied for the longest amongst 3digit primes, so a(3) = 7.
The 4digit optimal prime ladder 4651  4951  4931  4933  4733  6733  6833  6883  6983 is tied for the longest amongst 4digit primes, so a(4) = 9.
The 5digit optimal prime ladder 88259  48259  45259  45959  41959  41969  91969  91961  99961  99761  99721 is tied for the longest amongst 5digit primes, so a(5) = 13.
The 6digit optimal prime ladder 440497  410497  410491  710491  710441  710443  717443  917443  917843  907843  905843  905833  995833 is tied for the longest amongst 6digit primes, so a(6) = 13.
The 7digit optimal prime ladder 3038459  3032459  3032453  3034453  3034457  3034657  3074657  3074557  4074557  4079557  4779557  4779547  7779547  7759547  7755547 is tied for the longest amongst 7digit primes, so a(7) = 15.  Michael S. Branicky, May 21 2022


CROSSREFS



KEYWORD

nonn,base,more


AUTHOR



EXTENSIONS



STATUS

approved



