Egyptian Fractions
During the Middle Kingdom of Egypt, 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 1 / n (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 m / n, where m > 1. Instead, any such fraction was written as the sum of unit fractions. For example, the fraction 3 / 4 could be written as:
Notice that multiple sums may yield the same result; for example, can also be written as
Your job is to take a fraction 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 . A greedy search would find the sum in three steps, like so:
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 . The first two unit fractions we would subtract would be and , leaving us with . At this point, the largest unit fraction we could subtract would be , leaving us with
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, , which leaves us with
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 .
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^12. 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:
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 . 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 you are to output a single line containing numbers D[1] ≤ D[2] ≤ D[3] ≤ … such that:
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.