In the following equation $x$, $y$, and $n$ are positive integers.
$$\dfrac{1}{x} + \dfrac{1}{y} = \dfrac{1}{n}$$
For $n = 4$ there are exactly three distinct solutions:
$$\begin{align}
\dfrac{1}{5} + \dfrac{1}{20} &= \dfrac{1}{4}\\
\dfrac{1}{6} + \dfrac{1}{12} &= \dfrac{1}{4}\\
\dfrac{1}{8} + \dfrac{1}{8} &= \dfrac{1}{4}
\end{align}
$$
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.
This is an algebra problem that involves diophantine equations.
The given equation is a particular case of the general diophantine equation known as the equation of friendly pairs:
$\dfrac{1}{x} + \dfrac{1}{y} = \dfrac{1}{n}$
If we rewrite it, we get:
$yx = n(x+y)$
And further simplified to:
$yx-nx = ny$
This is equivalent to:
$x(y-n) = ny$
Here the positive integer solutions (x, y) are dependent on the positive integer divisors of $n^2$. Note that x must be greater than n.
Let’s denote d as a divisor of $n^2$; then, x can be represented as:
$x = \dfrac{n^2}{d} + d$
Where d can take any value from n+1 to $\sqrt{n^2}$ (inclusive).
The number of solutions is hence equal to half the number of divisors of $n^2$.
Therefore, to find the least value of n, we need to find the least integer whose square has over 2000 divisors (since 2*1000=2000, and we need over 1000 solutions).
A number $n$ = $p_1^{k_1}*p_2^{k_2}*…*p_n^{k_n}$ (p’s are prime divisors) has $(k_1 + 1)*(k_2 + 1)*…*(k_n + 1)$ divisors. For square number n^2, the number of its divisors is $(2*k_1 + 1)*(2*k_2 + 1)*…*(2*k_n + 1)$.
From this, we want to find the smallest $n$ such that $(2*k_1 + 1)*(2*k_2 + 1)*…*(2*k_n + 1) > 2000$.
The product is maximized when $k_1 >= k_2 >= … >= k_n$.
Start with first few prime numbers (2, 3, 5, 7…) and assign them power starting from 1. So, The smallest such $n$ is $2^3 * 3^2 * 5^1 * 7^1 * 11^0 * 13^0 … = 2^3 * 3^2 * 5 * 7 = 2520$.
Therefore, the least value of $n$ for which the number of distinct solutions exceeds one-thousand is 2520.
More Answers:
Special Subset Sums: TestingSpecial Subset Sums: Meta-testing
Minimal Network