0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Wouldn't a number system which distinguishes between $10$, $1$, and $01$ be more efficient? $\endgroup$ – Justin Benfield Aug 28 '16 at 4:31
  • $\begingroup$ @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. $\endgroup$ – Anand Aug 28 '16 at 4:41
  • $\begingroup$ 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$. $\endgroup$ – David Peterson Aug 28 '16 at 4:49
  • $\begingroup$ @DavidP - agreed. Please see my update 1 above $\endgroup$ – Anand Aug 28 '16 at 4:59
  • 1
    $\begingroup$ 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.) $\endgroup$ – B. Goddard Aug 28 '16 at 19:34
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Anand Aug 28 '16 at 4:55
  • 1
    $\begingroup$ 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. $\endgroup$ – Eric Wofsey Aug 28 '16 at 5:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.