A given natural number $n \in \mathbb{N}$ has many *representations*
as expressions mixing other natural numbers and the operators and punctuation symbols
$\{+,-,\times,/,\exp,(,)\}$, where '$\exp$' means exponentiation. For example,
four representations of $128$ are $\{130-2,128, 2 \times 64, 2^7\}$.
Define the *cost* of a representation as the total number of digits that occur in the
representation, with all operators and parentheses assigned zero cost.
In other words, imagine erasing all the symbols and just counting up the digits.
So the costs of the four representations of $128$ above are $\{4,3,3,2\}$.

I am interested in minimal-cost representations of numbers, and especially those numbers that have representations of smaller cost than their explicit representation as just a number with no operators. In some sense, I am asking for which numbers are compressible via the operators. (Thinking about compression is the origin of this question.) Unfortunately, I think the notion is base-dependent, but perhaps not fundamentally so.

Here are two specific questions:

(1) Which natural numbers have a representation more efficient than the unadorned number? At least, what is the start of such a list? In particular, which is the smallest
number efficiently representable? (In base $10$; but other bases are equally
interesting.)

**Answered** by *Gerry Myerson*. The list starts
$5^3{=}125,\; 2^7{=}128,\; 6^3{=}216,\; 3^5{=}243,\; 4^4{=}256, \ldots$.

(2) What fraction of numbers $n \le N$ have a more efficient representation than themselves, as $N \to \infty$? Perhaps this question has a base-independent answer?

Analogous questions may have been explored previously, perhaps with a different set of operators. If so, I'd appreciate a pointer—Thanks!

9more comments