Writing numbers with fewer symbols using expressions with powers

For example, it takes 7 symbols to write the natural number $n=9999999$ but we can also write it with 5 symbols as $n=10^7-1$. (Of course, with even larger exponents we can save even more symbols.)

Another example: $13841304697 = 7^{12}+8*3^7$. Here we have 11 symbols vs. 8 symbols.

Let's denote by $r(n)$ the minimal number of symbols needed to represent the natural number $n$ with this sort of expressions using exponentiation (to a natural number), $+, -, *$ and $/$.

There are all sorts of interesting questions that arise:

• How to find the minimal representation? Does some sort of greedy algorithm that takes $a^b$ away from $n$ so that $r(n-a^b)$ is minimal work?

• What type of numbers $n$ have large values for $r(n)$ relative to the number of digits of $n$?

• How much writing numbers minimally like this, saves space. To put it formally, what can we say about

$$\frac{\sum_{n=0}^N r(n)}{ \sum_{n=0}^N (\lfloor \log_{10}(n)\rfloor + 1) }?$$

Solution 1:

Are you intending to restrict this just to base 10? It may be more natural to look at base 2, or to look at what happens in base b.

Note that for any fixed base b, one isn't going on average to do much better than writing in base b, as one can see from a counting argument of how many arrangements of symbols one has. In general, exponentiation and concatenation are tough to work with. Even simpler versions of this problem are not well understood. See my comment on this How many fours are needed to represent numbers up to $N$? question as well as the paper referenced there.