Addition Chains

Time Limit: 2 Seconds
Memory Limit: 65536 KB
Special Judge

An addition chain for n is an integer sequence <a0, a1,a2,...,am> with
the following four properties:

- a0 = 1
- am = n
- a0 < a1 < a2 < ... < am-1 < am
- For each k (1 <= k <= m) there exist two (not necessarily different)
integers i and j (0 <= i, j <= k-1) with ak = ai + aj

You are given an integer n. Your job is to construct an addition chain for
n with minimal length. If there is more than one such sequence, any one is acceptable.

For example, <1, 2, 3, 5> and <1, 2, 4, 5> are both valid solutions
when you are asked for an addition chain for 5.

**Input**

The input will contain one or more test cases. Each test case consists of one
line containing one integer n (1 <= n <= 100). Input is terminated by
a value of zero (0) for n.

**Output**

For each test case, print one line containing the required integer sequence.
Separate the numbers by one blank.

**Sample Input**

5

7

12

15

77

0

Sample Output

1 2 4 5

1 2 4 6 7

1 2 4 8 12

1 2 4 5 10 15

1 2 4 8 9 17 34 68 77

Source:

**University of Ulm Local Contest 1997**
Submit
Status