Diophantine Reciprocals II

In the following equation $x$, $y$, and $n$ are positive integers.
$$\dfrac{1}{x} + \dfrac{1}{y} = \dfrac{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?
NOTE: This problem is a much more difficult version of Problem 108 and as it is well beyond the limitations of a brute force approach it requires a clever implementation.

Based on the equation, we can transform the equation to xy = n(x+y). This is a fairly normal Diophantine equation, which deals with integer solutions to polynomial equations.

To find the value of n which has more than 4 million solutions, here the solutions refer to pairs of (x, y).

We observe that for each value of x > n, there must be a corresponding value of y <= n. We know that x*y = n*(x+y), meaning if x is significantly larger than n, y must be quite close to n.

In other words, for every x = n + k, there is a corresponding y = n/(1 + n/k). Since x and y are integers, the number of solutions can be determined by the number of divisors of n squared.

This is because n must be able to be divided by k and n + k (they are the two dimensions of the rectangle, if you think in terms of geometry) to have a valid integer solution.

For a number to have a higher count of divisors, it must be factored by a lot of small prime numbers, because the number of divisors of n, d(n) is determined by its prime factors.

If the prime factorization of n is of the form p1^i * p2^j * p3^k …, then d(n) = (i+1)(j+1)(k+1)… To maximize the number of divisors, we must factorize it with as many small prime numbers as possible.

This means we want the factored form to be something like 2^i * 3^j * 5^k * 7^l * 11^m * 13^n… where i >= j >= k >= l >= m >= n …

Now we want to find the least n for which d(n^2) > 4000000. If p1, p2, … are sorted primes and n = p1^a1 * p2^a2 * …, then say b1 = 2a1 + 1, b2 = 2a2 + 1, …, the number of solutions of x,y pairs is given by ((b1+1)(b2+1)(b3+1)…-1)/2.

And we want ((b1+1)(b2+1)(b3+1)…-1)/2 > 4000000.

From this, we can calculate that a1 = 39, a2 = 19, a3 = 9, a4 = 6, a5 = 4, a6 = 4 is the first solution to make it exceed 4 million, so the prime factorization of n is: 2^39 * 3^19 * 5^9 * 7^6 * 11^4 * 13^4. multiplying this out gives the least n to be 9350130049860600.

More Answers: