Towers of Powers

One of the many problems in computer-generated graphics is realistically modeling the “orderly random- ness” of things like mountain ranges and city skylines. A new student intern at a graphics company had an idea—use fluctuations in number representations to model height. In this problem you will compute several such number representations and show the “skylines” they produce. Let n be any positive integer, and let b be an integer greater than or equal to 2. The complete base− b expansion of n is obtained as follows. First write the usual base-b expansion of n, which is just a sum of powers of b, each multiplied by a coefficient between 1 and b − 1, omitting terms with zero coefficients. For example, if n = 20000 and b = 3, the base-3 expansion of 20000 is given by 20000=39 +35 +2×33 +2×32 +2 To obtain the complete base-b expansion, we apply the same procedure to the exponents until all numbers are represented in base b. For n = 20000 and b = 3 we would have 20000=332 +33+2 +2×33 +2×32 +2 As another example, consider n = 16647 and b = 2. The resulting expansion is 16647=222+1+22+2 +222+1 +22 +2+1 The rising and falling heights of the numbers form the number’s “skyline.” For each pair of integers n and b in the input, display the complete base-b representation of n. Your display should use multiple output lines for different exponent heights. The display must begin with ‘n =’ , followed by the expansion. Answers should use an asterisk (*) as the multiplication symbol between coefficients and powers of b. Zero terms must not be printed, and unnecessary coefficients and exponents must not be shown (for example, display 1 instead of b0, b2 instead of 1 ∗ b2 and b instead of b1). To assist in accurately viewing the skyline of the number, the display must show one character (either a digit, +, or *) per column of the multi-line display; there must be no unnecessary spaces. The correct format is illustrated in the sample output shown below. Answers must be displayed using no more than 80 columns. Expansions requiring more than 80 columns must be split between terms, and a second set of display lines used to show the remaining portion of the expansion. The second part of the answer must begin in the same column as the previous part of the answer. See the sample output for an example. Input Input is a sequence of pairs of integers, n and b, followed by a pair of zeroes. Each value for n will be positive, and each value for b will be greater than or equal to 2. No value will exceed the maximum signed integer size for the machine. Output For each input pair, n and b, print the complete base-b expansion of n as described above. Print a line containing n in complete base b: preceding each expansion. Separate the output for consecutive pairs by a line of hyphens. All coef- ficients, bases, and exponents are to be displayed as standard base 10 integers. The expansion for each input pair will require at most two standard screen widths, allowing for indentation and splitting between terms of the expansion.

1000 in complete base 12: 2 1000 = 612 +1112+4

85026244 in complete base 3: 2222222 3 +23+1 85026244 = 3 23+2 +23 +3 +23 +3+1 3 +23 3 +3+2 3 +3+1 3 +2 3 +1 3 +23 +23 +23 +23 +23 +23 23+1 3