# Number of solutions for $\frac{1}{X} + \frac{1}{Y} = \frac{1}{N!}$ where $1 \leq N \leq 10^6$

Note: this is a programming challenge at this site

For this equation $$\frac{1}{X} + \frac{1}{Y} = \frac{1}{N!}\quad ( N \text{ factorial} ),$$ find the number of positive integral solutions for $(X,Y)$ ?

Note that : $1 \leq N \leq 10^6$.

• Welcome to math.SE: since you are new, I wanted to let you know a few things about the site. In order to get the best possible answers, it is helpful if you say in what context you encountered the problem, and what your thoughts on it are; this will prevent people from telling you things you already know, and help them give their answers at the right level. – Julian Kuelshammer Nov 8 '12 at 19:09
• @Xiba: thank you for pointing out the fact that this is a programming challenge. This should be a comment instead of an edit, but I see you don't have the reputation to leave a comment. I accepted your edit (giving you 2 rep) and then rolled back as the best solution to the situation. – Ross Millikan Nov 20 '12 at 4:27
• Thanks to Xiba, who informs us that this is a programming challenge at interviewstreet.com/challenges/dashboard/#problem/4e14a0058572a – Ross Millikan Nov 20 '12 at 4:27
• @Ross, does that mean we shouldn't be answering it? – Gerry Myerson Nov 20 '12 at 4:30
• @GerryMyerson: this was discussed at meta.math.stackexchange.com/questions/4004/… I'm not sure this site is really a contest, but I would avoid answering. – Ross Millikan Nov 20 '12 at 4:35

Equivalently, we want to solve $N!(X+Y)=XY$, which can be rewritten as $$(X-N!)(Y-N!)=(N!)^2.$$

Note that $X\gt N!$ and $Y\gt N!$. For if, for example, $X\lt N!$, then since $X$ and $Y$ are positive, we have $\dfrac{1}{X}+\dfrac{1}{Y} \ge \dfrac{1}{N!}+\dfrac{1}{Y}\gt \dfrac{1}{N!}$.

Now let $s=X-N!$ and $t=Y-N!$. To count the solutions of our original equation, we count the number of solutions of $st=(N!)^2$.

To do this, note that $s$ ranges over the divisors of $(N!)^2$, and that once we know $s$, we know $t$, and therefore $X$ and $Y$.

Thus the number of solutions of our equation is the number $d((N!)^2)$ of (positive) divisors of $(N!)^2$.

That still leaves a great deal of work to do. There is a simple formula for the number of divisors of $n$, once we know the structure of the prime power factorization of $n$. However, there is no simple expression for the structure of the prime power factorization of $(N!)^2$.

However, the problem is not computationally hopeless. For any prime $p$, the highest power of $p$ that divides $N!$ is $$\lfloor N/p\rfloor+\lfloor N/p^2\rfloor+\lfloor N/p^3\rfloor+ \lfloor N/p^4\rfloor+\cdots,$$ and for $(N!)^2$ we just double. The sum above is a finite sum, indeed a rather short sum, since the terms $p^i$ in the denominator grow exponentially, and soon surpass $N$.

Remark: For completeness, so that you can begin to build a program, suppose that $n$ has prime power factorization $$p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k},$$ where the $p_i$ are distinct primes. Then the number of positive divisors of $n$ is $$(a_1+1)(a_2+1)\cdots(a_k+1).$$

Some things to try:

Because of the symmetry, you can insist $X \le Y$ then double the ones where $X \ne Y$. $X$ can't be too large-what is the maximum? Try by hand a small case or two: $N=1,2,3$. You might see a pattern For Diaphontine equations, thinking about divisibility of the numbers is often productive.

For example, for $N=1$, $X$ can't be larger than $2$ or $\frac 1X+\frac 1Y \lt 1$. It also can't be $1$ or the sum is too large. Then check that $X=Y=2$ works. We have shown it is the only solution.

For the equation:

$\frac{1}{X}+\frac{1}{Y}=\frac{1}{A}$

You can write a simple solution if the number on the decomposition factors as follows:

$A=(k-t)(k+t)$

then:

$X=2k(k+t)$

$Y=2k(k-t)$

or:

$X=2t(k-t)$

$Y=-2t(k+t)$