Logo

Greetings from The On-Line Encyclopedia of Integer Sequences!

Hints

Search: id:A000120
Displaying 1-1 of 1 results found. page 1
     Format: long | short | internal | text      Sort: relevance | references | number      Highlight: on | off
A000120 1's-counting sequence: number of 1's in binary expansion of n (or the binary weight of n).
(Formerly M0105 N0041)
+0
296
0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3 (list; graph; listen)
OFFSET

0,4

COMMENT

a(n) is also the largest integer such that 2^a(n) divides binomial(2n,n)=A000984(n) - Benoit Cloitre (benoit7848c(AT)orange.fr), Mar 27 2002

To construct the sequence, start with 0 and use the rule: If k>=0 and a(0),a(1),...,a(2^k-1) are the 2^k first terms, then the next 2^k terms are a(0)+1,a(1)+1,...,a(2^k-1)+1. - Benoit Cloitre (benoit7848c(AT)orange.fr), Jan 30 2003

An example of a fractal sequence. That is, if you omit every other number in the sequence, you get the original sequence. And of course this can be repeated. So if you form the sequence a(0 * 2^n), a(1 * 2^n), a(2 * 2^n), a(3 * 2^n), ... (for any integer n > 0), you get the original sequence. - Christopher.Hills(AT)sepura.co.uk, May 14, 2003

The n-th row of Pascal's triangle has 2^k distinct odd binomial coefficients where k=a(n)-1. - Lekraj Beedassy (blekraj(AT)yahoo.com), May 15 2003

a(0)=0, a(n)=a(n-2^log_2(floor(n)))+1. Examples: a(6)=a(6-2^2)+1=a(2)+1=a(2-2^1)+1+1=a(0)+2=2; a(101)=a(101-2^6)+1=a(37)+1=a(37-2^5)+2=a(5-2^2)+3=a(1-2^0)+4=a(0)+4=4; a(6275)=a(6275-2^12)+1=a(2179-2^11)+2=a(131-2^7)+3=a(3-2^1)+4=a(1-2^0)+5=5; a(4129)=a(4129-2^12)+1=a(33-2^5)+2=a(1-2^0)+3=3; - Hieronymus Fischer (Hieronymus.Fischer(AT)gmx.de), Jan 22 2006

Fixed point of the morphism 0 -> 01, 1 -> 12, 2 -> 23, 3 -> 34, 4 -> 45, etc., starting from a(0) = 0. - Robert G. Wilson v, Jan 24 2006. - Jeremy Gardiner (jeremy.gardiner(AT)btinternet.com), Jan 25 2006

a(n) = number of times n appears among the mystery calculator sequences: A005408, A042964, A047566, A115419, A115420, A115421. - Jeremy Gardiner (jeremy.gardiner(AT)btinternet.com), Jan 25 2006

a(n) = number of solutions of the diophantine equation 2^m*k+2^(m-1)+i=n, where m>=1, k>=0, 0<=i<2^(m-1); a(5)=2 because only (m,k,i)=(1,2,0) [2^1*2+2^0+0=5] and (m,k,i)=(3,0,1) [2^3*0+2^2+1=5] are solutions. - Hieronymus Fischer (Hieronymus.Fischer(AT)gmx.de), Jan 31 2006

The first appearance of k, k=>0, is at a(2^k). - Robert G. Wilson v Jul 27 2006

a(n) = A138530(n,2) for n > 1. - Reinhard Zumkeller (reinhard.zumkeller(AT)gmail.com), Mar 26 2008

REFERENCES

J.-P. Allouche and J. Shallit, The ring of k-regular sequences, Theoretical Computer Sci., 98 (1992), 163-197.

Emmanuel Ferrand, Deformations of the Taylor Formula, Journal of Integer Sequences, Vol. 10 (2007), Article 07.1.7.

R. L. Graham, On primitive graphs and optimal vertex assignments, pp. 170-186 of Internat. Conf. Combin. Math. (New York, 1970), Annals of the NY Academy of Sciences, Vol. 175, 1970.

M. D. McIlroy, The number of 1's in binary integers: bounds and extremal properties, SIAM J. Comput., 3 (1974), 255-261.

Problem B-82, Fib. Quart., 4 (1966), 374-375.

LINKS

N. J. A. Sloane, Table of n, a(n) for n = 0..10000

S. Finch, P. Sebah and Z.-Q. Bai, Odd Entries in Pascal's Trinomial Triangle (arXiv:0802.2654)

J.-P. Allouche and J. Shallit, The ring of k-regular sequences, Theoretical Computer Sci., 98 (1992), 163-197.

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

Michael Gilleland, Some Self-Similar Integer Sequences

Nick Hobson, Python program for this sequence

K. Q. Ji and H. S. Wilf, Extreme Palindromes

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

R. Stephan, Table of generating functions

R. Stephan, Divide-and-conquer generating functions. I. Elementary sequences

Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics.

Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics.

Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics.

Eric Weisstein's World of Mathematics, Digit Sum

