3
$\begingroup$

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!

Improve this question
$\endgroup$
14
  • 1
    $\begingroup$ See related concept of Kolmogorov complexity: en.wikipedia.org/wiki/Kolmogorov_complexity $\endgroup$
    – Joel David Hamkins
    Commented Dec 2, 2013 at 1:50
  • 1
    $\begingroup$ Kolmogorov complexity would be relevant if you allowed an operator like "Output of the C program whose ASCII code is". For the limited list of operators in the question, the issue seems to be more number-theoretic than computability-theoretic. $\endgroup$
    – Andreas Blass
    Commented Dec 2, 2013 at 1:57
  • 1
    $\begingroup$ @JoelDavidHamkins, it does not make difference (up to a constant factor), because in a binary tree the number of external nodes (leaves) is always equal to one plus the number of internal nodes. $\endgroup$
    – Michal R. Przybylek
    Commented Dec 2, 2013 at 12:45
  • 2
    $\begingroup$ @JosephO'Rourke, a more accurate reference than "Kolmogorov complexity" is "minimum description length". Computationally, MDL is almost always either "impossible" or "very difficult". However, in most cases it can be well approximated by Bayesian complexity. $\endgroup$
    – Michal R. Przybylek
    Commented Dec 2, 2013 at 12:59
  • 1
    $\begingroup$ If you like "base 1", you might consider the one complexity of an integer. The version I like involves plus, times, parentheses, and as few copies of the number 1 as can be managed. The one complexity of x is x for x < 6, and goes up as log base 3 x. An unanswered question is if 4lg3 x is an upper bound for x>1, although it is known 3lg2 x is. (I'm using base 2 and base 3 logs here.) It turns out to be easy to approximate but hard to determine exactly and quickly for many x. Gerhard "Has Some Ear Worms, Too" Paseman, 2013.12.02 $\endgroup$
    – Gerhard Paseman
    Commented Dec 3, 2013 at 3:33

2 Answers 2

Reset to default
3
$\begingroup$

I think what's wanted are the numbers tabulated at http://oeis.org/A104233, in which case the start of the list is 125, 128, 216, 243, 256, 343, 512, 625, 729, 1000, 1015, 1016, 1017, 1018, 1019, 1020, 1021, 1022, 1023, 1024, 1025, 1026, 1027, 1028, 1029, 1030, 1031, 1032, 1033. These are perfect powers, or $4^5\pm d$ with $d$ a single digit.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Nice find! So $\{ /,(,) \}$ never occur in the optimal representation? $\endgroup$
    – Joseph O'Rourke
    Commented Dec 2, 2013 at 10:43
  • 2
    $\begingroup$ @JosephO'Rourke, I guess that it is easy to prove that $99^{99}/9$ is the optimal representation. $\endgroup$
    – Michal R. Przybylek
    Commented Dec 2, 2013 at 15:56
  • 2
    $\begingroup$ Also $1029=3\cdot 7^3.$ It may be that $5\cdot 6^3=1080$ is the smallest one not a perfect power nor $a^b \pm c$ $\endgroup$
    – Aaron Meyerowitz
    Commented Dec 2, 2013 at 22:14
  • 1
    $\begingroup$ Perhaps $(7^9+9^9)/2$ is an optimal representation using parentheses, but I haven't made any serious effort to check this. $\endgroup$
    – Gerry Myerson
    Commented Dec 2, 2013 at 23:57
1
$\begingroup$

In the limit of large $N$, I'd have thought a simple lower bound for the average "compression ratio" by minimal-length representations in base $b$ is something like $\frac{log(b)}{log(b + n)}$, where $n$ is the number of extra symbols permitted. This is because one can simply identify the symbols with extra digits in base $b + n$, and map the base $b$ numbers to the base $b + n$ numbers, obtaining a conservative estimate by neglecting symbol constraints such as the need for balanced brackets and no trailing $+$ signs etc.

Improve this answer
$\endgroup$

You must log in to answer this question.

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