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

Author

Reinhard Zumkeller, Dec 19 2003

Keywords

• nonn
• base
• easy
• changed

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
• Dillan Agrawal, Selena Ge, Jate Greene, Tanya Khovanova, Dohun Kim, Rajarshi Mandal, Tanish Parida, Anirudh Pulugurtha, Gordon Redwine, Soham Samanta, and Albert Xu, Chip-Firing on Infinite k-ary Trees, arXiv:2501.06675 [math.CO], 2025. See p. 11.
• Michael Gilleland, Levenshtein Distance [broken link] [It has been suggested that this algorithm gives incorrect results sometimes. - _N. J. A. Sloane_]
• Ryota Inagaki, Tanya Khovanova, and Austin Luo, On Chip-Firing on Undirected Binary Trees, Ann. Comb. (2025). See p. 22.
• 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.

Crossrefs

Cf. A007088, A135517.

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

Programs

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

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

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

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