# Number of positive integral solutions of equation $\dfrac 1 x+ \dfrac 1 y= \dfrac 1 {n!}$

$$\dfrac 1 x+ \dfrac 1 y= \dfrac 1 {n!}$$

This is one of the popular equation to find out the number of solutions. From Google, here I found that for equation $\dfrac 1 x+ \dfrac 1 y= \dfrac 1 {n!}$, number of solutions are

$\psi(n)=\text{number of divisors of } n$.

$$\frac{\psi(n^2)+1}{2}$$

but when i turned here, it says that for equation $\dfrac 1 x+ \dfrac 1 y= \dfrac 1 {n!}$, number of solutions are $$\frac{\psi(n!^2)-1}{2}$$

However in the first link they explained the equation for $n=4$ and their formula correctly suits on that. But I want to confirm the correct answer.

If there exist any better way to get the number of positive integral solutions for the equation $\dfrac 1 x+ \dfrac 1 y= \dfrac 1 {n!}$, then please suggest me.

Would prime factorization help here? I have an algorithm to find out prime factors of any number. But not have any exact idea about implementing it over here.

My objective is to find out total number of positive integral solutions of the equation $\dfrac 1 x+ \dfrac 1 y= \dfrac 1 {n!}$.

Thank you.

-
Would $\frac{1}{4} +\frac{1}{-12} = \frac{1}{3!}$ count as a solution? –  Henry Apr 12 '12 at 22:28

Let's deal with the $N$ case before moving on to the $N!$ case

You have $\dfrac{1}{N} = \dfrac{1}{N+d} + \dfrac{1}{\frac{N^2}{d}+N}$ and you want all the denominators to be positive integers, which happens iff $d$ is a divisor of $N^2$. So the number of solutions is the number of divisors of $N^2$, but since almost all of these come in pairs, except when $d=N$, to de-duplicate you need to add $1$ and then divide by $2$ and your first link was correct.

Now moving on to the $N!$ case, if you write $N! = 2^{e_2}3^{e_3}5^{e_5}7^{e_7}11^{e_{11}}\cdots$ then the number of solutions is $\dfrac{1+ \prod_p (2e_p+1)}{2}$ where $e_p = \lfloor N/p^1 \rfloor + \lfloor N/p^2 \rfloor + \lfloor N/p^3 \rfloor + \cdots$, i.e.

$$\frac{1}{2} + \frac{1}{2} \prod_{p \text{ prime } \le N} \left(1+2 \sum_{i=1}^{\lfloor \log_p N \rfloor} \lfloor N/p^i \rfloor\right).$$

For example looking at $N!= 10!$, the answer would be $$[1 + (1+2(5+2+1))(1+2(3+1))(1+2(2))(1+2(1))]/2$$ $$=[1+ 17 \times 9 \times 5 \times 3]/2$$ $$= 1148$$

-
I got your concept, But how you write the last expression while explaining N!=10! . I understand your formula. but i didn't understand [1+(1+2(5+2+1))(1+2(3+1))(1+2(2))(1+2(1))]/2. I want to ask that is it necessary to compute N!? what i did is 10!=3628800=2^8*3^4*5^2*7^1. now (1+((2*8+1)(2*4+1)(2*2+1)(2*1+1)))/2=1148 –  Ravi Joshi Apr 13 '12 at 6:42
I did not explicitly work out $10!$ and then factorise it. So instead of finding eight factors of $2$ directly, I worked out $\lfloor 10/2 \rfloor + \lfloor 10/4 \rfloor + \lfloor 10/8 \rfloor = \lfloor 5 \rfloor + \lfloor 2.5 \rfloor + \lfloor 1.25 \rfloor = 5+2+1 = 8$. –  Henry Apr 13 '12 at 7:57
Correct me if i am wrong. So there is no need to calculate N!. I have to just find prime factorization of N, which are p1, p2, p3... then I can apply your formula, which uses ∑ . –  Ravi Joshi Apr 13 '12 at 12:15
Not quite: my formula calculates the prime factorisation of $N!$ without calculating $N!$. But knowing $10=2 \times 5$ does not help much for $10!$. –  Henry Apr 13 '12 at 12:29
$\lfloor 10/2 \rfloor + \lfloor 10/4 \rfloor + \lfloor 10/8 \rfloor = \lfloor 5 \rfloor + \lfloor 2.5 \rfloor + \lfloor 1.25 \rfloor = 5+2+1 = 8$, $\lfloor 10/3 \rfloor + \lfloor 10/9 \rfloor = \lfloor 3.33\ldots \rfloor + \lfloor 1.11\ldots \rfloor = 3+1 = 4$, $\lfloor 10/5 \rfloor = \lfloor 2 \rfloor = 2$, and $\lfloor 10/7 \rfloor = \lfloor 1.42\ldots \rfloor = 1$, but I did not calculate $10!$ explicitly. –  Henry Apr 13 '12 at 18:44

If we let $N! = M$,

$$\frac{1}{x}+\frac{1}{y} = \frac{1}{N!} = \frac{1}{M}$$

Let $x=M+a$ and $y=M+b$ where $a$ and $b$ are integers (positive or negative)

$$\Rightarrow \frac{2M+a+b}{(M+a)(M+b)} = \frac{1}{M}$$

$$2M^2+M(a+b) = M^2+M(a+b)+ab$$

$$\Rightarrow M^2 = ab$$

Now look at all the divisors of $M^2 = (N!)^2$ and find the values of $a$ and $b$ and hence find the values of $x$ and $y$.

It will be easier if you pick an example such as

$$\frac{1}{x}+\frac{1}{y} = \frac{1}{3!} = \frac{1}{6} \tag{1}$$

and show that

$$\fbox{(7, 42), (8, 24), (9, 18), (10, 15), (12, 12), (15, 10), (18, 9), (24, 8),(42, 7),(5,-30),}\\ \fbox{(4,-12),(3,-6), (2, -3), (-3, 2), (-6, 3), (-12, 4), (-30, 5)}$$

are $(x,y)$ pairs that satisfy $(1)$, which when counted are $17$ pairs.

Hint: The number of divisors of $36=6^2 = d(6^2) = 9$, and they are $1,2,3,4,6,9,12,18, 36$.

What is the relationship between $d(6^2)$ and the number of solutions?

Note: I am just giving you an approach. It was not explicitly mentioned that $(x,y)$ pairs have to be positive. If that is the case, then you have to only consider positive pairs. (Henry rightly pointed out that it should be clear whether you are looking for only positive integer solutions).

-
You have negative $x$ and $y$, and I am not sure that was intended by the original question. –  Henry Apr 12 '12 at 22:16
@Henry, thanks. You are right. I assumed integer solutions (positive and negative). However, I did not give a complete solution. That was just an approach to solve it. –  Kirthi Raman Apr 13 '12 at 0:42
@KVRaman: Ya. i am interested in positive integral solutions of the equation. In that case, i have to neglect all the negative solutions, which are 7 in this case. But how? –  Ravi Joshi Apr 13 '12 at 5:56
@KVRaman: Thanks man. Your explanation is very cool. i get the logic now. thank you. –  Ravi Joshi Apr 13 '12 at 6:31