11
$\begingroup$

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

  • 0
    Would $\frac{1}{4} +\frac{1}{-12} = \frac{1}{3!}$ count as a solution?2012-04-12
  • 0
    @Henry *Positive integral* solutions.2017-03-16

2 Answers 2

9

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

  • 0
    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`2012-04-13
  • 0
    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$.2012-04-13
  • 0
    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 `∑` .2012-04-13
  • 0
    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!$.2012-04-13
  • 0
    Okay. For `p1=2` you calculated `∑` from `i=1` to `i=log2(10)`, which gives you 8. For `p2=3` you calculated `∑` from `i=1` to `i=log3(10)`, which gives 4 and so on.... Is it correct?2012-04-13
  • 0
    Yes. You could extend the sum further but all you would get is zeros to add into the sum2012-04-13
  • 0
    Here comes a doubt. `p1`, `p2`, `p3`... are the prime factors of N. Correct?2012-04-13
  • 0
    No. $p$ is a prime (less than or equal to $N$) and $p^2$ is its square, $p^3$ is its cube, etc.2012-04-13
  • 0
    I am sorry man, can you explain me in detail. Actually i got your first formula, which has `∏`. Using this formula, i am getting the same ans as you are getting. `10!=3628800=2^8*3^4*5^2*7^1`. According to the first formula ans is `(1+((2*8+1)(2*4+1)(2*2+1)(2*1+1)))/2=1148`. This is correct but in the second formula, as mention by you, one need not to calculate 10!. This idea impressed me but i still don't know, how exactly you are getting `1148` without even calculating 10!. Please explain. Sorry for extending the discussion in comments.2012-04-13
  • 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.2012-04-13
  • 0
    Ohhhhhhh......... Excellent. The idea is to divide the number `n` with `p^i`, until we get 1. Here `p` is a prime number less than or equal to `n` and `i` is a positive integer number. Simply Awesome.2012-04-13
13

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).

  • 0
    You have negative $x$ and $y$, and I am not sure that was intended by the original question.2012-04-12
  • 0
    @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.2012-04-13
  • 0
    @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?2012-04-13
  • 0
    @KVRaman: Thanks man. Your explanation is very cool. i get the logic now. thank you.2012-04-13