5
$\begingroup$

Let $1(n)$ be the number of digits $1$ in binary representation of number $n$.

For example, $13=1101_2$ so $1(13)=3\\$

Is there explicit form of $\,\,\sum{1(i)x^i} $?

I checked OEIS and didn't find information about this sequence (1,1,2,2,2,3,1,2,2,3,...)

Improve this question
$\endgroup$
4
  • 5
    $\begingroup$ oeis.org/A000120 $\endgroup$
    – Zack Wolske
    Commented Mar 25, 2014 at 17:56
  • $\begingroup$ Can you be more explicit how to obtain the sequence? $\endgroup$
    – Stephan Müller
    Commented Mar 25, 2014 at 18:06
  • 2
    $\begingroup$ Your version is missing $1(4)=1$ $\endgroup$
    – Henry
    Commented Mar 25, 2014 at 22:56
  • $\begingroup$ For those looking to actually count binary 1s in computer program code, you may enjoy reading fast bit-counting routines. $\endgroup$
    – ErikE
    Commented Mar 25, 2014 at 23:18

2 Answers 2

Reset to default
19
$\begingroup$

The generating function you ask about, more typically written as $\sum_{i\ge 0} s_2(i) x^i$, can be expressed as $$\frac{1}{1-x} \sum_{m\ge 0} \frac{x^{2^m}}{1+x^{2^m}}$$ The number of 1's in the binary expansion is just the sums of digits; there also exists a generalization for sums of digits function in other bases. For details, references and further information, see for example "Generating Functions for the Digital Sum and Other Digit Counting Sequences" by Adams-Watters and Ruskey (Journal of Integer Sequences, 2009)

Improve this answer
$\endgroup$
7
$\begingroup$

By the way, the reason why the OP did not find the sequence in the OEIS is that he/she wrote down the first few terms incorrectly. They are 0,1,1,2,1,2,2,3, ..., which is sequence http://oeis.org/A000120 .

Improve this answer
$\endgroup$
1
  • 5
    $\begingroup$ This hsould be a comment $\endgroup$
    – Darkhogg
    Commented Mar 25, 2014 at 22:51

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .