This seems obviously wrong, though I admittedly don't know the stars and bars trick. Lets say you wanted to store a number a in [0,k), for arbitrarily large k.

This seems obviously wrong, though I admittedly don't know the stars and bars trick. Lets say you wanted to store a number a in [0,k), for arbitrarily large k. All you would need to so is encode your value as 0 repeated a times, and 1 repeated k-a times. Because you can store arbitrary integers below k with this method, you would need at least log(k) space. If k can be arbitrarily large, you would require unbounded space.