This site is supported by donations to The OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A091090 In binary representation: number of editing steps (delete, insert, or substitute) to transform n into n + 1. 13
 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 (list; graph; refs; listen; history; text; internal format)
 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] F. Ruskey, C. Deugau, The Combinatorics of Certain k-ary Meta-Fibonacci Sequences, JIS 12 (2009) 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 FORMULA 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 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 CROSSREFS Cf. A007088, A135517. This is Guy Steele's sequence GS(2, 4) (see A135416). Sequence in context: A178544 A161506 A066451 * A305079 A305052 A319841 Adjacent sequences:  A091087 A091088 A091089 * A091091 A091092 A091093 KEYWORD nonn,base,easy AUTHOR Reinhard Zumkeller, Dec 19 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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified October 15 16:06 EDT 2018. Contains 316236 sequences. (Running on oeis4.)