combinatorics - 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?