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!)
A005811 Number of runs in binary expansion of n (n>0); number of 1's in Gray code for n.
(Formerly M0110)
212

%I M0110 #154 Mar 10 2023 09:07:41

%S 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,

%T 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,

%U 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

%N Number of runs in binary expansion of n (n>0); number of 1's in Gray code for n.

%C Starting with a(1) = 0 mirror all initial 2^k segments and increase by one.

%C 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

%C 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_, Sep 20 2003

%C Starting with 1 = partial sums of A034947: (1, 1, -1, 1, 1, -1, -1, 1, 1, 1, ...). - _Gary W. Adamson_, Jul 23 2008

%C The composer Per Nørgård's name is also written in the OEIS as Per Noergaard.

%C Can be used as a binomial transform operator: Let a(n) = the n-th term in any S(n); then extract 2^k strings, adding the terms. This results in the binomial transform of S(n). Say S(n) = 1, 3, 5, ...; then we obtain the strings: (1), (3, 1), (3, 5, 3, 1), (3, 5, 7, 5, 3, 5, 3, 1), ...; = the binomial transform of (1, 3, 5, ...) = (1, 4, 12, 32, 80, ...). Example: the 8-bit string has a sum of 32 with a distribution of (1, 3, 3, 1) or one 1, three 3's, three 5's, and one 7; as expected. - _Gary W. Adamson_, Jun 21 2012

%C Considers all positive odd numbers as nodes of a graph. Two nodes are connected if and only if the sum of the two corresponding odd numbers is a power of 2. Then a(n) is the distance between 2n + 1 and 1. - _Jianing Song_, Apr 20 2019

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H T. D. Noe, <a href="/A005811/b005811.txt">Table of n, a(n) for n = 0..10000</a>

%H Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Matters Computational (The Fxtbook)</a>

%H J.-P. Allouche, G.-N. Han and J. Shallit, <a href="https://arxiv.org/abs/2006.08909">On some conjectures of P. Barry</a>, arXiv:2006.08909 [math.NT], 2020.

%H J.-P. Allouche and J. Shallit, <a href="http://www.math.jussieu.fr/~allouche/kreg2.ps">The Ring of k-regular Sequences, II</a>

%H J.-P. Allouche and J. Shallit, <a href="http://dx.doi.org/10.1016/S0304-3975(03)00090-2">The ring of k-regular sequences, II</a>, Theoret. Computer Sci., 307 (2003), 3-29.

%H Danielle Cox and K. McLellan, <a href="https://www.fq.math.ca/Papers1/55-2/CoxMcLellan021717.pdf">A problem on generation sets containing Fibonacci numbers</a>, Fib. Quart., 55 (No. 2, 2017), 105-113.

%H Chandler Davis and Donald E. Knuth, Number Representations and Dragon Curves -- I and II, Journal of Recreational Mathematics, volume 3, number 2, April 1970, pages 66-81, and number 3, July 1970, pages 133-149. Reprinted with addendum in Donald E. Knuth, <a href="http://www-cs-faculty.stanford.edu/~uno/fg.html">Selected Papers on Fun and Games</a>, 2010, pages 571-614. Equation 3.2 g(n) = a(n-1).

%H P. Flajolet et al., <a href="http://algo.inria.fr/flajolet/Publications/FlGrKiPrTi94.pdf">Mellin Transforms And Asymptotics: Digital Sums</a>, Theoret. Computer Sci. 23 (1994), 291-314.

%H P. Flajolet and Lyle Ramshaw, <a href="http://dx.doi.org/10.1137/0209014">A note on Gray code and odd-even merge</a>, SIAM J. Comput. 9 (1980), 142-158.

%H S. Kropf and S. Wagner, <a href="https://arxiv.org/abs/1605.03654">q-Quasiadditive functions</a>, arXiv:1605.03654 [math.CO], 2016.

%H Sara Kropf and S. Wagner, <a href="https://arxiv.org/abs/1608.03700">On q-Quasiadditive and q-Quasimultiplicative Functions</a>, arXiv preprint arXiv:1608.03700 [math.CO], 2016.

%H Shuo Li, <a href="https://arxiv.org/abs/2007.08317">Palindromic length sequence of the ruler sequence and of the period-doubling sequence</a>, arXiv:2007.08317 [math.CO], 2020.

%H Helmut Prodinger and Friedrich J. Urbanek, <a href="https://doi.org/10.1016/0012-365X(79)90135-3">Infinite 0-1-Sequences Without Long Adjacent Identical Blocks</a>, Discrete Mathematics, volume 28, issue 3, 1979, pages 277-289. Also <a href="http://finanz.math.tugraz.at/~prodinger/pdffiles/long_adjacent.pdf">first author's copy</a>. Their "variation" v(k) at definition 3.4 is a(k).

