day1/exercise/find_pow_2.py
author Madhusudan.C.S <madhusudancs@gmail.com>
Fri, 02 Apr 2010 15:45:07 +0530
changeset 453 38adf73fd123
parent 64 333092b68926
permissions -rw-r--r--
Merged Vattam and Puneeth branches.
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
64
333092b68926 Added quiz tex file and all exercise problems Madhu worked out.
Madhusudan.C.S <madhusudancs@gmail.com>
parents:
diff changeset
     1
def is_pow_2(n):
333092b68926 Added quiz tex file and all exercise problems Madhu worked out.
Madhusudan.C.S <madhusudancs@gmail.com>
parents:
diff changeset
     2
    bin_count = 0
333092b68926 Added quiz tex file and all exercise problems Madhu worked out.
Madhusudan.C.S <madhusudancs@gmail.com>
parents:
diff changeset
     3
    while n > 0:
333092b68926 Added quiz tex file and all exercise problems Madhu worked out.
Madhusudan.C.S <madhusudancs@gmail.com>
parents:
diff changeset
     4
        if n % 2 == 1:
333092b68926 Added quiz tex file and all exercise problems Madhu worked out.
Madhusudan.C.S <madhusudancs@gmail.com>
parents:
diff changeset
     5
            bin_count += 1
333092b68926 Added quiz tex file and all exercise problems Madhu worked out.
Madhusudan.C.S <madhusudancs@gmail.com>
parents:
diff changeset
     6
        if bin_count > 1:
333092b68926 Added quiz tex file and all exercise problems Madhu worked out.
Madhusudan.C.S <madhusudancs@gmail.com>
parents:
diff changeset
     7
            return False
333092b68926 Added quiz tex file and all exercise problems Madhu worked out.
Madhusudan.C.S <madhusudancs@gmail.com>
parents:
diff changeset
     8
        n /= 2
333092b68926 Added quiz tex file and all exercise problems Madhu worked out.
Madhusudan.C.S <madhusudancs@gmail.com>
parents:
diff changeset
     9
333092b68926 Added quiz tex file and all exercise problems Madhu worked out.
Madhusudan.C.S <madhusudancs@gmail.com>
parents:
diff changeset
    10
    return bin_count == 1
333092b68926 Added quiz tex file and all exercise problems Madhu worked out.
Madhusudan.C.S <madhusudancs@gmail.com>
parents:
diff changeset
    11
333092b68926 Added quiz tex file and all exercise problems Madhu worked out.
Madhusudan.C.S <madhusudancs@gmail.com>
parents:
diff changeset
    12
def collatz_pow_2(n):
333092b68926 Added quiz tex file and all exercise problems Madhu worked out.
Madhusudan.C.S <madhusudancs@gmail.com>
parents:
diff changeset
    13
    if n == 1: return 4
333092b68926 Added quiz tex file and all exercise problems Madhu worked out.
Madhusudan.C.S <madhusudancs@gmail.com>
parents:
diff changeset
    14
    if n == 2: return 4
333092b68926 Added quiz tex file and all exercise problems Madhu worked out.
Madhusudan.C.S <madhusudancs@gmail.com>
parents:
diff changeset
    15
    collatz_pow_2 = []
333092b68926 Added quiz tex file and all exercise problems Madhu worked out.
Madhusudan.C.S <madhusudancs@gmail.com>
parents:
diff changeset
    16
    while n > 2:
333092b68926 Added quiz tex file and all exercise problems Madhu worked out.
Madhusudan.C.S <madhusudancs@gmail.com>
parents:
diff changeset
    17
        print n, 
333092b68926 Added quiz tex file and all exercise problems Madhu worked out.
Madhusudan.C.S <madhusudancs@gmail.com>
parents:
diff changeset
    18
        if is_pow_2(n):
333092b68926 Added quiz tex file and all exercise problems Madhu worked out.
Madhusudan.C.S <madhusudancs@gmail.com>
parents:
diff changeset
    19
            collatz_pow_2.append(n)
333092b68926 Added quiz tex file and all exercise problems Madhu worked out.
Madhusudan.C.S <madhusudancs@gmail.com>
parents:
diff changeset
    20
333092b68926 Added quiz tex file and all exercise problems Madhu worked out.
Madhusudan.C.S <madhusudancs@gmail.com>
parents:
diff changeset
    21
        if n % 2:
333092b68926 Added quiz tex file and all exercise problems Madhu worked out.
Madhusudan.C.S <madhusudancs@gmail.com>
parents:
diff changeset
    22
            n = n * 3 - 1
333092b68926 Added quiz tex file and all exercise problems Madhu worked out.
Madhusudan.C.S <madhusudancs@gmail.com>
parents:
diff changeset
    23
        else:
333092b68926 Added quiz tex file and all exercise problems Madhu worked out.
Madhusudan.C.S <madhusudancs@gmail.com>
parents:
diff changeset
    24
            n /= 2 
333092b68926 Added quiz tex file and all exercise problems Madhu worked out.
Madhusudan.C.S <madhusudancs@gmail.com>
parents:
diff changeset
    25
333092b68926 Added quiz tex file and all exercise problems Madhu worked out.
Madhusudan.C.S <madhusudancs@gmail.com>
parents:
diff changeset
    26
    return max(collatz_pow_2)
333092b68926 Added quiz tex file and all exercise problems Madhu worked out.
Madhusudan.C.S <madhusudancs@gmail.com>
parents:
diff changeset
    27
333092b68926 Added quiz tex file and all exercise problems Madhu worked out.
Madhusudan.C.S <madhusudancs@gmail.com>
parents:
diff changeset
    28
import sys
333092b68926 Added quiz tex file and all exercise problems Madhu worked out.
Madhusudan.C.S <madhusudancs@gmail.com>
parents:
diff changeset
    29
collatz_pow_2(int(sys.argv[1]))