1
$\begingroup$

In any (standard) positional number system, the number of symbols required to represent a number $n$ is asymptotic to $O(\text{ln}(n))$. For example, in the base 2 (binary), the number of symbols required to represent $n$ is $\text{floor}(\text{log}_2(n))+1$.

In constrast, in most tally mark systems, the number of symbols required to represent a number $n$ is asymptotic to $O(n)$. These systems are less efficient than the positional number systems since numbers require exponentially more symbols to represent.

My question

I want to know if there exist systems that are even more efficient than the positional number systems, perhaps on the cor even $O(1)$ level, which only have a finite number of symbols.

The only one I could find online is called factorial number system, but it requires an infinite number of symbols.

UPDATE: I also am open to non-positional systems, as long as they are below $O(\text{ln}(n))$ and use a finite collection of symbols.

$\endgroup$
9
  • $\begingroup$ Pigeonhole principle $\endgroup$
    – David Lui
    May 27, 2021 at 0:18
  • $\begingroup$ you can cheat by using position. For example consider our system but in each position you can put the digit on top, or in the middle or in the bottom, then instead we would get $30$ options for our "10" symbols. You can also get an extra digit by allowing places to be empty and such. $\endgroup$
    – Asinomás
    May 27, 2021 at 0:21
  • $\begingroup$ @Onir That doesn't change $O(\ln n)$... $\endgroup$ May 27, 2021 at 0:24
  • $\begingroup$ And to OP, no, it is not possible, without an infinite collection of symbols, in which case you can do it with $O(1)$. $\endgroup$ May 27, 2021 at 0:25
  • $\begingroup$ @DonThousand is it impossible even for O(ln(ln(n)))? $\endgroup$
    – Nirvana
    May 27, 2021 at 0:27

1 Answer 1

2
$\begingroup$

If you have $c$ symbols and use $n$ of them there are only $c^n$ different strings, so that is the most numbers you can represent. That means to represent all the numbers up to $N$ you need $\log_c(N)$ symbols.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .