# Why is the unary representation of a number exponentially larger than a base k representation of it?

According to a book I am reading, the unary representation of a number exponentially larger than a base k representation of it. I, however, feel that the unary representation should scale linearly with the input.

After all, 1 is 1, 2 is 11, 3 is 111, and so on, right? Wouldn't that be linear?

-

The base $k$ representation of the number $n$ takes $\log_{k}n$ bits, whereas the unary representation takes $n$, and of course $n = k^{\log_{k}n}$
Thanks! I wonder how to prove though that the base $k$ representation of the number $n$ takes $\log_{k}n$ bits... the example with large numbers in base 10 does make sense though. – John Hoffman Dec 1 '12 at 1:11
A sketch of why it takes a logarithmic amount of space is to get the first digit, you divide your number by your base $k$, the remainder gives you your least significant digit, then you divide the quotient by $k$ again, getting the next digit as the remainder, and so on. So the length of the number $n$ representation base $k$ is the number of times you can divide $n$ by $k$ and get a non-zero quotient. I'll stick an example in the next comment. – Luke Mathieson Dec 1 '12 at 1:29
Say we have 25, and we want it in base 2. We divide by 2, and get quotient 12, remainder 1, so our base 2 number has 1 as its first bit. Then divide 12 by 2, get quotient 6, remainder 0, so our number-in-progress is 01. Compressing the notation a little now; 6/2 = 3r0 -> 001 : 3/2 = 1r1 -> 1001 : 1/2 = 0r1 -> 11001. At this point our quotient is down to zero, so we're done. This took 5 steps, which is $\lceil \log_{2}25\rceil$ (we need the ceiling function as we can't have a fraction of a digit - there's some other small technicalities too, exact powers take $1+log_{k}n$ digits). – Luke Mathieson Dec 1 '12 at 1:37