login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,1

COMMENTS

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

LINKS

Robert Israel, Table of n, a(n) for n = 0..10000

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: A187831 A087786 A210468 * A023852 A048750 A326136

Adjacent sequences:  A080947 A080948 A080949 * A080951 A080952 A080953

KEYWORD

nonn,base,look

AUTHOR

Reinhard Zumkeller, Apr 02 2003

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 24 04:35 EST 2020. Contains 331183 sequences. (Running on oeis4.)