Wolfram Research, Numbers in Pascal's triangle

Index entries for "core" sequences

Index entries for sequences related to binary expansion of n

FORMULA

a(0) = 0, a(2n) = a(n), a(2n+1) = a(n) + 1.

a(n) = a(n-1)+1-A007814(n) = log2[A001316(n)] = 2n-A005187(n) = A070939(n)-A023416(n). - Henry Bottomley (se16(AT)btinternet.com), Apr 04 2001; corrected by Ralf Stephan (ralf(AT)ark.in-berlin.de), Apr 15 2002

a(n)=log2(A000984(n)/A001790(n) ). - Benoit Cloitre, Oct 02 2002

For n>0, a(n)=n-sum(k=1, n, A007814(k)). - Benoit Cloitre (benoit7848c(AT)orange.fr), Oct 19 2002

a(n)=n-sum(k>0, floor(n/2^k))=n-A011371(n). - Benoit Cloitre, Dec 19 2002

G.f.: 1/(1-x) * Sum(k>=0, x^(2^k)/(1+x^(2^k))). - Ralf Stephan (ralf(AT)ark.in-berlin.de), Apr 19 2003

A fixed point of the mapping 0 -> 01, 1 -> 12, 2 -> 23, 3 -> 34, 4 -> 45, ... With f(i) = floor(n/2^i), a(n) is the number of odd numbers in the sequence f(0), f(1), f(2), f(3), f(4), f(5), ... - DELEHAM Philippe (kolotoko(AT)wanadoo.fr), Jan 04 2004

When read mod 2 gives the Morse-Thue sequence A010060.

Where floor_pow4(n) is n rounded down to the next power of four, floor_pow4(n) = 4 ^ floor(log4 n) a(0) = 0, a(1) = 1, a(2) = 1, a(3) = 2, a(n) = a(floor(n / floor_pow4(n))) + a(n % floor_pow4(n)) - Stephen K. Touset (stephen(AT)touset.org), Apr 04 2007

a(n)=n-sum{2<=k<=n, sum{j|n,j>=2, floor(log_2(j))-floor(log_2(j-1))}}. - Hieronymus Fischer (Hieronymus.Fischer(AT)gmx.de), Jun 18 2007

EXAMPLE

a(4) = a(0) + a(0) = 0

a(8) = a(2) + a(0) = 1

a(13) = a(3) + a(1) = 2 + 1 = 3

a(23) = a(1) + a(7) = 1 + a(1) + a(3) = 1 + 1 + 2 = 4

MAPLE

A000120 := proc(n) local w, m, i; w := 0; m := n; while m > 0 do i := m mod 2; w := w+i; m := (m-i)/2; od; w; end: wt := A000120;

MATHEMATICA

Table[ Count[ IntegerDigits[n, 2], 1], {n, 0, 100} ]

Nest[ Flatten[ #1 /. a_Integer -> {a, a + 1}] &, {0}, 7] (* Robert G. Wilson v Jul 27 2006 *)

Table[Plus @@ IntegerDigits[n, 2], {n, 0, 104}]

PROGRAM

(PARI) a(n)=if(n<0, 0, 2*n-valuation((2*n)!, 2))

(PARI) a(n)=if(n<0, 0, subst(Pol(binary(n)), x, 1))

(PARI) a(n)=if(n<1, 0, a(n\2)+n%2) - Michael Somos Mar 06 2004

Common LISP: (defun floor-to-power (n pow) (declare (fixnum pow)) (expt pow (floor (log n pow)))) (defun enabled-bits (n) (if (< n 4) (nth n (list 0 1 1 2)) (+ (enabled-bits (floor (/ n (floor-to-power n 4)))) (enabled-bits (mod n (floor-to-power n 4)))))) - Stephen K. Touset (stephen(AT)touset.org), Apr 04 2007

CROSSREFS

The basic sequences concerning the binary expansion of n are this one, A000788, A000069, A001969, A023416, A059015, A007088.

a(n)=n-A011371[n]. - Labos E. (labos(AT)ana.sote.hu), Jul 27 2000

Sum of digits of n written in base 2-16: this sequence, A053735, A053737, A053824, A053827, A053828, A053829, A053830, A007953, A053831, A053832, A053833, A053834, A053835, A053836.

Cf. A007953.

This is Guy Steele's sequence GS(3,4) (see A135416).

Adjacent sequences: A000117 A000118 A000119 this_sequence A000121 A000122 A000123

Sequence in context: A105056 A105061 A105164 this_sequence A105062 A106487 A105102

KEYWORD

nonn,easy,core,nice

AUTHOR

njas

EXTENSIONS

More terms from Stephen K. Touset (stephen(AT)touset.org), Apr 04 2007

page 1

Search completed in 0.005 seconds

Lookup | Welcome | Find friends | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Puzzles | Hot | Classics
More pages | Superseeker | Maintained by N. J. A. Sloane (njas@research.att.com)

Last modified May 16 23:01 EDT 2008. Contains 139884 sequences.


AT&T Labs Research