A353737 Length of longest n-digit optimal prime ladder (base 10).

2, 4, 7, 9, 11, 13, 15

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.

a(7) >= 15.

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

Examples

			The 1-digit optimal prime ladder 3 - 5 is tied for the longest amongst 1-digit primes, so a(1) = 2.
The 2-digit optimal prime ladder 97 - 17 - 13 - 53 is tied for the longest amongst 2-digit primes, so a(2) = 4.
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.
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.
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.
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.
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
		

Links

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

Crossrefs

Cf. A000040, A050249, A125002, A158576, A253269, A345985.

Formula

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.

Extensions

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