From: Henry Baker <hbaker1@pipeline.com>

The length of a unary representation of n is O(n), while the length of a positional representation of n is O(log(n)).

Are there representations of n that grow as O(sqrt(n)) or O(cbrt(n)) ?

The examples given by Joshua Zucker and Richard Guy are in funky bases ("base triangle" and base j(j+1)/2) that are between unary representation and positional representation. For binary, using histogram-of-lengths notation, a simple O(sqrt(n)) code is 0. 0 1 2 3 4 5 6... Meaning the code words are 00, 010, 011, 1000, 1001, 1010, 10101, 10110, 10111, 11000, 110010, 110011, 110100, 110101, 110110... Because 1/4 + 2/8 + 3/16 + 4/32 + 5/64... = 1 I found this not by smarts but by feeding 1 / 2 ^ sqrt(n) weights into my Huffman code histogram generator. It put out: 0. 0 0 2 4 6 8 10... Which is more efficient (fair) for that set of probabilities but not as cute. For 1 / 2 ^ cbrt( n ) it says: 0. 0 0 0 0 2 10 24 44 70 102 140 184 234 290... Which is ( 3 n^2 - n ) / 2^(n+4) for n = 1... So Huffman's algorithm is a way to turn an arbitrary expression into a series that adds up to 1. Including rootary binaries. --Steve