Project Euler Problem 110


In the following equation x, y, and n are positive integers.

$\frac{1}{x} + \frac{1}{y} = \frac{1}{n}$

It can be verified that when n = 1260 there are 113 distinct solutions and this is the least value of n for which the total number of distinct solutions exceeds one hundred.

What is the least value of n for which the number of distinct solutions exceeds four million?


To solve the problem first I investigated about the equation and after researching I found that the number of solutions equals to the number of divisors of n2, and as they have to be unique it has to be divided by 2. The number of divisors is equal to the multiplication of the number of appearances plus one of each prime factor in n2.

As we know that we are looking for squares of numbers the number of appearances of each prime factor is even, so what we are going to multiply are odd numbers. All what I did is bruteforce on the combination of appearances of the first 15 primes, finding which of those combinations gave a number of divisors greater than 8 million and taking the smallest one.

from functools import reduce
from CommonFunctions import find_primes_less_than
primes = find_primes_less_than(50)
mult = lambda x: reduce(lambda y, z: y * z, x, 1)
translate = lambda x: mult(primes[i] ** ((x[i] - 1) // 2) for i in range(len(x)))
def generator(limit):
    l = [1] * 14
    while l[13] < limit:
        i = 13
        while i > 0 and (l[i] == l[i-1]):
            l[i] = 1
            i -= 1
        l[i] += 2
        yield l
if __name__ == '__main__':
    result = min(translate(l) for l in generator(13) if mult(l) > 8000000)
    print("The result is:", result)

The Python file is available for download:

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License