When we talk about large numbers, we are talking about numbers that are bigger than what we use in our ordinary day to day life. These are numbers typically used by mathematicians in fields such as cosmology, cryptography and statistical mechanics.
Since big numbers have a lot of digits, it is more efficient to use a special notation to make them more manageable. One of those systems is called Knuth's up arrow notation.
Invented by Donald Knuth in 1976, up arrow notation is a very powerful sequence. It is one of the more popular big number notations and it produces very big numbers. This article will explain how it works and provide some examples.
Introduction
Knuth up arrow notation is based on hyperoperations which are a sequence of increasing arithmetic operations that start at successorship, then go to addition, multiplication, exponentiation, and all the way up to infinity. Knuth up arrow notation leverages this sequence by using simple up arrows. It starts with exponentiation. Here is a simple example:
$$ 3^3 = 27 $$
If we progressed to the next hyperoperation it would be tetration which looks like this:
$$ 3^{3^3} = 3^{27} = 7625597484987 $$
Notice how quickly the number grows when going from exponentiation to tetration? Just adding another 3 gives us a number that is already 1000 times the size of the world population.
We can keep adding more numbers to the tower to get even bigger numbers. After a while this gets annoying because you get this massive power tower:
$$ 3^{3^{3^{3^{\unicode{x22f0}^{3}}}}} $$
This is where Knuth up arrow notation comes in handy. Rather than writing all of those exponents we can use arrows. Each up arrow is a higher level of operational power. It produces numbers that are massively bigger than the previous level. Here is a simple progression of up arrow notation:
$$ 2\uparrow3 = 2^3 = 8 $$
The digit on the left of the arrows represents the base. The digits to the right of the arrows represent how many times you want to perform the operation. The number of arrows represents the level of hyperoperation you want to perform.
One arrow is exponentiation. Two arrows is tetration. Three arrows is pentation. Four arrows is hexation and so on.
Let's try a few examples:
$$ 2\uparrow\uparrow3 = 2\uparrow2\uparrow2 = 2\uparrow4 = 2^4 = 16 $$
With two arrows it doesn't grow too quickly. With three arrows it starts to get crazy:
$$ 2\uparrow\uparrow\uparrow3 = 2\uparrow\uparrow2\uparrow\uparrow2 = 2\uparrow\uparrow(2\uparrow2) $$
$$ = 2\uparrow\uparrow4 = 2\uparrow2\uparrow2\uparrow2 = 2^{2^{2^2}} = 2^{16} = 65536 $$
See how quickly things got big? Now check out four up arrows:
$$ 2 \uparrow\uparrow\uparrow\uparrow 3 = 2 \uparrow\uparrow\uparrow 2 \uparrow\uparrow\uparrow 2 $$
$$ = 2 \uparrow\uparrow\uparrow 4 = 2 \uparrow\uparrow 2 \uparrow\uparrow 2 = 2 \uparrow\uparrow 65536 $$
We still have one more expansion left. At this point the number is freaking HUGE! It looks like this:
$$ \underbrace{ 2\uparrow2\uparrow2\uparrow...\uparrow2}_{65536 \text{ up arrows}} $$
To give you another frame of reference for how big this number is, let's take a look at where googolplex sits in terms of Knuth up arrow notation:
$$ Googolplex = 10^{10^{100}} $$
Another way to think of a Googolplex is 10 raised to the Googol. Its a big number. With up arrow notation this is where we would find Googolplex:
$$ 3\uparrow\uparrow4 > Googolplex < 3 \uparrow\uparrow5 $$
A Googolplex is actually closer to the lower bound but this is a good way approximate how big it is in terms of Knuth's up arrow notation.
Here is another example demonstrating the power of Knuth's up arrow notation:
$$ 3 \uparrow\uparrow\uparrow3 = 3\uparrow\uparrow3\uparrow\uparrow3 = 3 \uparrow\uparrow(3\uparrow3\uparrow3) $$
$$ = 3 \uparrow\uparrow(3^{3^3}) = 3 \uparrow\uparrow (7,625,597,484,987) $$
Another way to look at this number:
$$ = \underbrace{ 3\uparrow3\uparrow3\uparrow...\uparrow3}_{ 7,625,597,484,987 \text{ up arrows}} $$
Or you could look at it this way. It represents a tower of 3's 7.6 trillion high:
$$ = \underbrace{ 3^{3^{3^{3^{\unicode{x22f0}}}}}}_{7,625,597,484,987 \text{ 3's high}} $$
This number is already so big that we have no ability to understand it. Nothing in the world is this numerous. Even if we were to shuffle every particle in the known universe, we couldn't approach this number.
At some point the number of up arrows becomes a bit cumbersome to write. Are more efficient method is to use this notation:
$$ a\uparrow^n b $$
Formal definition
You can see the formal definition for Knuth's up arrow notation on Wikipedia. I'm not going to try to re-define all of it here. I will however show you the three important rules:
- \( a\uparrow^1b = a^b \)
- \(\uparrow^n 1 = a \)
- \( a\uparrow^{n+1} (b+1) = a\uparrow^n(a\uparrow^{n+1} b) \)
\(a\uparrow^n b\) is shorthand for \(a \uparrow\uparrow ... \uparrow\uparrow b\) with n arrows (where n is a positive integer.)
Arrow notation operations are right-associative: \( a\uparrow b \uparrow c \) always means \(a \uparrow (b \uparrow c) \).
The first few hyperoperations:
- \( a\uparrow b \) = exponentiation
- \( a\uparrow \uparrow b \) = tetration
- \( a\uparrow\uparrow\uparrow b \) = pentation
- \( a\uparrow\uparrow\uparrow\uparrow b \) = hexation
Graham's number
One of the classic big numbers is Graham's number. For a while it was the largest number ever used in a proof. That isn’t the case anymore but it is still a legend. I wrote a more comprehensive article on Graham's number. The number is the upper bound to a problem in Ramsey’s Theory. I won’t detail the problem but you can read more about it on the Wiki page.
Using up arrow notation to define Graham's number we would start with this:
$$ G1 = 3 \uparrow\uparrow\uparrow\uparrow 3 $$
Now that we've define G1 we can define G2 based on the result of G1:
$$ G2 = \underbrace{3\uparrow\uparrow...\uparrow\uparrow3}_{G1 \text{ up arrows}} $$
What!? That's sick. That number is ridiculous. We already know that G1 is this massive number and we use that to define the number of up arrows in G2? Wow. We have to keep doing this for G3, G4, G5, etc..
$$ G3 = \underbrace{3\uparrow\uparrow...\uparrow\uparrow3}_{G2 \text{ up arrows}} $$
$$ G4 = \underbrace{3\uparrow\uparrow...\uparrow\uparrow3}_{G3 \text{ up arrows}} $$
$$ G5 = \underbrace{3\uparrow\uparrow...\uparrow\uparrow3}_{G4 \text{ up arrows}} $$
This keeps going until we get to G4:
$$ G4 = \underbrace{3\uparrow\uparrow...\uparrow\uparrow3}_{G63 \text{ up arrows}} $$
And that's Graham's number. Another way to write it is:
G = g64, where g1 = \( 3\uparrow\uparrow\uparrow\uparrow3\), gn = \(3\uparrow^{g_{n-1}} 3\)
That number is just insanely big. It is clear that Knuth's up arrow notation is a very fast growing function.
How fast does it grow?
If we wanted to gauge its growth based on the Fast Growing Hierarchy we would say that:
$$ a\uparrow^n b \approx f_\omega(n) $$
This function will eventually dominate all primitive recursive functions.
Examples
A more progressive way to see the growth of this function is to see a slow growing example[1]:
Two arrows
\(10\uparrow2=10x10=100 \)
\(10\uparrow3=10x10x10=1000 \)
\(10\uparrow4=10x10x10x10=10000 \)
\(10\uparrow5=10x10x10x10x10=100000 \)
\(10\uparrow6=10x10x10x10x10x10=1000000 \)
\(10\uparrow7=10x10x10x10x10x10x10=10000000 \)
\(10\uparrow8=10x10x10x10x10x10x10x10=100000000 \)
\(10\uparrow9=10x10x10x10x10x10x10x10x10=1000000000 \)
\(10\uparrow10=10x10x10x10x10x10x10x10x10x10=10000000000 \)
\(10\uparrow10 = 10\uparrow\uparrow2 \)
Three arrows
\(10\uparrow\uparrow2=10^{10}\)
\(10\uparrow\uparrow3=10^{10^{10}}\)
\(10\uparrow\uparrow4=10^{10^{10^{10}}}\)
\(10\uparrow\uparrow5=10^{10^{10^{10^{10}}}}\)
\(10\uparrow\uparrow6=10^{10^{10^{10^{10^{10}}}}}\)
\(10\uparrow\uparrow7=10^{10^{10^{10^{10^{10^{10}}}}}}\)
\(10\uparrow\uparrow8=10^{10^{10^{10^{10^{10^{10^{10}}}}}}}\)
\(10\uparrow\uparrow9=10^{10^{10^{10^{10^{10^{10^{10^{10}}}}}}}}\)
\(10\uparrow\uparrow10=10^{10^{10^{10^{10^{10^{10^{10^{10^{10}}}}}}}}} \)
\(10\uparrow\uparrow10 = 10\uparrow\uparrow\uparrow2 \)
Four arrows
\(10\uparrow\uparrow\uparrow2 = 10\uparrow\uparrow10 \)
\(10\uparrow\uparrow\uparrow3 = 10\uparrow\uparrow10\uparrow\uparrow10 \)
\(10\uparrow\uparrow\uparrow4 = 10\uparrow\uparrow10\uparrow\uparrow10\uparrow\uparrow10 \)
\(10\uparrow\uparrow\uparrow5 = 10\uparrow\uparrow10\uparrow\uparrow10\uparrow\uparrow10\uparrow\uparrow10 \)
\(10\uparrow\uparrow\uparrow6 = 10\uparrow\uparrow10\uparrow\uparrow10\uparrow\uparrow10\uparrow\uparrow10\uparrow\uparrow10 \)
\(10\uparrow\uparrow\uparrow7 = 10\uparrow\uparrow10\uparrow\uparrow10\uparrow\uparrow10\uparrow\uparrow10\uparrow\uparrow10\uparrow\uparrow10 \)
\(10\uparrow\uparrow\uparrow8 = 10\uparrow\uparrow10\uparrow\uparrow10\uparrow\uparrow10\uparrow\uparrow10\uparrow\uparrow10\uparrow\uparrow10\uparrow\uparrow10 \)
\(10\uparrow\uparrow\uparrow9 = 10\uparrow\uparrow10\uparrow\uparrow10\uparrow\uparrow10\uparrow\uparrow10\uparrow\uparrow10\uparrow\uparrow10\uparrow\uparrow10\uparrow\uparrow10 \)
\(10\uparrow\uparrow\uparrow10 = 10\uparrow\uparrow10\uparrow\uparrow10\uparrow\uparrow10\uparrow\uparrow10\uparrow\uparrow10\uparrow\uparrow10\uparrow\uparrow10\uparrow\uparrow10\uparrow\uparrow10 \)
\(10\uparrow\uparrow\uparrow10 = 10\uparrow\uparrow\uparrow\uparrow2 \)
Five arrows
\(10\uparrow\uparrow\uparrow\uparrow2 = 10\uparrow\uparrow\uparrow10 \)
\(10\uparrow\uparrow\uparrow\uparrow3 = 10\uparrow\uparrow\uparrow10\uparrow\uparrow\uparrow10 \)
\(10\uparrow\uparrow\uparrow\uparrow4 = 10\uparrow\uparrow\uparrow10\uparrow\uparrow\uparrow10\uparrow\uparrow\uparrow\uparrow10 \)
\(10\uparrow\uparrow\uparrow\uparrow5 = 10\uparrow\uparrow\uparrow10\uparrow\uparrow\uparrow10\uparrow\uparrow\uparrow10\uparrow\uparrow\uparrow10 \)
\(10\uparrow\uparrow\uparrow\uparrow6 = 10\uparrow\uparrow\uparrow10\uparrow\uparrow\uparrow10\uparrow\uparrow\uparrow10\uparrow\uparrow\uparrow10\uparrow\uparrow\uparrow10 \)
\(10\uparrow\uparrow\uparrow\uparrow7 = 10\uparrow\uparrow\uparrow10\uparrow\uparrow\uparrow10\uparrow\uparrow\uparrow10\uparrow\uparrow\uparrow10\uparrow\uparrow\uparrow10\uparrow\uparrow\uparrow10 \)
\(10\uparrow\uparrow\uparrow\uparrow8 = 10\uparrow\uparrow\uparrow10\uparrow\uparrow\uparrow10\uparrow\uparrow\uparrow10\uparrow\uparrow\uparrow10\uparrow\uparrow\uparrow10\uparrow\uparrow\uparrow10\uparrow\uparrow\uparrow10 \)
\(10\uparrow\uparrow\uparrow\uparrow9 = 10\uparrow\uparrow\uparrow10\uparrow\uparrow\uparrow10\uparrow\uparrow\uparrow10\uparrow\uparrow\uparrow10\uparrow\uparrow\uparrow10\uparrow\uparrow\uparrow10\uparrow\uparrow\uparrow\uparrow10\uparrow\uparrow\uparrow10 \)
\(10\uparrow\uparrow\uparrow\uparrow10 = 10\uparrow\uparrow\uparrow10\uparrow\uparrow\uparrow10\uparrow\uparrow\uparrow10\uparrow\uparrow\uparrow10\uparrow\uparrow\uparrow10\uparrow\uparrow\uparrow10\uparrow\uparrow\uparrow10\uparrow\uparrow\uparrow10\uparrow\uparrow\uparrow10 \)
\(10\uparrow\uparrow\uparrow\uparrow10 = 10\uparrow\uparrow\uparrow\uparrow\uparrow2 \)