Given a set of digits, what is the biggest number we can make using exponentiation - numberphile noodle quiz

The question is motivated by a question on a can of number noodles.

Each item is a digit between $0$ and $9$. Clearly, if you form a string and consider it to represent a base $10$ integer, then you'll get the biggest number if you start with the high digits $999...$ and end with the zeros $...1111000000000$.

In this youtube video, username numberphile (who does enthusiastic number theory videos for the layman) presents the digis of his can and brings forward the following generalized question:

Given a set of digits from my noodle can, what's the biggest number you can make using only

(a) addition,

(b) multiplication

and

(c) exponentiation?

So here my thoughts:

Generally, I'm given a multiset of digits and I can use up any of these together two form numbers greater than $9$. And each of the three operations is binary, i.e.

$(a,b)\mapsto a+b,\ \ \ \ \ \ $

$(a,b)\mapsto a\cdot b,\ \ \ \ \ \ $

$(a,b)\mapsto a^b,$

and only the last one isn't commutative and associative. The question seems to imply we can use bracketing as we like, so I won't bother about these.

I can decide the first two tasks simply by checking if the concatenation of digits is better than binary operation for accieving big numbers: Given $n+1$ digits $(d_0,d_1,d_2,...,d_n)$, their concatenation

$\text{con}:(d_n,d_{n-1},d_{n-2},\dots,d_1,d_0) \mapsto \sum_{k=0}^n d_k 10^k$

gives us summands involving higher and higher powers of $10$.

Since for $d_{n}\ne 0$ we have

$\sum_{k=0}^{n} d_k 10^k < 10^{n+1},$

we find

$d_{n+1}\cdot\text{con}(d_n,\dots) =d_{n+1}\sum_{k=0}^{n} d_k 10^k < d_{n+1}10^{n+1} < \sum_{k=0}^{n+1} d_k 10^k = \text{con}(d_{n+1},d_n,\dots).$

i.e. $\text{con}$ is stronger than multiplication for any free digit.

However, checking some pairs of digits for the third operation

$$2^3<3^2<23<32,$$

$$34<43<4^3<3^4$$

or

$$5^2=25<2^5<52$$

I can see no obvious pattern! The algorithm to construct the biggest number will depend on the values of the symbols. So my first question is this (the question in the video):

(c) Using concatenation and exponentiation, what is the biggest number you can make? How can you show that it is really is the maximum?

I guess that proof should be done in general, but here are the specific digits of the problem:

I'm just going to assume no available computer will be able to compute that absurd power, but I'd be interested in some of its characteristics nevertheless.

Further thoughts:

Now if there are $N$ digits in total, which are free to use in concatenation, you can use number sets of up to size $N$ for the binary operaton. E.g. If there were only three digits $\{0,3,7\}$, the number sets of size $N=2$ would be $\{\{0,37\}, \{0,73\},\{3,70\},\{7,30\}\}$. Side note: There is an obvious additional rule regarding zero, namely that you can't have strings starting with $0$.

For each number $N$, there are a fixed number of possible bracketings, like e.g. $(a,((b,c),d))$, which determine the result, $a^{(b^c)^d}$ here. I guess the bracketing is a simple (downwards) tree graph where each node has eighter none or two (downwards) offspings. One should be able to count these.

The amount of of different numbers for the binary operation (exponentiation is of primary interest here) one can generate is limited by the quantity of number sets you can build using concatenation of digits and the number of braketings for each set size. How many different filled bracket structures can you have?

Notice that for the noncommutative exponentiation, the two number sets $\{a,b\}$ have to be replaces by pairs $\{(a,b),(b,a)\}$ because $a^b\ne b^a$.

And much more difficult:

Taking into account that different such structures can end up in the same number: What is the quantity of different results you can have? Is there a workable method of working out the "kernel" of this construction?

Lastly (minor priority):

As we deal with high number of digits here, the majority of results have relatively low Kolmogorov complexity. Given a certain operaton (e.g. exponentiation), the biggest number we can generate and the number of results we can have, can we conclude a pattern regarding the gap size between different biggest numbers as a function of the numbers of digits we use as input?

This is just a scketch of a solution:

• $(a^b)^{c^x}=a^{b*c^x}<a^{b^x*c^x}=a^{(b*c)^x}<a^{concatenation(b,c)^x}$ for $x\geq1$. So the only parentethization possible is $a^{b^{c^d}}$
• $a^{b^x}>concatenation(a,b)^x$ if $a,b>1$ for any decent $x$ (say $\geq10$)
• $a^{b^x}\leq concatenation(a,b)^x$ if $a$ or $b$ are $\leq 1$ for any decent $x$
• $a^{b^x} > b^{a^x}$ is true if $a<b$ for any decent $x$
• given this rule, after the first few exponentiation (for witch concatenation/inversion between smaller and bigger number can be better) you should have the number sorted, with the smaller at the beginning and biggest number going up

Now the only thing left is understand how concatenate $0$s and $1$s, and what are the inner few steps, fixing these thing give an optimal solution (just exponentiate fromn smallest to biggest, until the last few steps).

For $0$ and $1$ I do not have a complete proof, but I suspect that is better to first build $10$s, if there are $0$ left use them for build $90$ (or $80$ ..), and if there are $1$ left first add them for forming $11$ and then for forming $91$ (or $81$).

For the inner few steps, if the biggest number that you have is bigger than the "decent" $x$, you already have a solution, otherwise few tries can be needed to found the optimal inner steps (eg. given three $2$, the optimal form is $2^{22}$ instead of $2^{2^2}$).

I suggest the following greedy strategy:

• first match the $0$ and the $1$ forming two digit numbers $10$
• if you have spare $0$, utilize them to form $90$, then $80$, ... (this need a proof)
• if you have spare $1$, utilize them to form $11$, then $91$, $81$, ... (this part too)
• sort the number that you have, smaller to biggest
• the solution should be something like: $2^{2^{3^{...^{10^{80^{90}}}}}}$, with the number sorted
• if the biggest number is greater that the "decent" $x$ in the above proofs, this is the solution, otherwise you might need to try other solution for the inner step , but fixed the first few inner step (until the number become big enought to justify the "decent" $x$ assumption), the order of other numbers is fixed by the greedy strategy.

In conclusion, the number that you are looking I think is 2^2^2^2^2^2^ ... 3^3^3^3^3^3^ ... 10^10^10^10^ ... 90^90^90^90 ($12$ $2$s followed by $14$ $3$s, $25$ $4$s, $16$ $5$s, $9$ $6$s, $28$ $7$s, $18$ $8$s, $9$ $9$s, $16$ $10$s and $16$ $90$s).