login
Number of numbers that differ from n in binary representation by exactly one edit-operation: deletion, insertion, or substitution.
2

%I #15 Oct 24 2019 10:07:56

%S 2,3,6,5,7,8,8,7,9,10,11,10,10,11,10,9,11,12,13,12,13,14,13,12,12,13,

%T 14,13,12,13,12,11,13,14,15,14,15,16,15,14,15,16,17,16,15,16,15,14,14,

%U 15,16,15,16,17,16,15,14,15,16,15,14,15,14,13,15,16,17,16,17,18,17,16,17

%N Number of numbers that differ from n in binary representation by exactly one edit-operation: deletion, insertion, or substitution.

%C a(n) = #{i: LD-2(n,i)=1}, where LD-2 is the Levenshtein distance on binary strings.

%H Robert Israel, <a href="/A080950/b080950.txt">Table of n, a(n) for n = 0..10000</a>

%H Michael Gilleland, <a href="http://www.merriampark.com/ld.htm">Levenshtein Distance</a>. [It has been suggested that this algorithm gives incorrect results sometimes. - _N. J. A. Sloane_]

%F From _Robert Israel_, Aug 08 2019: (Start)

%F a(4*k) = a(2*k)+2 for k >= 2.

%F a(4*k+1) = a(2*k)+3 for k >= 2.

%F a(4*k+2) = a(2*k+1)+3.

%F a(4*k+3) = a(2*k+1)+2.

%F G.f. g(x) satisfies g(x) = (1+x)*g(x^2) + (x+2*x^2+x^4+x^8)/(1-x+x^2-x^3).

%F (End)

%e n=6: binary representation of numbers at Levenshtein distance 1 from 6='110': {10, 11, 100, 111, 1010, 1100, 1101, 1110}, so a(6)=8.

%e n=42: binary representation of numbers at Levenshtein distance 1 from 42='101010': {10010, 10100, 10101, 10110, 11010, 100010, 101000, 101011, 101110, 111010, 1001010, 1010010, 1010100, 1010101, 1010110, 1011010, 1101010}, therefore a(42)=17.

%p f:= proc(n) local R,i,m,a,b;

%p m:= ilog2(n);

%p R:= {n+2^(m+1),n+2^m};

%p for i from 0 to m-1 do

%p b:= n mod 2^i;

%p a:= (n-b)/2^i;

%p R:= R union {floor(a/2)*2^i+b, a*2^(i+1)+b,

%p (2*a+1)*2^i+b,n + (1-2*(a mod 2))*2^i}

%p od;

%p nops(R)

%p end proc:

%p f(0):= 2: f(1):= 3: f(2):= 6:

%p map(f, [$0..100]); # _Robert Israel_, Aug 08 2019

%t a[n_] := a[n] = If[n < 6, {2, 3, 6, 5, 7, 8}[[n+1]], Switch[Mod[n, 4], 0, a[n/2]+2, 1, a[(n-1)/2]+3, 2, a[(n-2)/2+1]+3, 3, a[(n-3)/2+1]+2]];

%t a /@ Range[0, 100]

%t (* or: *)

%t m = 100; g[_] = 1;

%t Do[g[x_] = (1 + x) g[x^2] + (x + 2 x^2 + x^4 + x^8)/(1 - x + x^2 - x^3) + O[x]^m // Normal, {m}];

%t 1 + CoefficientList[g[x], x] (* _Jean-François Alcover_, Oct 24 2019, after _Robert Israel_ *)

%Y Cf. A080910.

%K nonn,base,look

%O 0,1

%A _Reinhard Zumkeller_, Apr 02 2003