Project Euler 108: Solving the Diophantine equation 1/x + 1/y = 1/n.

Let us jump right into Problem 108 of Project Euler which reads

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

For n = 4 there are exactly three distinct solutions:

What is the least value of n for which the number of distinct solutions exceeds one-thousand?

NOTE: This problem is an easier version of problem 110; it is strongly advised that you solve this one first.

We could possibly brute force, but my guess is that it would take a rather long time to do so. So instead I started fiddling around with the equation to get some insight into the problem.

Starting with the original

we can see that both x and y needs to be greater than n since they both need to be non-negative. This means that we can express the equation as

where , meaning that they are integers strictly larger than zero.

Putting this on a common denominator gives us

 So both s and r are divisors of n^2, which also means that all divisor pairs of will give us a solution to the problem. However, only half of the divisor pairs will give a unique solution since you can simply swap r and s and get a solution as well.

So if d(n) is a function giving us the number of divisors of n, we are looking for the first n such that d(n^2) / 2 > 1000.  All numbers have an even number of divisors unless is a divisor of n. In that case the number will have an odd number of divisors. I wont prove this, but I will leave it for you to figure out. In our case we have  which is also a divisor, therefore we are looking for a solution to which have (d(n^2) + 1) / 2 > 1000, where the division is an integer division.

Finding divisors

The huge task in this exercise is to actually find the smallest number with many divisors. In Problem 12 we were asked to find the number of divisors of a number. Where we established that we could use the prime factorization to find the number of divisors such that if we have the number N we have

 and then the number of divisors will be

However, we can cheat a bit so instead of factoring we will factor and the number of factors of   will then be

since we have that

This will help us significantly since it is much easier to factor a smaller number.

The algorithm I use for prime factorization requires a list of prime numbers, so I started probing around to figure out what I needed. I found that (2357111317)^2 has 2187 divisors, which is more than the 1999 we need in order to solve the problem, so we can set the upperlimit of the prime list to 17, and if a number have a prime factor larger than 17, that is not the number we are looking for anyway.

Coding the solution

I have changed the divisor counting function as described above, which resulted in  the C# code

private long NoDSquared(long number, long[] primelist) {
    long nod = 1;
    long exponent;
    long remain = number;

    for (int i = 0; i < primelist.Length; i++) {
        // In case there is a remainder this is a prime factor as well
        // The exponent of that factor is 1
        if (primelist&#91;i&#93; * primelist&#91;i&#93; > number) {
            return nod * 2;
        }

        exponent = 1;
        while (remain % primelist[i] == 0) {
            exponent+=2;
            remain = remain / primelist[i];
        }
        nod *= exponent;

        //If there is no remainder, return the count
        if (remain == 1) {
            return nod;
        }
    }
    return nod;
}

and then the main loop for the code is

long n = 1;
long result = 0;
long limit = 1000;

while (true) {
    if ((NoDSquared(n, primes) + 1) / 2 > limit) {
        result = n;
        break;
    }
    n++;
}

Nothing more to say than we should run the code which on my computer gives me the result

The first n with more than 1000 solutions is 180180

and the time

Solution took 31,0487 ms

Wrapping up

While this most certainly solved problem 108 within the time limit, it is far from fast enough for Problem 110, so we will be revisiting this problem soon enough.

You can find the complete source code here as always.