Number of positive integral solutions of equation 1/x+1/y=1/n!

Revision en2, by Vivek.p, 2020-05-03 16:46:53

Recently, i was solving some mathematical problems from the Hackerrank math's section, And i came up with this formula :

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

The question was find the number of positive integral solutions for $\dfrac{1}{x}+\dfrac{1}{y}=\dfrac{1}{n!}$ equation. You can find the problem here.

My solution :

$\dfrac{1}{x}+\dfrac{1}{y}=\dfrac{1}{n!}$ , Consider N = n!.

Now,the equation,

$\dfrac{1}{x}+\dfrac{1}{y}=\dfrac{1}{N}$

∴ $\dfrac{x+y}{xy} = \dfrac{1}{N}$

∴ $N( {x + y} ) = xy$

∴ ${xy - N({x+y})} = 0$

Now adding both sides with N^2 :

${xy - N( {x + y}) + N^2} = N^2$

∴ ${xy - Nx - Ny + N^2} = N^2$

∴ ${x({y - N}) - N ({y - N })} = N^2$

∴ $({x - N}) ({y - N}) = N^2$

From this equation we know that number solution will be the number of divisiors of N.

That means we only need to find number of divisors of $n!^2$.

1. Now one way is find value of $n!^2$ and find the number of divisors of them.But for less time complexity we can find number of divisiors $n!^2$ by Legendre's formula.
2. For that,

• Find all prime numbers less than equals to $n$.Let say prime numbers less than equals to $n$ : [p,p1,p2,...]
• For each prime number p find the largest power of it that divides $n!$. We use below Legendre's formula for this purpose.

The value of largest power that divides p is $⌊n/p⌋ + ⌊n/(p1)⌋ + ⌊n/(p2)⌋ + ...$

• Let these largest powers are : [e,e1,e2,...]
• So, for number of divisors of $n!$ the result is ${({e + 1}) * ({e1 + 1}) * ({e2 + 1}) ...}$ .
• And for $n!^2$ the result will be : ${({2*e + 1}) * ({2*e1 + 1}) * ({2*e2 + 1}) ...}$.

And that is the answer we are looking for.

For example, lets take $n=4$, $n! = 24$ and $(n!)^2 = 576$.

$24 = 2^3 * 3^1$

Hence no. of factors $= (3+1) * (1+1) = 8$, which are : [1,2,3,4,6,8,12,24].

For $576 = 2^6 * 3^2$,

it is $(2*3 + 1) * (2*1 + 1) = 21$;

Hence for $\dfrac{1}{x}+\dfrac{1}{y}=\dfrac{1}{4!}$ this equation total number of positive integral solution are $21$.

So, that was my answer for the question,Correct me if i am wrong.

Here is more information about finding divisors of $n!$.

History

Revisions

Rev. Lang. By When Δ Comment
en2 Vivek.p 2020-05-03 16:46:53 11 Tiny change: '0$\n\nNow multiplying both s' -> '0$\n\nNow adding both s'
en1 Vivek.p 2020-05-03 14:25:14 2688 Initial revision (published)