login
This site is supported by donations to The OEIS Foundation.

 

Logo


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

Index entries for sequences related to binary expansion of n

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 * A290090 A066075 A072347

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.

License Agreements, Terms of Use, Privacy Policy .

Last modified February 21 04:43 EST 2018. Contains 299389 sequences. (Running on oeis4.)