import sys # for command-line arguments
# Given a number n, print all of its binary factors. For example,
# 105 = 64 + 32 + 8 + 1
n = int(sys.argv[1]) # n is command-line argument
power = 1
factors = []
binary = "" # binary bit string
while n>0:
if n%2==1:
factors.append(power)
binary = str(n%2) + binary # note bit added in front of string
power = power * 2
n = n/2
# while
print # blank line
print "in binary:", binary
print "factors:",factors
# Inductive proof that every integer >=0 has a binary factorization:
# This proof requires "strong" induction. That is, we prove the base
# case, then assume that it is true for all values <=n, then prove it
# for n+1:
# First, note that if m has a binary factor, then 2*m has has a binary
# factor. For example, if m = 2**a + 2**b + 2**c, then 2*m is equal to
# 2**(a+1) + 2**(b+1) + 2**(c+1). Multiplying by 2 effectively shifts the
# binary digits to the left by one.
# Now the result is trivial for n == 0 and n==1. Now assume that it holds
# for all m<=n. We want to show that it holds for n+1. There are two cases
# to consider: n is even or n is odd. If n is even, the result is trivial
# since we just add 1 to the assumed binary factors of n. If n is odd, that
# means n = 2*m+1. So n+1 = 2(m+1). But m+1<=n, so n+1 also has a binary
# factorization. (n-1=2m) so m=(n-1)/2. so m+1 = (n-1)/2 + 1, which is <= n
# for n>1