The Universe of Discourse

A puzzle about representing numbers as a sum of 3-smooth numbers

I think this would be fun for a suitably-minded bright kid of maybe 12–15 years old.

Consider the following table of numbers of the form !!2^i3^j!!:

Given a number !!n!!, it is possible to represent !!n!! as a sum of entries from the table, with the following constraints:

• No more than one entry from any column
• An entry may only be used if it is in a strictly higher row than any entry to its left.

For example, one may not represent !!23 = 2 + 12 + 9!!, because the !!12!! is in a lower row than the !!2!! to its left.

But !!23 = 8 + 6 + 9!! is acceptable, because 6 is higher than 8, and 9 is higher than 6.

Or, put another way: can we represent any number !!n!! in the form $$n = \sum_i 2^{a_i}3^{b_i}$$ where the !!a_i!! are strictly decreasing and the !!b_i!! are strictly increasing?

Spoiler:

    maxpow3 1 = 1
    maxpow3 2 = 1
    maxpow3 n = 3 * maxpow3 (n `div` 3)

    rep :: Integer -> [Integer]
    rep 0 = []
    rep n = if even n then map (* 2) (rep (n `div` 2))
        else (rep (n - mp3)) ++ [mp3] where mp3 = maxpow3 n

Sadly, the representation is not unique. For example, !!8+3 = 2+9!!, and !!32+24+9 = 32+6+27 = 8+12=18+27!!.

[Other articles in category /math] permanent link