cp's OEIS Frontend

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

%I A005811 M0110 #188 Jan 05 2025 19:51:33
%S A005811 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 A005811 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 A005811 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 A005811 Number of runs in binary expansion of n (n>0); number of 1's in Gray code for n.
%C A005811 Starting with a(1) = 0 mirror all initial 2^k segments and increase by one.
%C A005811 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 A005811 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 A005811 Starting with 1 = partial sums of A034947: (1, 1, -1, 1, 1, -1, -1, 1, 1, 1, ...). - _Gary W. Adamson_, Jul 23 2008
%C A005811 The composer Per Nørgård's name is also written in the OEIS as Per Noergaard.
%C A005811 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 A005811 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 A005811 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A005811 T. D. Noe, <a href="/A005811/b005811.txt">Table of n, a(n) for n = 0..10000</a>
%H A005811 Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Matters Computational (The Fxtbook)</a>.
%H A005811 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 A005811 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 A005811 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 A005811 Danielle Cox and Karyn McLellan, <a href="https://web.archive.org/web/2024*/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 A005811 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 A005811 Chandler Davis and Donald E. Knuth, <a href="/A005811/a005811.pdf">Number Representations and Dragon Curves</a>, Journal of Recreational Mathematics, volume 3, number 2, April 1970, pages 66-81, and number 3, July 1970, pages 133-149. [Cached copy, with permission]
%H A005811 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 A005811 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 A005811 Sara Kropf and Stephan Wagner, <a href="https://arxiv.org/abs/1605.03654">q-Quasiadditive functions</a>, arXiv:1605.03654 [math.CO], 2016.
%H A005811 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 A005811 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 A005811 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 A005811 Jeffrey Shallit, <a href="https://web.archive.org/web/2024*/https://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 A005811 Ralf Stephan, <a href="/somedcgf.html">Some divide-and-conquer sequences with (relatively) simple ordinary generating functions</a>, 2004.
%H A005811 Ralf Stephan, <a href="/A079944/a079944.ps">Table of generating functions</a>.
%H A005811 <a href="/index/Cor#core">Index entries for "core" sequences</a>.
%H A005811 <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>.
%F A005811 a(2^k + i) = a(2^k - i + 1) + 1 for k >= 0 and 0 < i <= 2^k. - _Reinhard Zumkeller_, Aug 14 2001
%F A005811 a(2n+1) = 2a(n) - a(2n) + 1, a(4n) = a(2n), a(4n+2) = 1 + a(2n+1).
%F A005811 a(j+1) = a(j) + (-1)^A014707(j). - Christopher Hendrie (hendrie(AT)acm.org), Sep 11 2002
%F A005811 G.f.: (1/(1-x)) * Sum_{k>=0} x^2^k/(1+x^2^(k+1)). - _Ralf Stephan_, May 02 2003
%F A005811 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 A005811 a(0) = 0, a(2n) = a(n) + [n odd], a(2n+1) = a(n) + [n even]. - _Ralf Stephan_, Oct 20 2003
%F A005811 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 A005811 a(n) = A069010(n) + A033264(n). - _Ralf Stephan_, Oct 29 2003
%F A005811 a(0) = 0 then a(n) = a(floor(n/2)) + (a(floor(n/2)) + n) mod 2. - _Benoit Cloitre_, Jan 20 2014
%F A005811 a(n) = A037834(n) + 1.
%F A005811 a(n) = A000120(A003188(n)). - _Amiram Eldar_, Jul 11 2024
%e A005811 Considered as a triangle with 2^k terms per row, the first few rows are:
%e A005811   1
%e A005811   2, 1
%e A005811   2, 3, 2, 1
%e A005811   2, 3, 4, 3, 2, 3, 2, 1
%e A005811   ...
%e A005811 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 A005811 := proc(n)
%p A005811     local i, b, ans;
%p A005811     if n = 0 then
%p A005811         return 0 ;
%p A005811     end if;
%p A005811     ans := 1;
%p A005811     b := convert(n, base, 2);
%p A005811     for i from nops(b)-1 to 1 by -1 do
%p A005811         if b[ i+1 ]<>b[ i ] then
%p A005811             ans := ans+1
%p A005811         fi
%p A005811     od;
%p A005811     return ans ;
%p A005811 end proc:
%p A005811 seq(A005811(i), i=1..50) ;
%p A005811 # second Maple program:
%p A005811 a:= n-> add(i, i=Bits[Split](Bits[Xor](n, iquo(n, 2)))):
%p A005811 seq(a(n), n=0..100);  # _Alois P. Heinz_, Feb 01 2023
%t A005811 Table[ Length[ Length/@Split[ IntegerDigits[ n, 2 ] ] ], {n, 1, 255} ]
%t A005811 a[n_] := DigitCount[BitXor[n, Floor[n/2]], 2, 1]; Array[a, 100, 0] (* _Amiram Eldar_, Jul 11 2024 *)
%o A005811 (PARI) a(n)=sum(k=1,n,(-1)^((k/2^valuation(k,2)-1)/2))
%o A005811 (PARI) a(n)=if(n<1,0,a(n\2)+(a(n\2)+n)%2) \\ _Benoit Cloitre_, Jan 20 2014
%o A005811 (PARI) a(n) = hammingweight(bitxor(n, n>>1));  \\ _Gheorghe Coserea_, Sep 03 2015
%o A005811 (Haskell)
%o A005811 import Data.List (group)
%o A005811 a005811 0 = 0
%o A005811 a005811 n = length $ group $ a030308_row n
%o A005811 a005811_list = 0 : f [1] where
%o A005811    f (x:xs) = x : f (xs ++ [x + x `mod` 2, x + 1 - x `mod` 2])
%o A005811 -- _Reinhard Zumkeller_, Feb 16 2013, Mar 07 2011
%o A005811 (Python)
%o A005811 def a(n): return bin(n^(n>>1))[2:].count("1") # _Indranil Ghosh_, Apr 29 2017
%Y A005811 Cf. A037834 (-1), A088748 (+1), A246960 (mod 4), A034947 (first differences), A000975 (indices of record highs), A173318 (partial sums).
%Y A005811 Cf. A056539, A014707, A014577, A082410, A030308, A090079, A044813, A165413, A226227, A226228, A226229.
%Y A005811 Partial sums of A112347. Recursion depth of A035327.
%Y A005811 Cf. A000120, A003188.
%K A005811 easy,nonn,core,nice,hear
%O A005811 0,3
%A A005811 _N. J. A. Sloane_, _Jeffrey Shallit_, _Simon Plouffe_
%E A005811 Additional description from _Wouter Meeussen_