A091090 In binary representation: number of editing steps (delete, insert, or substitute) to transform n into n + 1.

1, 1, 1, 2, 1, 2, 1, 3, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 6, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 6, 1, 2, 1, 3, 1, 2

Offset

0,4

Comments

Apparently, one less than the number of cyclotomic factors of the polynomial x^n - 1. - Ralf Stephan, Aug 27 2013

Let the binary expansion of n >= 1 end with m >= 0 1's. Then a(n) = m if n = 2^m-1 and a(n) = m+1 if n > 2^m-1. - Vladimir Shevelev, Aug 14 2017

Links

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000

Michael Gilleland, Levenshtein Distance [broken link] [It has been suggested that this algorithm gives incorrect results sometimes. - N. J. A. Sloane]

Frank Ruskey and Chris Deugau, The Combinatorics of Certain k-ary Meta-Fibonacci Sequences, JIS 12 (2009), Article 09.4.3.

Vladimir Shevelev, On a Luschny question, arXiv:1708.08096 [math.NT], 2017.

Eric Weisstein's World of Mathematics, Binary.

Eric Weisstein's World of Mathematics, Binary Carry Sequence.

WikiBooks: Algorithm Implementation, Levenshtein distance.

Index entries for sequences related to binary expansion of n.

Formula

a(n) = LevenshteinDistance(A007088(n), A007088(n + 1)).

a(n) = A007814(n + 1) + 1 - A036987(n).

a(n) = A152487(n + 1, n). - Reinhard Zumkeller, Dec 06 2008

a(A004275(n)) = 1. - Reinhard Zumkeller, Mar 13 2011

From Vladeta Jovovic, Aug 25 2004, fixed by Reinhard Zumkeller, Jun 09 2015: (Start)

a(2*n) = 1, a(2*n + 1) = a(n) + 1 for n > 0.

G.f.: 1 + Sum_{k > 0} x^(2^k - 1)/(1 - x^(2^(k - 1))). (End)

Let T(x) be the g.f., then T(x) - x*T(x^2) = x/(1 - x). - Joerg Arndt, May 11 2010

Asymptotic mean: Limit_{m->oo} (1/m) * Sum_{k=1..m} a(k) = 2. - Amiram Eldar, Sep 29 2023

a(n) = A000120(n) + A070939(n) - A000120(n+1) - A070939(n+1) + 2. - Chai Wah Wu, Sep 18 2024

Maple

A091090 := proc(n)
    if n = 0 then
        1;
    else
        A007814(n+1)+1-A036987(n) ;
    end if;
end proc:
seq(A091090(n), n=0..100); # R. J. Mathar, Sep 07 2016
# Alternatively, explaining the connection with A135517:
a := proc(n) local count, k; count := 1; k := n;
while k <> 1 and k mod 2 <> 0 do count := count + 1; k := iquo(k, 2) od:
count end: seq(a(n), n=0..101); # Peter Luschny, Aug 10 2017

Mathematica

a[n_] := a[n] = Which[n==0, 1, n==1, 1, EvenQ[n], 1, True, a[(n-1)/2] + 1]; Array[a, 102, 0] (* Jean-François Alcover, Aug 12 2017 *)

Prog

(Haskell)
a091090 n = a091090_list !! n
a091090_list = 1 : f [1, 1] where f (x:y:xs) = y : f (x:xs ++ [x, x+y])
-- Same list generator function as for a036987_list, cf. A036987.
-- Reinhard Zumkeller, Mar 13 2011
(Haskell)
a091090' n = levenshtein (show $ a007088 (n + 1)) (show $ a007088 n) where
  levenshtein :: (Eq t) => [t] -> [t] -> Int
  levenshtein us vs = last $ foldl transform [0..length us] vs where
    transform xs@(x:xs') c = scanl compute (x+1) (zip3 us xs xs') where
      compute z (c', x, y) = minimum [y+1, z+1, x + fromEnum (c' /= c)]
-- Reinhard Zumkeller, Jun 09 2015
(Haskell) -- following Vladeta Jovovic's formula
import Data.List (transpose)
a091090'' n = vjs !! n where
   vjs = 1 : 1 : concat (transpose [[1, 1 ..], map (+ 1) $ tail vjs])
-- Reinhard Zumkeller, Jun 09 2015
(PARI) a(n)=my(m=valuation(n+1, 2)); if(n>>m, m+1, max(m, 1)) \\ Charles R Greathouse IV, Aug 15 2017
(Python)
def A091090(n): return (~(n+1)&n).bit_length()+bool(n&(n+1)) if n else 1 # Chai Wah Wu, Sep 18 2024

Crossrefs

Cf. A007088, A135517.

This is Guy Steele's sequence GS(2, 4) (see A135416).

Sequence in context: A066451 A328048 A363522 * A305052 A305079 A319841

Adjacent sequences: A091087 A091088 A091089 * A091091 A091092 A091093

Keyword

nonn,base,easy

Author

Reinhard Zumkeller, Dec 19 2003

Status

approved