cp's OEIS Frontend

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

%I A353738 #10 May 21 2022 17:51:12
%S A353738 0,2,2,1,5,3,7,5,15,15,19,24,39,48,35,64,57,51,59,61,67,61,61
%N A353738 Length of longest n-digit optimal prime ladder (base 2).
%C A353738 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 A353738 A shortest such construct between two given primes is optimal.
%C A353738 Analogous to a word ladder (see Wikipedia link).
%C A353738 Here, n-digit primes do not allow leading 0 digits.
%C A353738 If all n-digit primes are disconnected, a(n) = 1; if there are no n-digit primes, a(n) = 0.
%H A353738 Wikipedia, <a href="https://en.wikipedia.org/wiki/Word_ladder">Word Ladder</a>
%H A353738 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 A353738 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.
%e A353738 There are no 1-digit primes in base 2, so a(1) = 0.
%e A353738 The 2-digit optimal prime ladder 10 - 11 is tied for the longest amongst 2-digit primes in binary, so a(2) = 2.
%e A353738 The 3-digit optimal prime ladder 101 - 111 is tied for the longest amongst 3-digit primes in binary, so a(3) = 2.
%e A353738 The only 4-digit primes in binary, 1011 and 1101, are disconnected, so a(3) = 1.
%e A353738 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.
%Y A353738 Cf. A000040, A004676, A104080, A014234, A145667, A353737.
%K A353738 nonn,base,more
%O A353738 1,2
%A A353738 _Michael S. Branicky_, May 09 2022
%E A353738 a(23) from _Michael S. Branicky_, May 21 2022