In this problem we are studying equations of the form...
where x,y and n are integers. For any value of n there may be multiple solutions. For example, when n = 4 we could have (8,8) or (5,20) or (6,30) as values of (x,y). This means that there are three possible solutions to the equation for n = 4.
The challenge here is to find the smallest value of n that has more than 1000 different solutions. It turns out that this is not as easy as it seems.
I started off by working out all the solutions to the n = 5 case by hand. I came up with (10,10) and (6,30). The first thing that I noticed was that the largest possible values of x and y were always going to be equal to 2n. This seemed like a good thing as it limits the candidates for x to the range 2n down to n+1.
Now that I had a range of x values to check, I thought about what values of y would go along with them to create a solution. By re-arranging the original formula I arrived at...
Since y must be an integer, we need values of x that give nx/(x - 1) = a whole number. In other words, nx % (x - 1) = 0. Since I had a limited range of x values to check I thought that it would be both quick and easy to find a solution with the following method.
1. Taking each of the integers in turn, generate values of x in the range (n + 1) to 2n
2. For each value of x, check that nx % (x - 1) = 0.
3. If step 2 is true, we have a solution to the equation.
This method works fine for small values of n. The problem is that working through the range (n + 1) to 2n for large values of n takes a very long time. To check all the n between 1000 and 1010 requires around 10,000 numbers to be checked. To go from 50,000 to 50,010 requires over half a million passes through the loop. This method starts off slow and gets progressively worse as n increases.
Inspecting my results, I saw that if n is prime then we never get more then two solutions. However, only working through composite values of n did not improve matters greatly. The price of my ignorance is endless frustration.
It was time to do some reading. From this blog I discovered that since x and y must both be larger than n we can write...
and that after some algebra this gives us...
Isn't the internet wonderful! This final result is useful because it means that the number of different solutions for each value of n depends on the number of (a,b) pairs that multiply together to give n squared. Since we only want distinct solutions (i.e. 2 × 4 = 4 × 2 and so count as a single solution) the number of solutions is equal to half of the number of possible pairs (a,b). Actually, we need to add 1 before dividing by 2 because the solution (n,n) = (a,b) isn't doubled.
The problem now was to find how many ways to solve n2 = ab. In other words, how many divisors does n2 have? The blog post that I was reading informed me that we could use the prime factorisation of n to find the answer, but I found it difficult to follow the mathematics. It was time to do some more reading.
According to this page, "If you have the prime factorisation of the number n, then to find the number of divisors it has, you take all the exponents in the factorisation, add 1 to each of them and then multiply these 'exponents + 1' together." I tried this on some small numbers.
The prime factorisation of 18 is 2, 32. So it should have 2 × 3 = 6 divisors. It does, 1,2,3,6,9,18.
I now had a better plan.
1. Take each of the composite numbers in turn as values of n
2. For each n, find the prime factorisation
3. Use the prime factorisation to find the number of solutions = [(number of divisors of n2) +1] / 2
4. If the result of step 3 is > 1000 we have the answer
At this point I stopped reading the internet because I wanted to put the code together entirely by my own efforts. As you can see, the result is an unholy mess.
I solved the problem, which is good. I was quite happy that I got the code to work. Many other people have solved this problem and their solutions are better than mine. I won't let that bother me. Low personal expectations are the key to happiness.