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

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

Written by on 4 August 2012

Topics: Project Euler

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

In the following equation xy, 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 (2*3*5*7*11*13*17)^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[i] * primelist[i] > 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.

4 Comments For This Post I'd Love to Hear Yours!

  1. Eman says:

    Hello, nice solution I solved this on the third or fourth try. I used this approach: I found the the number we are looking for must be very composite (lot of factors) so I made some test, some tries and finally found solution.

    P.S this is very stupid factorization metod but it was from my beginings

    #include 
    #include 
    #include 
    
    using namespace std;
    
    const int MAX_SOLUTIONS = 1000;
    typedef unsigned long long Long;
    int getSolutions(Long n);
    
    int main()
    {
    
        time_t start = clock();
    
        int solutions = 0;
        Long n=2*3*5*7*11*13;
        Long x = 2*3*5*7*11*13;
        
        while(solutions <= MAX_SOLUTIONS)
        {
    
            solutions = getSolutions(n);
            //cout<<n<<'\t'<<solutions<<endl;
            //cin.get();
              n+=x;
        }
    
        cout<< "Project Euler 108:\t"<<n - x<<"\t"<<solutions<<endl;
        cou<<"PROGRAM LAST:\t"<<(clock() - start)"<< ms."<<endl;
    
    
    }
    
    int getSolutions(Long  n)
    {
    
        Long maxX = 2*n;
        register int solutions=0;
        Long differ;
        long double y;
        Long x;
    
        for(x = n+1; x<=maxX; x++)
        {
            differ = x-n;
            
                y = (x*n)/(long double)differ;
                //if(y < x)
                   // return solutions;
                if((Long)y == y)
                {
                    solutions++;
                   // cout<<x<<"\t"<<y<<"\t"<<differ<<endl;
                    
                }
    
        }
        
      
    
        return solutions;
    
    }
    
    
  2. robert says:

    Your pages show very well with the MathML. I wonder whether you ca let me know what sort of software that you are using to get the Math symbols right. Thanks.

  3. Kristian says:

    Hi Robert

    I use wordpress as you probably have figured out and to render the math I use the optimized latex plugin

  4. Ralf says:

    How would you solve Diophantine equation a*c1+b*c2+c*c3+d*c4+…+i*c9=n?

Leave a Comment Here's Your Chance to Be Heard!

You can use these html tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

You can use short tags like: [code language="language"][/code]

The code tag supports the following languages: as3, bash, coldfusion, c, cpp, csharp, css, delphi, diff,erlang, groovy, javascript, java, javafx, perl, php, plain, powershell, python, ruby, scala, sql, tex, vb, xml

You can use [latex]your formula[/latex] if you want to format something using latex

Notify me of comments via e-mail. You can also subscribe without commenting.