Solution Exercise 758: algorithm python to find list of all tuples of integers satisfying some conditions

Sep 17, 2020

Exercise 758

Write a python algorithm as a function that takes as argument a pair of integers (d, s) and returns a list of all the couple who determine the list of all pairs of integers (m, n) of greatest common divisor GCD(m, n) = d and of sum m + n = s (*)

Solution

# Creating a functon which calculating the gcd of two integers.
def gcd(m , n):
    # initializing the gcd of m and n
    d = m
    while( m%d != 0 or n%d != 0):
        d = d - 1
    return d
# creating a function that solve th problem (*)
def tuplesSolutions(d , s):
    # initializing the list of tuples solutions
    listTuples = []
    for m in range(1 , s ):
        for n in range(1 ,s):
            if gcd(m , n) == d and m + n == s:
                listTuples.append((m,n))
    return listTuples
# Testing algorithm
print("List of tuples (m,n) such that m + n = 140 et gcd(m,n) = 7 is : n" , tuplesSolutions(7 , 140))
"""
The output is :
List of tuples (m,n) such that m + n = 140 et gcd(m,n) = 7 is : 
 [(7, 133), (21, 119), (49, 91), (63, 77), (77, 63), (91, 49), (119, 21), (133, 7)]
"""