The Universe of Discourse

Tue, 13 Nov 2018

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!!:

 1 3 9 27 81 243 2 6 18 54 162 … 4 12 36 108 … … 8 24 72 216 … … 16 48 144 … … … 32 96 … … … … 64 192 … … … … 128 … … … … …

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.

 1 3 9 27 2 6 18 54 4 12 36 108

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

 1 3 9 27 2 6 18 54 4 12 36 108 8 24 72 216

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!!.