## Friday, October 5, 2012

### Number of positive integral solutions for an equation

In this post i will explain my solution for a very nice mathematical problem. If you have an account on interviewstreet, you can view it using this link EQUATIONS. However in this problem you have the following equation (1/X) + (1/Y) = 1/N! and N is given, And you have to find all the valid pairs of X, and Y that solve this problem.

One can say that the simplest way is to iterate through all possible Xs, and Ys checking the pairs that solve the equation. But what if N is equal 10^6 for example?.

First lets define M = N!, then we have:

1x+1y=1N!=1M

Lets also define that X = M+a and Y = M+b. where (a, b) could be positive or negative numbers, then we have:
2M+a+b(M+a)(M+b)=1M

We can solve the above equation and we will get the following:

2M2+M(a+b)=M2+M(a+b)+ab
M2=ab

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

So we need to know how many divisors (N!)^2 have. As you may know that the number of divisors of a number equals the result of multiplying the exponents of the prime factors of this number.
So
So if we have n = a^x * b^y * c^z, where (a, b, c) are the prime factors of n, then the number of divisors of n = (x+1)*(y+1)*(z+1), I hear you asking why?

As you can see that all the divisors of n are multipliers of the prime factors of n.

So a could be chosen (x+1) times (0, 1, 2, ... x) times,
b could be chosen (y+1) times (0, 1, 2, .... y) times,
c could be chosen (z+1) times (0, 1, 2, ... z) times.

Now you have all the ideas that make a solution, show me your skills :)

#### 1 comment:

1. I think there is some problem in here.
We are finding Y and X where Y,X >0
X=M+a; Y=M+b;
M^2=ab; so one of following will be happen
(a=b=M)
Y = X = 0;
OR
(a>M & b 0 & Y<0;
OR
(aM)
X<0 & Y>0;

in all the above cases both X & Y are never be > 0;