Problem I: Egyptian Fractions

During the Middle Kingdom of Egypt (circa 2000 BC), the Egyptians developed a novel way of writing fractions. Adding a certain symbol to the hieroglyph for an integer was understood to represent the reciprocal of that integer. This made it easy to write any fraction of the form 1N (called a unit fraction)—simply add the reciprocal symbol to the hieroglyph for N.

There was no direct way to represent a fraction of the form MN, where M > 1. Instead, any such fraction was written as the sum of unit fractions. For example, the fraction 34 could be written as:

34 = 12 + 14

Notice that multiple sums may yield the same result; for example, 34 can also be written as

34 = 13 + 14 + 16

Your job is to take a fraction MN and write it as a sum of unit fractions by way of a “greedy” search. In a greedy search you continually subtract the largest unit fraction possible until you are left with zero. For example, consider the fraction 920. A greedy search would find the sum 13 + 19 + 1180 in three steps, like so:

(1.) 920 - 13 = 760,  (2.) 760 - 19 = 1180,  (3.) 1180 - 1180 = 0

Note that at each step we subtracted the largest possible unit fraction from whatever remained of our original fraction.

One additional restriction must be added to keep our solutions from becoming too large: Each time we subtract a unit fraction, we must be left with a fraction whose denominator is strictly less than 1,000,000. For example, consider the fraction 1769. The first two unit fractions we would subtract would be 15 and 122, leaving us with 77590. At this point, the largest unit fraction we could subtract would be 11085, leaving us with

77590 - 11085 = 15191647030 - 15181647030 = 11647030

Unfortunately, this leaves us with a fraction whose denominator is larger than 1,000,000, so we can not use this unit fraction in our sum. We move on to the next largest unit fraction, 11086, which leaves us with

77590 - 11086 = 12671373790 - 12651373790 = 21373790 = 1686895

Since the final answer reduces to a fraction with a denominator less than 1,000,000, we can use this unit fraction, leaving us with a final answer of 15 + 122 + 11086 + 1686895.

In this case we only had to skip over a single fraction. In general, however, you may have to skip over many fractions in order to find one that will work. While you are searching, you will have to perform calculations on many fractions with large denominators; make sure you do so efficiently, or your program may take too long to execute.

You should also make sure you are using a data type large enough to hold the large numbers you are working with. Even though we have restricted denominators to 1,000,000, you may have to calculate intermediate values with denominators up to 10¹². A 64-bit integer will be required to hold such values (long in Java, long long in C/C++).

Finally, it might be worth noting that, by its very nature, the greedy algorithm will always find some answer consisting of fractions with denominators less than 1,000,000 since, at the very least, any fraction can be represented as a sum of unit fractions with its own denominator. For example:

3999983 = 1999983 + 1999983 + 1999983

Input:  The input will consist of a sequence of fractions; one per line. Each line will contain only two integers M and N, where 1 < M < N < 100, representing the fraction MN.  M and N will have no common divisors greater than 1. The end of the input will be indicated by two zeros: 0 0.

Output:  For each input fraction MN you are to output a single line containing numbers D₁ ≤ D₂ ≤ D₃ ≤ … such that:

MN = 1D₁ + 1D₂ + 1D₃ + …

This should be the first sum arrived at using a greedy search while enforcing the denominator bound of 1,000,000. Each number should be separated by a single space, with no leading or trailing whitespace.