cp's OEIS Frontend

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

%I A091090 #87 Aug 22 2025 13:31:53
%S A091090 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 A091090 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 A091090 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 A091090 In binary representation: number of editing steps (delete, insert, or substitute) to transform n into n + 1.
%C A091090 Apparently, one less than the number of cyclotomic factors of the polynomial x^n - 1. - _Ralf Stephan_, Aug 27 2013
%C A091090 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 A091090 Reinhard Zumkeller, <a href="/A091090/b091090.txt">Table of n, a(n) for n = 0..10000</a>
%H A091090 Dillan Agrawal, Selena Ge, Jate Greene, Tanya Khovanova, Dohun Kim, Rajarshi Mandal, Tanish Parida, Anirudh Pulugurtha, Gordon Redwine, Soham Samanta, and Albert Xu, <a href="https://arxiv.org/abs/2501.06675">Chip-Firing on Infinite k-ary Trees</a>, arXiv:2501.06675 [math.CO], 2025. See p. 11.
%H A091090 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 A091090 Ryota Inagaki, Tanya Khovanova, and Austin Luo, <a href="https://doi.org/10.1007/s00026-025-00779-6">On Chip-Firing on Undirected Binary Trees</a>, Ann. Comb. (2025). See p. 22.
%H A091090 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 A091090 Vladimir Shevelev, <a href="https://arxiv.org/abs/1708.08096">On a Luschny question</a>, arXiv:1708.08096 [math.NT], 2017.
%H A091090 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Binary.html">Binary</a>.
%H A091090 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/BinaryCarrySequence.html">Binary Carry Sequence</a>.
%H A091090 WikiBooks: Algorithm Implementation, <a href="http://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance">Levenshtein distance</a>.
%H A091090 <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>.
%F A091090 a(n) = LevenshteinDistance(A007088(n), A007088(n + 1)).
%F A091090 a(n) = A007814(n + 1) + 1 - A036987(n).
%F A091090 a(n) = A152487(n + 1, n). - _Reinhard Zumkeller_, Dec 06 2008
%F A091090 a(A004275(n)) = 1. - _Reinhard Zumkeller_, Mar 13 2011
%F A091090 From _Vladeta Jovovic_, Aug 25 2004, fixed by _Reinhard Zumkeller_, Jun 09 2015: (Start)
%F A091090 a(2*n) = 1, a(2*n + 1) = a(n) + 1 for n > 0.
%F A091090 G.f.: 1 + Sum_{k > 0} x^(2^k - 1)/(1 - x^(2^(k - 1))). (End)
%F A091090 Let T(x) be the g.f., then T(x) - x*T(x^2) = x/(1 - x). - _Joerg Arndt_, May 11 2010
%F A091090 Asymptotic mean: Limit_{m->oo} (1/m) * Sum_{k=1..m} a(k) = 2. - _Amiram Eldar_, Sep 29 2023
%F A091090 a(n) = A000120(n) + A070939(n) - A000120(n+1) - A070939(n+1) + 2. - _Chai Wah Wu_, Sep 18 2024
%p A091090 A091090 := proc(n)
%p A091090     if n = 0 then
%p A091090         1;
%p A091090     else
%p A091090         A007814(n+1)+1-A036987(n) ;
%p A091090     end if;
%p A091090 end proc:
%p A091090 seq(A091090(n),n=0..100); # _R. J. Mathar_, Sep 07 2016
%p A091090 # Alternatively, explaining the connection with A135517:
%p A091090 a := proc(n) local count, k; count := 1; k := n;
%p A091090 while k <> 1 and k mod 2 <> 0 do count := count + 1; k := iquo(k, 2) od:
%p A091090 count end: seq(a(n), n=0..101); # _Peter Luschny_, Aug 10 2017
%t A091090 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 A091090 (Haskell)
%o A091090 a091090 n = a091090_list !! n
%o A091090 a091090_list = 1 : f [1,1] where f (x:y:xs) = y : f (x:xs ++ [x,x+y])
%o A091090 -- Same list generator function as for a036987_list, cf. A036987.
%o A091090 -- _Reinhard Zumkeller_, Mar 13 2011
%o A091090 (Haskell)
%o A091090 a091090' n = levenshtein (show $ a007088 (n + 1)) (show $ a007088 n) where
%o A091090   levenshtein :: (Eq t) => [t] -> [t] -> Int
%o A091090   levenshtein us vs = last $ foldl transform [0..length us] vs where
%o A091090     transform xs@(x:xs') c = scanl compute (x+1) (zip3 us xs xs') where
%o A091090       compute z (c', x, y) = minimum [y+1, z+1, x + fromEnum (c' /= c)]
%o A091090 -- _Reinhard Zumkeller_, Jun 09 2015
%o A091090 (Haskell) -- following Vladeta Jovovic's formula
%o A091090 import Data.List (transpose)
%o A091090 a091090'' n = vjs !! n where
%o A091090    vjs = 1 : 1 : concat (transpose [[1, 1 ..], map (+ 1) $ tail vjs])
%o A091090 -- _Reinhard Zumkeller_, Jun 09 2015
%o A091090 (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 A091090 (Python)
%o A091090 def A091090(n): return (~(n+1)&n).bit_length()+bool(n&(n+1)) if n else 1 # _Chai Wah Wu_, Sep 18 2024
%Y A091090 Cf. A007088, A135517.
%Y A091090 This is Guy Steele's sequence GS(2, 4) (see A135416).
%K A091090 nonn,base,easy,changed
%O A091090 0,4
%A A091090 _Reinhard Zumkeller_, Dec 19 2003