The OEIS mourns the passing of Jim Simons and is grateful to the Simons Foundation for its support of research in many branches of science, including the OEIS.
login
The OEIS is supported by the many generous donors 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
Michael Gilleland, Levenshtein Distance [broken link] [It has been suggested that this algorithm gives incorrect results sometimes. - N. J. A. Sloane]
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.
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
Asymptotic mean: Limit_{m->oo} (1/m) * Sum_{k=1..m} a(k) = 2. - Amiram Eldar, Sep 29 2023
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
This is Guy Steele's sequence GS(2, 4) (see A135416).
Sequence in context: A066451 A328048 A363522 * A305052 A305079 A319841
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 | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 13 09:03 EDT 2024. Contains 373383 sequences. (Running on oeis4.)