Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

Algorithm to Print Sums of Inverses

Date: 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/ 
Associated Topics:
College Number Theory

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/