Finding the Number of Solutions and Factors

Date: 06/08/2007 at 17:45:55
From: Jean
Subject: How to Find the Number of Solutions and Upper Bounds

Suppose you have this equation:

(10^n / x) + (10^n / y) - z = 0

If x <= y, how do you find the number of positive integer solutions
for a given value of n?

I can solve the equation by using a computer program to brute force
solutions.  But this is not satisfying.  Is there a way to find out
how many solutions there are for a given value of n so that I know
when to stop the computer?  Also, how do I find the upper bounds for
values of y so I can test within a range?
 
Here's what I am thinking...it could be wildly wrong:

- The lower bound on x, y and z is 1
- The upper bound on x is y
- The upper bound on y is ???
- The upper bound on z is defined when you plug in x = y = 1
- The exact value of z is irrelevant because as long as the x + y is
  an integer, the problem is solved
- The solution appears to be tied to divisors of y and their
  multiples. 

The reason I say this is because all the solutions that I have found
feature y as a multiple of a divisor of the coefficient of y.  And all
the resulting x values from those solutions are multiples of divisors
of y.

For instance, if n=1, then a solution is x=3, y=15, z=4.  15 is
divisible by 5, which is a divisor of 10, and 3 is a divisor of
15.  There appears to be a pattern, but I cannot divine it.

The problem is, when n=5, how do I know how many solutions it has?
And, how do I establish an upper bound on y so that I search for the
solutions efficiently?  Right now, I just let the program run until it
doesn't find anything 'for a while'. 

I hate the brute force program.  It produces solutions, but does not
solve the equation.  Plus, its ugly.  Math is supposed to be elegant,
so if you have time, please help me understand what is happening here.

Date: 06/11/2007 at 17:37:21
From: Doctor Vogler
Subject: Re: How to Find the Number of Solutions and Upper Bounds

Hi Jean,

Thanks for writing to Dr. Math.  Unfortunately, math is not always 
elegant.  We love it when it is, and we like to teach those cases, 
but frequently we run into problems whose solutions are far from 
elegant, especially when they are problems from the real world, 
rather than from a textbook.

That aside, there is much to be observed in your problem.  First of 
all, I'd really like to answer the question:  For which pairs of 
positive integers (x, y) is the sum

  1/x + 1/y

some integer divided by some power of 10 (or, we might say, is a 
terminating decimal, which is the same thing).

It turns out that the answer to this question is fairly elegant, 
although counting the number of solutions is still not completely 
trivial (better than brute-force, however).  Consider:

If (x, y, z) is one solution to your equation, for a particular value 
of n, and if g divides z, then (gx, gy, z/g) is another solution, for 
the same value of n.

Therefore, if you find some solution, such as (1, 5, 12) for n=1, 
then you can take any divisor g of 12 (namely 1, 2, 3, 4, 6, or 12) 
such as g=3, then you can get another solution (3*1, 3*5, 12/3), 
which is the solution you described.

And it works in the other direction too.  If x and y have a common 
factor g, then the solution (x, y, z) comes from another integer 
solution (x/g, y/g, gz).  So if we could find all solutions where x 
and y have no common factors, then we could get from that to all 
integer solutions.  In fact, we can count the number of solutions 
that it will lead us to using the formula in the following article, 
since there is one solution for each factor of z.

  How Many Factors?
    http://mathforum.org/library/drmath/view/54227.html 

Now, consider this.  Suppose that some prime number p divides x, and 
p is neither 2 nor 5.  Then (rewriting your equation)

  xyz = (10^n)(x + y),

and the left side is divisible by p, so that means that some factor 
on the right side must be divisible by p.  It can't be 10^n, so it 
must be x + y.  But since x is divisible by p, that means that y must 
be divisible by p.

The same argument proves that if p divides y, then p must divide x.  
That means that any prime factor other than 2 or 5 divides neither x 
nor y, or it divides both.  So if x and y have no common factors, 
then that means that each can only be divisible by powers of 2 or 5.  
That means that either one of them is a power of 2 and the other a 
power of 5, or one of them is 1, and the other is some power of 2 
times some power of 5.

In other words, x divides 10^n for some n and y divides 10^n for some 
n, so 1/x and 1/y are both terminating decimals, and therefore their 
sum 1/x + 1/y is also a terminating decimal.

Of course, when you choose n from the start, then you have to be more 
careful, because you might find that x divides 10^n and y divides 
10^n, but 1/x + 1/y is an integer divided by 10^(n-1).

So, if we suppose that 10^n/x and 10^n/y sum to an integer, then each 
of those two fractions is a power of two times a power of five 
(possibly negative powers of two/five), and they have to have the 
same denominator (since an integer minus 10^n/y has the same 
denominator as 10^n/y).  But that would mean that the same power of 2 
or 5 larger than n divides both x and y, which means that they have a 
common factor.  So those will come from extra factors of 2 or 5 
coming from the transformation (x, y, z) -> (gx, gy, z/g).

Therefore, you can count the number of solutions as follows:

(1) First list off each solution where gcd(x, y) = 1.  They are:
    (a) x = 2^i, y = 5^j, 1 <= i <= n and 1 <= j <= n
    (b) x = 1, y = 2^i * 5^j, 0 <= i <= n and 0 <= j <= n

(2) For each such solution, compute z = (10^n)(1/x + 1/y), and 
    compute the number of factors of z from the formula at

  How Many Factors?
    http://mathforum.org/library/drmath/view/54227.html 

(3) Sum up all of the number of factors.

And that ought to do it (if I haven't made any mistakes in all this).

If you have any questions about this or need more help, please write 
back and show me what you have been able to do, and I will try to 
offer further suggestions.

- Doctor Vogler, The Math Forum
  http://mathforum.org/dr.math/ 

Date: 06/11/2007 at 17:43:45
From: Jean
Subject: Thank you (How to Find the Number of Solutions and Upper Bounds)

Thank you SOOO much!  This made it very clear.  I implemented the
solution that you described, and it works perfectly.  For example,
when I solve it for n = 2, I get 102 solutions, which is correct as
verified by my computer program.

When I complete the steps (1) and (2) below for n = 2, I get the
following:

  2,5   =  70 (factors =  8)
  2,25  =  54 (factors =  8)
  4,5   =  45 (factors =  6)
  4,25  =  29 (factors =  2)
  1,1   = 200 (factors = 12)
  1,5   = 120 (factors = 16)
  1,25  = 104 (factors =  8)
  1,2   = 150 (factors = 12)
  1,10  = 110 (factors =  8)
  1,50  = 102 (factors =  8)
  1,4   = 125 (factors =  4)
  1,20  = 105 (factors =  8)
  1,100 = 101 (factors =  2)

When I sum them per step (3), I get 102.  Beautiful!  I appreciate
your time and help tremendously!!!! 

Mahalos :)

- Jean