#!/usr/bin/python

from math import ceil, log

# Logarithms are only used to determine how far it's necessary to carry
# out a recursive calculation in order to generate the desired value.
# They aren't actually used to calculate the value itself (although
# in principle they could be).

def ld(n):
	# logarithmus dualis (dual logarithm, or logarithm to the base 2)

	return log(n)/log(2)

def ceil_ld(n):
	# ceiling of the log base 2 of n
	return ceil(ld(n))

def increment(n):
	return n + 1

def ones_binaryrep_list(n):
	# A list of the number of ones in the binary representation of
	# each of the first n integers, starting with 0.

	if n == 0:
		return [0]
	else:
		smaller = ones_binaryrep_list(n - 1)
		return smaller + map(increment, smaller)

def ones_graycoderep_list(n):
	# A list of the number of ones in the Gray code representation of
	# each of the first n integers, starting with 0.

	if n == 0:
		return [0]
	else:
		smaller = ones_graycoderep_list(n - 1)
		reversed = smaller[:]
		reversed.reverse()
		return smaller + map(increment, reversed)

def ones_binaryrep(n):
	# The number of ones in the binary representation of the integer n.
	return ones_binaryrep_list(ceil_ld(n+1))[n]

def ones_graycoderep(n):
	# The number of ones in the Gray code representation of the integer n.
	return ones_graycoderep_list(ceil_ld(n+1))[n]

# You might try:

#for i in range(10):
#	print ones_binaryrep(i)

#for i in range(10):
#	print ones_graycoderep(i)

# These are inefficient because there is no memoization (caching of
# calculated values).