login
Minimal number of editing steps (delete, insert or substitute) to transform the binary representation of n into that of A007918(n), the least prime not less than n.
5

%I #3 Mar 30 2012 18:51:05

%S 1,1,0,0,1,0,1,0,2,1,1,0,1,0,3,3,1,0,1,0,2,1,1,0,2,1,2,2,1,0,1,0,2,1,

%T 2,2,1,0,3,3,1,0,1,0,2,1,1,0,2,1,2,2,1,0,2,2,2,1,1,0,1,0,5,4,2,1,1,0,

%U 2,1,1,0,1,0,2,1,2,1,1,0,2,1,1,0,2,2,3,3,1,0,4,4,4,4,5,5,1,0,2,2,1,0,1,0,2

%N Minimal number of editing steps (delete, insert or substitute) to transform the binary representation of n into that of A007918(n), the least prime not less than n.

%C Delete steps are not necessary;

%C a(n) = 0 iff n is prime: a(A000040(n))=0;

%C a(A171401(n)) = 1;

%C A171402 gives smallest numbers m such that a(m)=n: a(A171402(n))=n.

%H R. Zumkeller, <a href="/A171400/b171400.txt">Table of n, a(n) for n = 0..2500</a>

%H Michael Gilleland, <a href="http://www.merriampark.com/ld.htm">Levenshtein Distance</a>

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

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

%e n=14, A007918(14)=17: 14==1110->1100->1100->10001==17, 2 subst and 1 ins: a(14)=3;

%e n=15, A007918(15)=17: 15==1111->1011->1001->10001==17, 2 subst and 1 ins: a(15)=3;

%e n=16, A007918(16)=17: 16==10000->10001==17, 1 subst: a(16)=1, A171401(8)=16;

%e n=17, A007918(17)=17: no editing step: a(17)=0;

%e n=18, A007918(18)=19: 18==10010->10011==19, 1 subst: a(18)=1, A171401(9)=18.

%Y Cf. A007088, A007920.

%K base,nonn

%O 0,9

%A _Reinhard Zumkeller_, Dec 08 2009