r"""
Python module for OEIS sequence number A000120.

1's-counting sequence: number of 1's in binary expansion of n.

Examples of use.
-----------------------------------------------------------------------
>>> from a000120 import *
>>> print a000120_list(20)
[0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3]
>>> print a000120_offset
0
>>> for x in a000120_list_pairs(6):
...     print x
...
(0, 0)
(1, 1)
(2, 1)
(3, 2)
(4, 1)
(5, 2)
>>> print a000120(4)
1
-----------------------------------------------------------------------
"""

from itertools import islice, izip

__all__ = ('a000120_offset', 'a000120_list', 'a000120_list_pairs', 'a000120')
__author__ = 'Nick Hobson <nickh@qbyte.org>'

a000120_offset = offset = 0
digit = {'0':0, '1':1, '2':1, '3':2, '4':1, '5':2, '6':2, '7':3, '8':1,
         '9':2, 'a':2, 'b':3, 'c':2, 'd':3, 'e':3, 'f':4, 'L':0}

def a000120_list(n):
    """Returns a list of the first n >= 0 terms."""
    if n < 0: raise ValueError, 'Input must be a non-negative integer'
    a = [0] * n
    if n < 2:
        return a
    a[1] = t = 1
    while t < n:
        for m in xrange(t, t+t):
            if m + m < n: a[m + m] = a[m]
            else: break
            if m + m + 1 < n: a[m + m + 1] = a[m] + 1
            else: break
        t += t
    return a

def a000120_list_pairs(n):
    """Returns a list of tuples (n, a(n)) of the first n >= 0 terms."""
    if n < 0: raise ValueError, 'Input must be a non-negative integer'
    return list(zip(xrange(offset, n+offset), a000120_list(n)))

def a000120(n):
    """Returns the term with index n >= 0; offset 0."""
    if n < offset: raise ValueError, 'Input must be an integer >= offset = ' + str(offset)
    return sum(digit[x] for x in hex(n)[2:])