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:


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

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


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 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
    Y = X = 0;
    (a>M & b 0 & Y<0;
    X<0 & Y>0;

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