# 
# Euclidean algorithm for finding GCD or GCF
# - from the Wikipedia page
"""
The GCD of two numbers is the largest number that divides both of them
without leaving a remainder. The Euclidean algorithm is based on the
principle that the greatest common divisor of two numbers does not change
if the smaller number is subtracted from the larger number.

For example, 21 is the GCD of 252 and 105 (252 = 21 * 12; 105 = 21 * 5);
since 252 - 105 = 147, the GCD of 147 and 105 is also 21.

Since the larger of the two numbers is reduced, repeating this process
gives successively smaller numbers until one of them is zero.
When that occurs, the GCD is the remaining nonzero number.
By reversing the steps in the Euclidean algorithm, the GCD can be
expressed as a sum of the two original numbers each multiplied by a
positive or negative integer, e.g., 21 = [5 * 105] + [(-2) * 252].
This important property is known as Bezout's identity.
"""
from operator import mul

def reduce_(tup):
    """
    returns the modulus and minum value of two numbers in a tuple
    tup --> ( max(tup) % min(tup), min(tup) )
    """
    return (max(tup) % min(tup), min(tup))

def done(tup):
    """
    returns true if any item in the tuple is 0
    """
    return not reduce(mul, tup)

def egcd(tup):
    """
    returns the greatest common divisor of two numbers

    Euclidean algorithm
    """
    return (done(reduce_(tup)) and min(tup)) or egcd(reduce_(tup))

def egcd3(tup3):
    """
    returns the greatest common divisor of three numbers

    Euclidean algorithm
    """
    return egcd((tup3[0], egcd((tup3[1], tup3[2]))))
    
tup3 = (1989, 153, 867)
print tup3, ':\t', egcd3(tup3)

tup3 = (1989, 867, 153)
print tup3, ':\t', egcd3(tup3)

tup3 = (867, 1989, 153)
print tup3, ':\t', egcd3(tup3)

tup3 = (867, 153, 1989)
print tup3, ':\t', egcd3(tup3)

tup3 = (153, 1989, 867)
print tup3, ':\t', egcd3(tup3)

tup3 = (153, 867, 1989)
print tup3, ':\t', egcd3(tup3)