%H Jeffrey Shallit, <a href="http://www.fq.math.ca/Papers1/43-3/paper43-3-9.pdf">The mathematics of Per Noergaard's rhythmic infinity system</a>, Fib. Q., 43 (2005), 262-268.

%H Ralf Stephan, <a href="/somedcgf.html">Some divide-and-conquer sequences ...</a>

%H Ralf Stephan, <a href="/A079944/a079944.ps">Table of generating functions</a>

%H <a href="/index/Cor#core">Index entries for "core" sequences</a>

%H <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>

%F a(2^k + i) = a(2^k - i + 1) + 1 for k >= 0 and 0 < i <= 2^k. - _Reinhard Zumkeller_, Aug 14 2001

%F a(2n+1) = 2a(n) - a(2n) + 1, a(4n) = a(2n), a(4n+2) = 1 + a(2n+1).

%F a(j+1) = a(j) + (-1)^A014707(j). - Christopher Hendrie (hendrie(AT)acm.org), Sep 11 2002

%F G.f.: (1/(1-x)) * Sum_{k>=0} x^2^k/(1+x^2^(k+1)). - _Ralf Stephan_, May 02 2003

%F Delete the 0, make subsets of 2^n terms; and reverse the terms in each subset to generate A088696. - _Gary W. Adamson_, Oct 19 2003

%F a(0) = 0, a(2n) = a(n) + [n odd], a(2n+1) = a(n) + [n even]. - _Ralf Stephan_, Oct 20 2003

%F a(n) = Sum_{k=1..n} (-1)^((k/2^A007814(k)-1)/2) = Sum_{k=1..n} (-1)^A025480(k-1). - _Ralf Stephan_, Oct 29 2003

%F a(n) = A069010(n) + A033264(n). - _Ralf Stephan_, Oct 29 2003

%F a(0) = 0 then a(n) = a(floor(n/2)) + (a(floor(n/2)) + n) mod 2. - _Benoit Cloitre_, Jan 20 2014

%F a(n) = A037834(n) + 1.

%e Considered as a triangle with 2^k terms per row, the first few rows are:

%e 1

%e 2, 1

%e 2, 3, 2, 1

%e 2, 3, 4, 3, 2, 3, 2, 1

%e ...

%e The n-th row becomes right half of next row; left half is mirrored terms of n-th row increased by one. - _Gary W. Adamson_, Jun 20 2012

%p A005811 := proc(n)

%p local i, b, ans;

%p if n = 0 then

%p return 0 ;

%p end if;

%p ans := 1;

%p b := convert(n, base, 2);

%p for i from nops(b)-1 to 1 by -1 do

%p if b[ i+1 ]<>b[ i ] then

%p ans := ans+1

%p fi

%p od;

%p return ans ;

%p end proc:

%p seq(A005811(i), i=1..50) ;

%p # second Maple program:

%p a:= n-> add(i, i=Bits[Split](Bits[Xor](n, iquo(n, 2)))):

%p seq(a(n), n=0..100); # _Alois P. Heinz_, Feb 01 2023

%t Table[ Length[ Length/@Split[ IntegerDigits[ n, 2 ] ] ], {n, 1, 255} ]

%o (PARI) a(n)=sum(k=1,n,(-1)^((k/2^valuation(k,2)-1)/2))

%o (PARI) a(n)=if(n<1,0,a(n\2)+(a(n\2)+n)%2) \\ _Benoit Cloitre_, Jan 20 2014

%o (PARI) a(n) = hammingweight(bitxor(n, n>>1)); \\ _Gheorghe Coserea_, Sep 03 2015

%o (Haskell)

%o import Data.List (group)

%o a005811 0 = 0

%o a005811 n = length $ group $ a030308_row n

%o a005811_list = 0 : f [1] where

%o f (x:xs) = x : f (xs ++ [x + x `mod` 2, x + 1 - x `mod` 2])

%o -- _Reinhard Zumkeller_, Feb 16 2013, Mar 07 2011

%o (Python)

%o def a(n): return bin(n^(n>>1))[2:].count("1") # _Indranil Ghosh_, Apr 29 2017

%Y Cf. A037834 (-1), A088748 (+1), A246960 (mod 4), A034947 (first differences), A000975 (indices of record highs).

%Y Cf. A056539, A014707, A014577, A082410, A030308, A090079, A044813, A165413, A226227, A226228, A226229.

%Y Partial sums of A112347.

%Y Cf. A003188.

%K easy,nonn,core,nice,hear

%O 0,3

%A _N. J. A. Sloane_, _Jeffrey Shallit_, _Simon Plouffe_

%E Additional description from _Wouter Meeussen_

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 March 29 08:08 EDT 2024. Contains 371265 sequences. (Running on oeis4.)