# Will $a^a$ ever out-grow $9^{9^{^\ldots}}$?

I am trying to come up with the largest finite number that can be made using a set number of characters.

I have two expressions which are calculated and printed out by a program (theoretically - they are too big to actually be calculated or displayed.)

print(9^9^9^9^9^9)
a=9^9^9 print(a^a)


These two programs are equal in length. My question is, if "^9" were added to the first expression, as well as to the definition of the variable 'a', would a^a ever become greater than the first expression? If not, what if it were a^a^a? Will it always be greater?

Based on the required length of the two programs, the first expression is $^n9$ while the second is $^2(^{n-3}9)$. My question boils down to this:

When is $^2(^{n-3}9)>{^n9}$?

Edit: I noticed something from how $^2(9^9)=(9^9)^{(9^9)}=9^{(9*9^9)}$ and $^2(9^{9^9})=9^{9^{9*9^{9^9}}}$. The tower from $^2(9^9)$ is 3 exponents high, and the tower from $^2(9^{9^9})$ is 5 exponents high. It appears that $^2({^x9})$ is always $2x-1$ exponents high. From this, an answer can be derived:

$$^2(^{n-3}9)>{^n9}$$ $$^{2n-7}9>{^n9}$$ $$2n-7>n$$ $$n>7$$

So, this tells me that $(^59)^{(^59)}>{^{8}}9$. Am I correct in going about this?

• If the powers are computed from left to right, your first formula doesn't give the tetration function, but $9^9$ then $9^{(9^2)}$ etc Aug 25, 2015 at 20:53
• They aren't computed from left to right. That would be $9^{9*9*...}$, they are computed correctly from right to left. Aug 25, 2015 at 20:54
• This is an old problem. The hardest part turns out to be not the specifying of a very large number but comparing two very different specifications. Your question is an example of this. Aug 25, 2015 at 20:55
• It's also very important to be very clear with what tools you have available, otherwise you venture into paradox territory. The archexample would be a+1, where a is the largest integer describable with fewer than 100 symbols. Aug 25, 2015 at 20:59
• @Waffle: That's a busy beaver problem. It's algorithmically unsolvable as soon as you have just modest code space available. Aug 25, 2015 at 21:04

Let $a = 9^{9^9}$ Then $$a^a = (9^{9^9})^{9^{9^9}} = 9^{9^9 \cdot 9^{9^9}} \overset{?}{<} 9^{9^{9^{9^{9^9}}}}$$ Take logarithm to base 9 $${9^9 \cdot 9^{9^9}} \overset{?}{<} {9^{9^{9^{9^9}}}}$$ Take logarithm to base 9 $${9 +{9^9}} \overset{?}{<} {{9^{9^{9^9}}}}$$ Take logarithm to base 9 making the solution perfectly obvious: $$\log_9({9 +{9^9}})<1+9 =10 \overset{!}{<} {{{9^{9^9}}}}$$

I think it is obvious how this generalizes (and can be checked) for other forms of $a$ (like $a=\;^49$) and other constructions like $\;^3a$ etc.

It seems like you only want to focus on towers of exponents and usage of variables. You might assume that the magnitudes of the numbers you can form are always strictly ordered by the heights of the exponential towers (which is a reasonable assumption, since it would take much larger numbers (hence, probably longer coding length) in a shorter tower to give a larger number than a higher tower). If you do that, then the question is what is the highest tower you can make given a certain maximum code length?

It should be clear that the optimal strategy is to define a tower of some height, call it $A$, and then form a tower $A^{A \ldots}$ of some height, call the tower $B$, and then form a tower $B^{B \ldots}$ of some height, call the tower $C$, etc. The question is how many definitions of new towers in terms of old you should use, and how high you should make the tower construction at each step when you define a new tower in terms of old. This is rather easy to solve as soon as you show that at a certain critical length of characters used in the current tower, you are better off stopping the current tower construction and defining a new tower construction, at the expense of 4 extra characters (since it seems you add a space and then basically $B = A \ldots$ and then you can use tower building the same as before, using $A$ as your building block tower instead of whatever $A$ was defined in terms of).

Anyways, when you start defining new towers in terms of old towers, the height of the $k$th tower you build will be $T(k) = N_k \cdot (T(k-1) - 1) + 1$ where $N_k$ is how how high you define the tower in the $k$th construction in terms of exponential tower iterations of the previous tower, and $T(k)$ is the height of the overall tower after $k$ iterations. And the length of your program will be $L(k) = L(k-1) + 2 + 2N_k$ after the $k$th construction iteration. This is a tractable recurrence maximization problem that you can solve to get the optimal choices of the $N_k$ for a given maximum program length.

In fact $^2(^{n-3}9) < {^{n-1}}9$ for all $n \ge 3$. This is easy to check for $n = 3,4$, and for $n \ge 5$ we have

$$^2(^{n-3}9) = (^{n-3}9)^{^{n-3}9} = 9^{(^{n-4}9)(^{n-3}9)} = 9^{9^{^{n-5}9 + ^{n-4}9}} < 9^{9^{^{n-3}9}} = {^{n-1}}9.$$

In your argument, you incorrectly state that $^2(9^{9^9}) = 9^{9^{9 * 9^{9^9}}}$, when in fact $^2(9^{9^9}) = 9^{9^9 * 9^{9^9}}$.