Algorithm to Print Sums of InversesDate: 09/29/2004 at 10:04:36 From: Endri Subject: number theory and algorithms Prove that any number n > 32 can be written in the form n = m_1 + m_2 + ... + m_k such that the sum of the inverses of m_i is 1: 1/m_1 + ... + 1/m_k = 1. Assume we proved it. But my real question is how can I find an algorithm that prints all the possible m_i's for a given number n? If you could help me with some tricks that I need to know from number theory... Date: 10/21/2004 at 15:08:49 From: Doctor Vogler Subject: Re: number theory and algorithms Hi Endri, Thanks for writing to Dr. Math. You've asked a very interesting question. Allow me to answer it. First of all, I am assuming that the m_i numbers must be positive integers, and that n is also a positive integer. Now, an easy but not very smart algorithm is this: Clearly k must be no bigger than n since m_i is at least 1. And clearly m_i must be no bigger than n. So, we just run some big loop that tries every value from 1 to n (inclusive) for k and m_1 through m_n, and for each value checks if the two equations are satisfied. Of course, this takes n^(n+1) time, which is not very impressive; it will take a very long time when n is not really really small. So the first speed-up we can do, which will make the thing run about n! times faster, is to notice that the order of the m_i numbers doesn't really matter, so we should assume that they are sorted. In other words, count m_1 from 1 to n, and then count m_2 from 1 to m_1, and count m_3 from 1 to m_2, and so on. To be a little smarter, we can look for solutions to the first equation (sum to n) and check the second equation for each one. But we don't even have to count k; we can just let it be the number of m's that we end up with (but we know it will never be bigger than n, which allows us to give a size to our m array). So first we will assume that m_1 >= m_2 >= m_3 >= ... >= m_k. So we count m_1 from 1 up to n. Then we start m_2 at 1, and we can certainly stop if we get to m_1, but we can also stop if we get to n-m_1. Similarly, each m_i counts from 1 up to the smaller of the two values m_(i-1) and n - (m_1 + m_2 + ... + m_(i-1)). Furthermore, for each of these values you need to go on to the next m_i and start it counting EXCEPT for the last value when it is n - (m_1 + m_2 + ... + m_(i-1)). If m_i is this value, then the sum m_1 + m_2 + ... + m_i = n so we have a solution to the first equation with k=i. There will be many of these, and for each we check the sum of the reciprocals 1/m_1 + 1/m_2 + ... + 1/m_i and see if we get 1. This is much faster than the previous two methods. It can also be sped up by checking 1/m_1 + 1/m_2 + ... + 1/m_i every time we pick an m_i value. If ever this sum is bigger than 1, then we can skip that m_i value. Finally, there are actually quite a bit fewer solutions to 1/m_1 + 1/m_2 + ... + 1/m_k = 1 than to the other equation, so we can do better by solving this equation first. Now the smaller m values will contribute larger amounts to the sum, so now we should reverse the sorting of the m's, so that 1 <= m_1 <= m_2 <= m_3 <= ... <= m_k. Now we first let m_1 count from 1 up to n. For each m_1, we let m_2 count, but we start at m_1 and count up to n-m_1, and so on. Each time we choose an m_i value, we look at the sum s = 1/m_1 + 1/m_2 + ... + 1/m_i. If this sum is bigger than 1, then we throw away that m_i value, because it can't work. If the sum equals 1, then we add up the m_i values and see if they sum to n. If the sum is smaller than 1, then we know that there is at least one more m value, and 1/m_(i+1) <= 1/m_(i+1) + ... + 1/m_k = 1 - s which means that m_(i+1) >= 1/(1 - s). If this number 1/(1-s) is bigger than n, or bigger than n - (m_1 + m_2 + ... + m_i), then there are no more solutions. If this number is bigger than m_i, then we start counting there instead of m_i. Does this algorithm make sense to you? I think it will be a lot faster than the previous ones. Just for fun, I thought I'd write up some code for you. This is C code, and I use s = 1/m_1 + 1/m_2 + ... + 1/m_i, and t = m_1 + m_2 + ... + m_i. // n is known here // m is an array of dimension at least n+1 // i, j, n, t, and m[i] are integers, s is real // initialize i = 1; m[1] = 1; t = 1; s = 1.0; for ( ; i > 0 ; ) { // main loop if ((t == n) && (s > 0.9999) && (s < 1.0001)) { // note that s == 1.0 for "real" data is dangerous, // due to round-off error // print a solution for (j=1; j<=i; j++) printf("%d ", m[j]); printf("\n"); } if (t >= n){ // we've checked all values for this m[i] - go back to i = i-1 t -= m[i]; s -= 1.0/m[i]; i--; // next m[i] s -= 1.0/m[i]; m[i]++; s += 1.0/m[i]; t++; } else if (s > 0.9999){ // again, > 1.0 is slightly dangerous // next m[i] s -= 1.0/m[i]; m[i]++; s += 1.0/m[i]; t++; } else { // t < n, and s < 1.0, so go up to i = i + 1 i++; if (1.0/(1.0-s) > m[i-1]) m[i] = 1.0/(1.0-s); // you can round up, but be careful else // about precision near integer values m[i] = m[i-1]; s += 1.0/m[i]; t += m[i]; } } 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/