Fastest algorithm for splitting an integer

Question

I have a number $n$ in the range $1$ - $255$. What I'm trying to do is split $n$ into the shortest list of numbers $1$ -$16$ that add up to $n$. For example, let's say $n$ is $32$. Then, we could simply use $16$ and $16$. However, if $n$ is $33$, it would be $16, 16, 1$.

Is there any simple and fast algorithm to accomplish this? I'm not even sure what to google when researching this, so even keywords and hints are a help. Thank you!

Answer 1

Write $n = 16q + r$ with $0 \le r < 16$. Then use $16$ exactly $q$ times and $r$ once, a total of $q+1$ terms.

Answer 2

So basically you are asking what the fastest way to compute the quotient and remainder of $n$ divided by $16$ is? Sounds more like a computer science question ...

In fact, if you have the number in binary (you seem to like binary, given your $255$, and $16$...), it's easy:

Say you have $158$, which is $10011110_2$

Then the first four bits ($1001=9_{10}$) gives you the quotient, and the last four bits ($1110=14_{10}$) the remainder. So you need $9$ $16$'s and $1$ $14$: $16,16,16,16,16,16,16,16,16,14$