# 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?

-

## 1 Answer

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}$

The gap is more apparent with larger numbers, if we take our normal base 10 system, then writing 1000 takes 4 decimal digits, but writing it in unary takes 1000 ones.

-
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

2
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

2
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
Thank you, that makes sense! – John Hoffman Dec 1 '12 at 1:50
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 16, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 5, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9286289215087891, "perplexity_flag": "middle"}