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 ' 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:])