login
This site is supported by donations 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)
93
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; text; 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, 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

REFERENCES

Danielle Cox and K. McLellan, A problem on generation sets containing Fibonacci numbers, Fib. Quart., 55 (No. 2, 2017), 105-113.

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, Matters Computational (The Fxtbook)

J.-P. Allouche, J. Shallit, The Ring of k-regular Sequences, II

J.-P. Allouche and J. Shallit, The ring of k-regular sequences, II, Theoret. Computer Sci., 307 (2003), 3-29.

P. Flajolet et al., Mellin Transforms And Asymptotics: Digital Sums, Theoret. Computer Sci. 23 (1994), 291-314.

P. Flajolet and Lyle Ramshaw, A note on Gray code and odd-even merge, SIAM J. Comput. 9 (1980), 142-158.

S. Kropf, S. Wagner, q-Quasiadditive functions, arXiv:1605.03654 [math.CO], 2016.

Sara Kropf, S. Wagner, On q-Quasiadditive and q-Quasimultiplicative Functions, arXiv preprint arXiv:1608.03700 [math.CO], 2016.

Jeffrey Shallit, The mathematics of Per Noergaard's rhythmic infinity system, Fib. Q., 43 (2005), 262-268.

R. Stephan, Some divide-and-conquer sequences ...

R. Stephan, Table of generating functions

Index entries for "core" sequences

Index entries for sequences related to binary expansion of n

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) modulo 2. - Benoit Cloitre, Jan 20 2014

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

EXAMPLE

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

... 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

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) ;

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))

(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

(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

(Python)

def a(n): return bin(n^(n>>1))[2:].count("1") # Indranil Ghosh, Apr 29 2017

CROSSREFS

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

A000975 gives records. - Oliver Kosut (vern(AT)mit.edu), May 06 2002

Sequence in context: A267108 A004738 A043554 * A008342 A277214 A278603

Adjacent sequences:  A005808 A005809 A005810 * A005812 A005813 A005814

KEYWORD

easy,nonn,core,nice,hear

AUTHOR

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

EXTENSIONS

Additional description from Wouter Meeussen

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 15 19:24 EDT 2018. Contains 316237 sequences. (Running on oeis4.)