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:
Minimal Network
Diophantine Reciprocals I
Darts

Error 403 The request cannot be completed because you have exceeded your quota. : quotaExceeded

Share:

Recent Posts

Mathematics in Cancer Treatment

How Mathematics is Transforming Cancer Treatment Mathematics plays an increasingly vital role in the fight against cancer mesothelioma. From optimizing drug delivery systems to personalizing

Read More »