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

Offset

0,1

Links

Table of n, a(n) for n=0..31.

Michael Gilleland, Levenshtein Distance

Wikipedia, Levenshtein Distance

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

Prog

(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

Crossrefs

Cf. A007918, A151799, A171400.

Sequence in context: A085814 A009524 A009794 * A104506 A088138 A186033

Adjacent sequences: A171399 A171400 A171401 * A171403 A171404 A171405

Keyword

nonn,base,more

Author

Reinhard Zumkeller, Dec 08 2009

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

Status

approved