A091090 - OEIS

%I #79 Sep 20 2024 06:05:04

%S 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,

%T 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,

%U 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

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

%C Apparently, one less than the number of cyclotomic factors of the polynomial x^n - 1. - _Ralf Stephan_, Aug 27 2013

%C 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

%H Reinhard Zumkeller, <a href="/A091090/b091090.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> [broken link] [It has been suggested that this algorithm gives incorrect results sometimes. - _N. J. A. Sloane_]

%H Frank Ruskey and Chris Deugau, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL12/Ruskey/ruskey6.html">The Combinatorics of Certain k-ary Meta-Fibonacci Sequences</a>, JIS 12 (2009), Article 09.4.3.

%H Vladimir Shevelev, <a href="https://arxiv.org/abs/1708.08096">On a Luschny question</a>, arXiv:1708.08096 [math.NT], 2017.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Binary.html">Binary</a>.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/BinaryCarrySequence.html">Binary Carry Sequence</a>.

%H WikiBooks: Algorithm Implementation, <a href="http://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance">Levenshtein distance</a>.

%H <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>.

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

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

%F a(n) = A152487(n + 1, n). - _Reinhard Zumkeller_, Dec 06 2008

%F a(A004275(n)) = 1. - _Reinhard Zumkeller_, Mar 13 2011

%F From _Vladeta Jovovic_, Aug 25 2004, fixed by _Reinhard Zumkeller_, Jun 09 2015: (Start)

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

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

%F Let T(x) be the g.f., then T(x) - x*T(x^2) = x/(1 - x). - _Joerg Arndt_, May 11 2010

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

%F a(n) = A000120(n) + A070939(n) - A000120(n+1) - A070939(n+1) + 2. - _Chai Wah Wu_, Sep 18 2024

%p A091090 := proc(n)

%p     if n = 0 then

%p         1;

%p     else

%p         A007814(n+1)+1-A036987(n) ;

%p     end if;

%p end proc:

%p seq(A091090(n),n=0..100); # _R. J. Mathar_, Sep 07 2016

%p # Alternatively, explaining the connection with A135517:

%p a := proc(n) local count, k; count := 1; k := n;

%p while k <> 1 and k mod 2 <> 0 do count := count + 1; k := iquo(k, 2) od:

%p count end: seq(a(n), n=0..101); # _Peter Luschny_, Aug 10 2017

%t 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 *)

%o (Haskell)

%o a091090 n = a091090_list !! n

%o a091090_list = 1 : f [1,1] where f (x:y:xs) = y : f (x:xs ++ [x,x+y])

%o -- Same list generator function as for a036987_list, cf. A036987.

%o -- _Reinhard Zumkeller_, Mar 13 2011

%o (Haskell)

%o a091090' n = levenshtein (show $ a007088 (n + 1)) (show $ a007088 n) where

%o   levenshtein :: (Eq t) => [t] -> [t] -> Int

%o   levenshtein us vs = last $ foldl transform [0..length us] vs where

%o     transform xs@(x:xs') c = scanl compute (x+1) (zip3 us xs xs') where

%o       compute z (c', x, y) = minimum [y+1, z+1, x + fromEnum (c' /= c)]

%o -- _Reinhard Zumkeller_, Jun 09 2015

%o (Haskell) -- following Vladeta Jovovic's formula

%o import Data.List (transpose)

%o a091090'' n = vjs !! n where

%o    vjs = 1 : 1 : concat (transpose [[1, 1 ..], map (+ 1) $ tail vjs])

%o -- _Reinhard Zumkeller_, Jun 09 2015

%o (PARI) a(n)=my(m=valuation(n+1,2)); if(n>>m, m+1, max(m, 1)) \\ _Charles R Greathouse IV_, Aug 15 2017

%o (Python)

%o def A091090(n): return (~(n+1)&n).bit_length()+bool(n&(n+1)) if n else 1 # _Chai Wah Wu_, Sep 18 2024

%Y Cf. A007088, A135517.

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

%K nonn,base,easy

%O 0,4

%A _Reinhard Zumkeller_, Dec 19 2003