%I #18 May 21 2022 17:50:36
%S 2,4,7,9,11,13,15
%N Length of longest n-digit optimal prime ladder (base 10).
%C 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.
%C A shortest such construct between two given primes is optimal.
%C Analogous to a word ladder (see Wikipedia link).
%C Here, n-digit primes do not allow leading 0 digits.
%C If all n-digit primes are disconnected, a(n) = 1; if there are no n-digit primes, a(n) = 0.
%C a(7) >= 15.
%C It follows from Bertrand's postulate that there exist n-digit primes for all n >= 1, so a(n) is never 0. - _Pontus von Brömssen_, May 11 2022
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Word_ladder">Word Ladder</a>
%H Zach Wissner-Gross, <a href="https://fivethirtyeight.com/features/can-you-build-the-longest-ladder/">Can You Build The Longest Ladder?</a>, Riddler Classic, May 06 2022.
%F a(n) is the number of vertices of a longest shortest path in the graph G = (V, E), where V = {n-digit base-10 primes} and E = {(v, w) | H_10(v, w) = 1}, where H_b is the Hamming distance in base b.
%e The 1-digit optimal prime ladder 3 - 5 is tied for the longest amongst 1-digit primes, so a(1) = 2.
%e The 2-digit optimal prime ladder 97 - 17 - 13 - 53 is tied for the longest amongst 2-digit primes, so a(2) = 4.
%e The 3-digit optimal prime ladder 389 - 383 - 283 - 281 - 251 - 751 - 761 is tied for the longest amongst 3-digit primes, so a(3) = 7.
%e The 4-digit optimal prime ladder 4651 - 4951 - 4931 - 4933 - 4733 - 6733 - 6833 - 6883 - 6983 is tied for the longest amongst 4-digit primes, so a(4) = 9.
%e The 5-digit optimal prime ladder 88259 - 48259 - 45259 - 45959 - 41959 - 41969 - 91969 - 91961 - 99961 - 99761 - 99721 is tied for the longest amongst 5-digit primes, so a(5) = 13.
%e The 6-digit optimal prime ladder 440497 - 410497 - 410491 - 710491 - 710441 - 710443 - 717443 - 917443 - 917843 - 907843 - 905843 - 905833 - 995833 is tied for the longest amongst 6-digit primes, so a(6) = 13.
%e The 7-digit optimal prime ladder 3038459 - 3032459 - 3032453 - 3034453 - 3034457 - 3034657 - 3074657 - 3074557 - 4074557 - 4079557 - 4779557 - 4779547 - 7779547 - 7759547 - 7755547 is tied for the longest amongst 7-digit primes, so a(7) = 15. - _Michael S. Branicky_, May 21 2022
%Y Cf. A000040, A050249, A125002, A158576, A253269, A345985.
%K nonn,base,more
%O 1,1
%A _Michael S. Branicky_, May 09 2022
%E a(7) from _Michael S. Branicky_, May 21 2022