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
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994-2013 The Math Forum