|
%I #70 Sep 29 2023 04:03:05
%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 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
%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
%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
|
