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