A171402 Smallest number m such that exactly n editing steps (insert or substitute) are necessary to transform the binary representation of m into the least prime not less than m.

2, 0, 8, 14, 63, 62, 252, 254, 766, 2040, 4095, 4094, 12286, 32750, 32764, 65534, 262141, 262140, 1048574, 2097150, 7340030, 8388602, 25165820, 33554428, 67108860, 134217696, 268435420, 268435452, 1073741790, 1073741820, 3221225470, 8589934590, 25769803760

Offset: 0

Author

Reinhard Zumkeller, Dec 08 2009

Keywords

• nonn
• base

Links

• Michael Gilleland, Levenshtein Distance
• Wikipedia, Levenshtein Distance

Crossrefs

Cf. A007918, A151799, A152487, A171400.

Programs

Python

from Levenshtein import distance  # after pip install python-Levenshtein
from sympy import nextprime
def a(n):
    m = 0
    while True:
        b = bin(m)[2:]
        if distance(b, bin(nextprime(m-1))[2:]) == n:
            return m
        m += 1
print([a(n) for n in range(1, 16)]) # Michael S. Branicky, Feb 05 2022

Formula

A171400(a(n)) = n.

BinaryLevenshteinDistance(a(n), A007918(a(n))) = n.

For n > 1, A007918(a(n)) must have >= n+1 digits and empirically a(n) >= A151799(A007918(2^(n+1))) + 1 - Michael S. Branicky, Feb 05 2022

Extensions

a(10)-a(26) from Michael S. Branicky, Feb 05 2022

a(27)-a(29) from Michael S. Branicky, Feb 06 2022

a(30)-a(31) from Michael S. Branicky, Feb 19 2022

a(32) from Jinyuan Wang, May 01 2025