Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

$$\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.

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

2 Answers 2

up vote 7 down vote accepted

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$$

share|improve this answer
    
Mathematics is just a fun until you guys are here. It's my pleasure that i got the solution with wonderful explanation. Thanks a ton. –  Ravi Joshi Apr 13 '12 at 6:37
    
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
1  
$\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).

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.