|
|
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
|
Eric Weisstein's World of Mathematics, Binary.
|
|
FORMULA
|
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
|
if n = 0 then
1;
else
end if;
end proc:
# 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:
|
|
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.
(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)]
(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])
|
|
CROSSREFS
|
This is Guy Steele's sequence GS(2, 4) (see A135416).
|
|
KEYWORD
|
nonn,base,easy
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|