A171402 - OEIS

%I #32 Feb 19 2022 11:17:04

%S 2,0,8,14,63,62,252,254,766,2040,4095,4094,12286,32750,32764,65534,

%T 262141,262140,1048574,2097150,7340030,8388602,25165820,33554428,

%U 67108860,134217696,268435420,268435452,1073741790,1073741820,3221225470,8589934590

%N 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.

%H Michael Gilleland, <a href="https://people.cs.pitt.edu/~kirk/cs1501/Pruhs/Spring2006/assignments/editdistance/Levenshtein%20Distance.htm">Levenshtein Distance</a>

%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Levenshtein_distance">Levenshtein Distance</a>

%F A171400(a(n)) = n.

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

%F 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

%o (Python)

%o from Levenshtein import distance  # after pip install python-Levenshtein

%o from sympy import nextprime

%o def a(n):

%o     m = 0

%o     while True:

%o         b = bin(m)[2:]

%o         if distance(b, bin(nextprime(m-1))[2:]) == n:

%o             return m

%o         m += 1

%o print([a(n) for n in range(1, 16)]) # _Michael S. Branicky_, Feb 05 2022

%Y Cf. A007918, A151799, A171400.

%K nonn,base,more

%O 0,1

%A _Reinhard Zumkeller_, Dec 08 2009

%E a(10)-a(26) from _Michael S. Branicky_, Feb 05 2022

%E a(27)-a(29) from _Michael S. Branicky_, Feb 06 2022

%E a(30)-a(31) from _Michael S. Branicky_, Feb 19 2022