|
| |
|
|
A005811
|
|
Number of runs in binary expansion of n (n>0); number of 1's in Gray code for n.
(Formerly M0110)
|
|
22
| |
|
|
0, 1, 2, 1, 2, 3, 2, 1, 2, 3, 4, 3, 2, 3, 2, 1, 2, 3, 4, 3, 4, 5, 4, 3, 2, 3, 4, 3, 2, 3, 2, 1, 2, 3, 4, 3, 4, 5, 4, 3, 4, 5, 6, 5, 4, 5, 4, 3, 2, 3, 4, 3, 4, 5, 4, 3, 2, 3, 4, 3, 2, 3, 2, 1, 2, 3, 4, 3, 4, 5, 4, 3, 4, 5, 6, 5, 4, 5, 4, 3, 4, 5, 6, 5, 6, 7, 6, 5, 4, 5, 6, 5, 4, 5
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 0,3
|
|
|
COMMENTS
| Starting with a(1)=0 mirror all initial 2^k segments and increase by one.
a(n) gives the net rotation (measured in right angles) after taking n steps along a dragon curve. - Christopher Hendrie (hendrie(AT)acm.org), Sep 11 2002
This sequence generates A082410: (0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1...) and A014577; identical to the latter except starting 1, 1, 0...; by writing a "1" if a(n+1) > a(n); if not, write "0". E.g. A014577(2) = 0, since a(3) < a(2), or 1 < 2. - Gary W. Adamson (qntmpkt(AT)yahoo.com), Sep 20 2003
Starting with 1 = partial sums of A034947: (1, 1, -1, 1, 1, -1, -1, 1, 1, 1,...). - Gary W. Adamson (qntmpkt(AT)yahoo.com), Jul 23 2008
The composer Per Norgard's name is also written in the OEIS as Per Noergaard.
|
|
|
REFERENCES
| J.-P. Allouche and J. Shallit, The ring of k-regular sequences, II, Theoret. Computer Sci., 307 (2003), 3-29.
Flajolet and Ramshaw, A note on Gray code..., SIAM J. Comput. 9 (1980), 142-158.
Jeffrey Shallit, The mathematics of Per Noergaard's rhythmic infinity system, Fib. Q., 43 (2005), 262-268.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
|
LINKS
| T. D. Noe, Table of n, a(n) for n = 0..10000
Joerg Arndt, Fxtbook
J.-P. Allouche, J. Shallit, The Ring of k-regular Sequences, II
P. Flajolet et al., Mellin Transforms And Asymptotics: Digital Sums, Theoret. Computer Sci. 23 (1994), 291-314.
R. Stephan, Some divide-and-conquer sequences ...
R. Stephan, Table of generating functions
Index entries for "core" sequences
|
|
|
FORMULA
| a(2^k + i) = a(2^k - i + 1) + 1 for k >= 0 and 0 < i <= 2^k. - Reinhard Zumkeller (reinhard.zumkeller(AT)gmail.com), Aug 14 2001
a(2n+1) = 2a(n)-a(2n)+1, a(4n) = a(2n), a(4n+2) = 1+a(2n+1).
a(j+1) = a(j) + (-1)^A014707[j] - Christopher Hendrie (hendrie(AT)acm.org), Sep 11 2002
G.f.: 1/(1-x) * sum(k>=0, x^2^k/(1+x^2^(k+1))). - Ralf Stephan, May 2 2003
Delete the 0, make subsets of 2^n terms; and reverse the terms in each subset to generate A088696. - Gary W. Adamson (qntmpkt(AT)yahoo.com), Oct 19 2003
a(0)=0, a(2n) = a(n) + [n odd], a(2n+1) = a(n) + [n even]. - Ralf Stephan (ralf(AT)ark.in-berlin.de), Oct 20 2003
a(n) = sum(k=1, n, (-1)^((k/2^A007814(k)-1)/2)) = sum(k=1, n, (-1)^A025480(k-1)). - Ralf Stephan (ralf(AT)ark.in-berlin.de), Oct 29 2003
|
|
|
MAPLE
| A005811 := proc(n) local i, b, ans; ans := 1; b := convert(n, base, 2); for i from 2 to nops(b) do if b[ i-1 ]<>b[ i ] then ans := ans+1 fi od; RETURN(ans); end; [ seq(A005811(i), i=1..50) ];
|
|
|
MATHEMATICA
| Table[ Length[ Length/@Split[ IntegerDigits[ n, 2 ] ] ], {n, 1, 255} ]
|
|
|
PROG
| (PARI) a(n)=sum(k=1, n, (-1)^((k/2^valuation(k, 2)-1)/2))
(Haskell)
a005811 n = a005811_list !! n
a005811_list = 0 : f [1] where
f (x:xs) = x : f (xs ++ [x + x `mod` 2, x + 1 - x `mod` 2])
-- Reinhard Zumkeller, Mar 07 2011
|
|
|
CROSSREFS
| Cf. A056539, A014707, A014577, A082410.
A000975 gives records. - Oliver Kosut (vern(AT)mit.edu), May 06 2002
a(n) = A037834(n)+1.
a(n) = A069010(n) + A033264(n) (from Ralf Stephan)
Cf. A034947.
Sequence in context: A088696 A004738 A043554 * A008342 A175328 A198325
Adjacent sequences: A005808 A005809 A005810 * A005812 A005813 A005814
|
|
|
KEYWORD
| easy,nonn,core,nice
|
|
|
AUTHOR
| N. J. A. Sloane (njas(AT)research.att.com), Jeffrey Shallit, Simon Plouffe
|
|
|
EXTENSIONS
| Additional description from Wouter Meeussen (wouter.meeussen(AT)pandora.be)
|
| |
|
|
