# How can we prove that the common place value system is the most efficient representation of numbers?

Concretely, given a base $b$ and a number of digits $d$, what place value system has both of these properties:

1. Hold the largest (decimal) number $N$ within those digits.
2. Ensure that every number from $0$ to $N$ is representable within those digits.

The benchmark is the standard place value system - where the $k^{th}$ position from the right is $b^{k-1}$ and can hold numbers upto $N = {b^k}-1$

For example, a place value system that assigns to place $k$ the number $k$ can hold every number upto the maximum but would not be able to hold numbers larger than $d(d+1)\over2$ in base $2$. So, it violates #1 but conforms to #2 above.

A place value system that assigns to place $k$ the number ${b^k}^k$ can probably hold much larger numbers than the standard place value system, but cannot hold every number from $0$ to the largest number - hence, #1 is 'better' than the standard place value scheme, but #2 is violated.

Can we prove that the standard place value system is the best based on the above two requirements?

Update 1: I realize that using a straight multiplicative place value system, where each digit is multiplied by its place value cannot do better than the standard system. However, what if, say, I partitioned d digits into p partitions, and used a faster growing place value function for each partition, and then recombined them using some (say) additive function? How do we know that cannot yield something better?

• Wouldn't a number system which distinguishes between $10$, $1$, and $01$ be more efficient? – Justin Benfield Aug 28 '16 at 4:31
• @JustinBenfield - assuming all numbers are padded with zeroes on the left, 1 and 01 are the same, and 10 is different (value is 2) than 01 (value is 1) under the standard place value scheme. – Anand Aug 28 '16 at 4:41
• If the $k^{th}$ place multiplier $a(k)$ satisfies $a(k)>b^k$ you cannot, for example, achieve $1_b$ or $10_b$ etc. using the same "coefficients" $0,...,b-1$. – David Peterson Aug 28 '16 at 4:49
• @DavidP - agreed. Please see my update 1 above – Anand Aug 28 '16 at 4:59
• The Cantor expansion, I think, fulfills your criteria just a s well, but isn't a "base $b$" system. (I tried to find a decent online reference to Cantor expansion, but most hits are junk. Ken Rosen's number theory text has a good explanation.) – B. Goddard Aug 28 '16 at 19:34

## 1 Answer

Let me assume that by "represent with $d$ digits", you mean represent using a string of exactly $d$ digits. For instance, if $d=5$, this means you want to represent the number $1$ using the string $00001$ with a bunch of initial $0$s that you normally don't write.

We can prove that the standard place value system is maximally efficient by a simple counting argument. There are only $b^d$ different strings of $d$ digits, since you have $d$ digits and $b$ choices for each one. So any system of representing numbers by strings of digits can represent at most $b^d$ different numbers using $d$-digit strings. If you are supposed to represent all the numbers from $0$ to $N$, this means you are representing $N+1$ different numbers, so $N$ can be at most $b^d-1$. But the standard place value system does achieve this with $N=b^d-1$, so no other system can do better.

• I agree that using a straight multiplicative place value system, where each digit is multiplied by its place value cannot do better than the standard system. However, what if, say, I partitioned d digits into p partitions, and used a different place value function for each partition, and then recombined them using some (say) additive function? How do we know that cannot yield something better? – Anand Aug 28 '16 at 4:55
• I'm not assuming the system is multiplicative. I'm saying that for any system at all that uses $d$ digits, it can only represent $b^d$ different numbers, no matter how it interprets them. No matter what they are representing, there are only $b^d$ different strings of $d$ digits you can form. – Eric Wofsey Aug 28 '16 at 5:03