login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

A080950
Number of numbers that differ from n in binary representation by exactly one edit-operation: deletion, insertion, or substitution.
2
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, 14, 13, 12, 13, 12, 11, 13, 14, 15, 14, 15, 16, 15, 14, 15, 16, 17, 16, 15, 16, 15, 14, 14, 15, 16, 15, 16, 17, 16, 15, 14, 15, 16, 15, 14, 15, 14, 13, 15, 16, 17, 16, 17, 18, 17, 16, 17
OFFSET
0,1
COMMENTS
a(n) = #{i: LD-2(n,i)=1}, where LD-2 is the Levenshtein distance on binary strings.
LINKS
Michael Gilleland, Levenshtein Distance. [It has been suggested that this algorithm gives incorrect results sometimes. - N. J. A. Sloane]
FORMULA
From Robert Israel, Aug 08 2019: (Start)
a(4*k) = a(2*k)+2 for k >= 2.
a(4*k+1) = a(2*k)+3 for k >= 2.
a(4*k+2) = a(2*k+1)+3.
a(4*k+3) = a(2*k+1)+2.
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).
(End)
EXAMPLE
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.
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.
MAPLE
f:= proc(n) local R, i, m, a, b;
m:= ilog2(n);
R:= {n+2^(m+1), n+2^m};
for i from 0 to m-1 do
b:= n mod 2^i;
a:= (n-b)/2^i;
R:= R union {floor(a/2)*2^i+b, a*2^(i+1)+b,
(2*a+1)*2^i+b, n + (1-2*(a mod 2))*2^i}
od;
nops(R)
end proc:
f(0):= 2: f(1):= 3: f(2):= 6:
map(f, [$0..100]); # Robert Israel, Aug 08 2019
MATHEMATICA
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]];
a /@ Range[0, 100]
(* or: *)
m = 100; g[_] = 1;
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}];
1 + CoefficientList[g[x], x] (* Jean-François Alcover, Oct 24 2019, after Robert Israel *)
CROSSREFS
Cf. A080910.
Sequence in context: A087786 A379776 A210468 * A023852 A354629 A048750
KEYWORD
nonn,base,look
AUTHOR
Reinhard Zumkeller, Apr 02 2003
STATUS
approved