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

In the following equationx,y, andnare positive integers.

Forn= 4 there are exactly three distinct solutions:

What is the least value ofnfor 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.

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

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.

Hi Robert

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

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