cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

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

Original entry on oeis.org

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
Offset: 0

Views

Author

N. J. A. Sloane, Jeffrey Shallit, Simon Plouffe

Keywords

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, Sep 20 2003
Starting with 1 = partial sums of A034947: (1, 1, -1, 1, 1, -1, -1, 1, 1, 1, ...). - Gary W. Adamson, Jul 23 2008
The composer Per Nørgård's name is also written in the OEIS as Per Noergaard.
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
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

Examples

			Considered as a triangle with 2^k terms per row, the first few rows are:
  1
  2, 1
  2, 3, 2, 1
  2, 3, 4, 3, 2, 3, 2, 1
  ...
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

References

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

Links

Crossrefs

Cf. A037834 (-1), A088748 (+1), A246960 (mod 4), A034947 (first differences), A000975 (indices of record highs), A173318 (partial sums).
Cf. A056539, A014707, A014577, A082410, A030308, A090079, A044813, A165413, A226227, A226228, A226229.
Partial sums of A112347. Recursion depth of A035327.
Cf. A000120, A003188.

Programs

  • Haskell
    import Data.List (group)
a005811 0 = 0
a005811 n = length $ group $ a030308_row n
a005811_list = 0 : f [1] where
   f (x:xs) = x : f (xs ++ [x + x `mod` 2, x + 1 - x `mod` 2])
-- Reinhard Zumkeller, Feb 16 2013, Mar 07 2011
  • Maple
    A005811 := proc(n)
    local i, b, ans;
    if n = 0 then
        return 0 ;
    end if;
    ans := 1;
    b := convert(n, base, 2);
    for i from nops(b)-1 to 1 by -1 do
        if b[ i+1 ]<>b[ i ] then
            ans := ans+1
        fi
    od;
    return ans ;
end proc:
seq(A005811(i), i=1..50) ;
# second Maple program:
a:= n-> add(i, i=Bits[Split](Bits[Xor](n, iquo(n, 2)))):
seq(a(n), n=0..100);  # Alois P. Heinz, Feb 01 2023
  • Mathematica
    Table[ Length[ Length/@Split[ IntegerDigits[ n, 2 ] ] ], {n, 1, 255} ]
a[n_] := DigitCount[BitXor[n, Floor[n/2]], 2, 1]; Array[a, 100, 0] (* Amiram Eldar, Jul 11 2024 *)
  • PARI
    a(n)=sum(k=1,n,(-1)^((k/2^valuation(k,2)-1)/2))
  • PARI
    a(n)=if(n<1,0,a(n\2)+(a(n\2)+n)%2) \\ Benoit Cloitre, Jan 20 2014
  • PARI
    a(n) = hammingweight(bitxor(n, n>>1));  \\ Gheorghe Coserea, Sep 03 2015
  • Python
    def a(n): return bin(n^(n>>1))[2:].count("1") # Indranil Ghosh, Apr 29 2017

Formula

a(2^k + i) = a(2^k - i + 1) + 1 for k >= 0 and 0 < i <= 2^k. - Reinhard Zumkeller, 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 02 2003
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
a(0) = 0, a(2n) = a(n) + [n odd], a(2n+1) = a(n) + [n even]. - Ralf Stephan, 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, Oct 29 2003
a(n) = A069010(n) + A033264(n). - Ralf Stephan, Oct 29 2003
a(0) = 0 then a(n) = a(floor(n/2)) + (a(floor(n/2)) + n) mod 2. - Benoit Cloitre, Jan 20 2014
a(n) = A037834(n) + 1.
a(n) = A000120(A003188(n)). - Amiram Eldar, Jul 11 2024

Extensions

Additional description from Wouter Meeussen

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.