cp's OEIS Frontend

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.

%I A171402 #36 May 01 2025 08:13:42
%S A171402 2,0,8,14,63,62,252,254,766,2040,4095,4094,12286,32750,32764,65534,
%T A171402 262141,262140,1048574,2097150,7340030,8388602,25165820,33554428,
%U A171402 67108860,134217696,268435420,268435452,1073741790,1073741820,3221225470,8589934590,25769803760
%N 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.
%H A171402 Michael Gilleland, <a href="https://people.cs.pitt.edu/~kirk/cs1501/Pruhs/Spring2006/assignments/editdistance/Levenshtein%20Distance.htm">Levenshtein Distance</a>
%H A171402 Wikipedia, <a href="http://en.wikipedia.org/wiki/Levenshtein_distance">Levenshtein Distance</a>
%F A171402 A171400(a(n)) = n.
%F A171402 BinaryLevenshteinDistance(a(n), A007918(a(n))) = n.
%F A171402 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 A171402 (Python)
%o A171402 from Levenshtein import distance  # after pip install python-Levenshtein
%o A171402 from sympy import nextprime
%o A171402 def a(n):
%o A171402     m = 0
%o A171402     while True:
%o A171402         b = bin(m)[2:]
%o A171402         if distance(b, bin(nextprime(m-1))[2:]) == n:
%o A171402             return m
%o A171402         m += 1
%o A171402 print([a(n) for n in range(1, 16)]) # _Michael S. Branicky_, Feb 05 2022
%Y A171402 Cf. A007918, A151799, A152487, A171400.
%K A171402 nonn,base
%O A171402 0,1
%A A171402 _Reinhard Zumkeller_, Dec 08 2009
%E A171402 a(10)-a(26) from _Michael S. Branicky_, Feb 05 2022
%E A171402 a(27)-a(29) from _Michael S. Branicky_, Feb 06 2022
%E A171402 a(30)-a(31) from _Michael S. Branicky_, Feb 19 2022
%E A171402 a(32) from _Jinyuan Wang_, May 01 2025