day1/exercise/amicable.py
author Santosh G. Vattam <vattam.santosh@gmail.com>
Fri, 23 Oct 2009 17:12:25 +0530
changeset 159 01f57cda252f
parent 94 8c92864c184b
child 380 669b72283b55
permissions -rw-r--r--
Manual merge of conflicting branches.
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
94
8c92864c184b Almost last set of official solutions and final quiz.
Madhusudan.C.S <madhusudancs@gmail.com>
parents: 64
diff changeset
     1
def is_perfect_square(n):
8c92864c184b Almost last set of official solutions and final quiz.
Madhusudan.C.S <madhusudancs@gmail.com>
parents: 64
diff changeset
     2
    i = 1
8c92864c184b Almost last set of official solutions and final quiz.
Madhusudan.C.S <madhusudancs@gmail.com>
parents: 64
diff changeset
     3
    while i * i < n:
8c92864c184b Almost last set of official solutions and final quiz.
Madhusudan.C.S <madhusudancs@gmail.com>
parents: 64
diff changeset
     4
        i += 1
8c92864c184b Almost last set of official solutions and final quiz.
Madhusudan.C.S <madhusudancs@gmail.com>
parents: 64
diff changeset
     5
    return i * i == n, i
64
333092b68926 Added quiz tex file and all exercise problems Madhu worked out.
Madhusudan.C.S <madhusudancs@gmail.com>
parents:
diff changeset
     6
333092b68926 Added quiz tex file and all exercise problems Madhu worked out.
Madhusudan.C.S <madhusudancs@gmail.com>
parents:
diff changeset
     7
def aliquot(n):
94
8c92864c184b Almost last set of official solutions and final quiz.
Madhusudan.C.S <madhusudancs@gmail.com>
parents: 64
diff changeset
     8
    sum = 1
8c92864c184b Almost last set of official solutions and final quiz.
Madhusudan.C.S <madhusudancs@gmail.com>
parents: 64
diff changeset
     9
    i = 2
8c92864c184b Almost last set of official solutions and final quiz.
Madhusudan.C.S <madhusudancs@gmail.com>
parents: 64
diff changeset
    10
8c92864c184b Almost last set of official solutions and final quiz.
Madhusudan.C.S <madhusudancs@gmail.com>
parents: 64
diff changeset
    11
    is_ps, root = is_perfect_square(n)
8c92864c184b Almost last set of official solutions and final quiz.
Madhusudan.C.S <madhusudancs@gmail.com>
parents: 64
diff changeset
    12
    while i < root:
64
333092b68926 Added quiz tex file and all exercise problems Madhu worked out.
Madhusudan.C.S <madhusudancs@gmail.com>
parents:
diff changeset
    13
        if n % i == 0:
94
8c92864c184b Almost last set of official solutions and final quiz.
Madhusudan.C.S <madhusudancs@gmail.com>
parents: 64
diff changeset
    14
            sum += i + (n / i)
8c92864c184b Almost last set of official solutions and final quiz.
Madhusudan.C.S <madhusudancs@gmail.com>
parents: 64
diff changeset
    15
        i += 1
64
333092b68926 Added quiz tex file and all exercise problems Madhu worked out.
Madhusudan.C.S <madhusudancs@gmail.com>
parents:
diff changeset
    16
    return sum
333092b68926 Added quiz tex file and all exercise problems Madhu worked out.
Madhusudan.C.S <madhusudancs@gmail.com>
parents:
diff changeset
    17
333092b68926 Added quiz tex file and all exercise problems Madhu worked out.
Madhusudan.C.S <madhusudancs@gmail.com>
parents:
diff changeset
    18
amicable = []
94
8c92864c184b Almost last set of official solutions and final quiz.
Madhusudan.C.S <madhusudancs@gmail.com>
parents: 64
diff changeset
    19
8c92864c184b Almost last set of official solutions and final quiz.
Madhusudan.C.S <madhusudancs@gmail.com>
parents: 64
diff changeset
    20
n = 1000
8c92864c184b Almost last set of official solutions and final quiz.
Madhusudan.C.S <madhusudancs@gmail.com>
parents: 64
diff changeset
    21
while n < 10000:
64
333092b68926 Added quiz tex file and all exercise problems Madhu worked out.
Madhusudan.C.S <madhusudancs@gmail.com>
parents:
diff changeset
    22
    m = aliquot(n)
94
8c92864c184b Almost last set of official solutions and final quiz.
Madhusudan.C.S <madhusudancs@gmail.com>
parents: 64
diff changeset
    23
    if m > n and aliquot(m) == n:
8c92864c184b Almost last set of official solutions and final quiz.
Madhusudan.C.S <madhusudancs@gmail.com>
parents: 64
diff changeset
    24
        print m, n
8c92864c184b Almost last set of official solutions and final quiz.
Madhusudan.C.S <madhusudancs@gmail.com>
parents: 64
diff changeset
    25
    n += 1