jordan scales home projects twitter github
May 19, 2019

A Blueprint for Large Numbers

Consider a modest function "A," which takes a number and adds one to it.

A(1)=2A(2)=3A(99)=100 \begin{aligned} A(1) &= 2 \ A(2) &= 3 \ A(99) &= 100 \end{aligned}

It's not much of an operator, and is easily defeated by its counterpart: "evil A."

Aˇ(2)=1Aˇ(3)=2Aˇ(100)=99 \begin{aligned} \check A(2) &= 1 \ \check A(3) &= 2 \ \check A(100) &= 99 \end{aligned}

We can apply "A" multiple times.

A(A(1))=A(2)=3A(A(A(A(1))))=5 \begin{aligned} A(A(1)) = A(2) &= 3 \ A(A(A(A(1)))) &= 5 \end{aligned}

Repeating "A" is a little tiring, so we can use a superscript to make things a little more concise.

A(A(1))=A2(1)=3A(A(A(A(10))))=A4(10)=14 \begin{alignedat}{2} A(A(1)) &= A^2(1) &&= 3 \ A(A(A(A(10)))) &= A^4(10) &&= 14 \end{alignedat}

Since the superscript implies "add 1 this many times," the following properties unfold:

An(1)=1+nAn(10)=10+nAn(99)=99+n \begin{aligned} A^n(1) &= 1 + n \ A^n(10) &= 10 + n \ A^n(99) &= 99 + n \end{aligned}

Or, more generally:

An(m)=m+n A^n(m) = m + n

Behold, addition!

Small steps

Our goal is to make large numbers, so we may start throwing some of them at A in hopes of making them even bigger.

A1000(1000)=2000A1000000(1000000)=2000000 \begin{aligned} A^{1000}(1000) &= 2000 \ A^{1000000}(1000000) &= 2000000 \end{aligned}

But we're not making much progress. For starters, we have to pass in two big numbers - what a waste. Let's not repeat ourselves so much by creating a new function "B":

B(n)=An(n) B(n) = A^n(n)

Now we can pass large numbers into B just once - half the work (I checked!).

B(1000)=A1000(1000)=1000+1000=2000B(1000000)=2000000B(1000000000)=2000000000 \begin{aligned} B(1000) &= A^{1000}(1000) \ &= 1000 + 1000 \ &= 2000 \ B(1000000) &= 2000000 \ B(1000000000) &= 2000000000 \end{aligned}

We can see that the following property holds:

B(n)=An(n)=n+n=2n B(n) = A^n(n) = n + n = 2 \cdot n

Behold, multiplication!

Try as it might, "evil A" can't stop our new friend "B" from taking our numbers to great heights.

Aˇ(n)=n1B(n)=2nAˇ(B(10))=201=19Aˇ(B(100))=199Aˇ(B(5000))=9999 \begin{aligned} \check A(n) &= n - 1 \ B(n) &= 2 \cdot n \ \check A(B(10)) &= 20 - 1 = 19 \ \check A(B(100)) &= 199 \ \check A(B(5000)) &= 9999 \ \end{aligned}

But "evil B" can, stopping our numbers dead in their tracks.

Bˇ(n)=n2B(n)=2nBˇ(B(10))=202=10Bˇ(B(100))=100Bˇ(B(5000))=5000 \begin{aligned} \check B(n) &= \frac{n}{2} \ B(n) &= 2 \cdot n \ \check B(B(10)) &= \frac{20}{2} = 10 \ \check B(B(100)) &= 100 \ \check B(B(5000)) &= 5000 \ \end{aligned}

We'll need something stronger.

Slightly bigger steps

We have a function "B" which doubles a number.

B(1)=2B(99)=198B(500)=1000 \begin{aligned} B(1) &= 2 \ B(99) &= 198 \ B(500) &= 1000 \end{aligned}

We can apply "B" multiple times.

B(B(1))=B(2)=4B(B(B(10)))=80 \begin{aligned} B(B(1)) = B(2) &= 4 \ B(B(B(10))) &= 80 \end{aligned}

To shorten things, we can use our trusty friend, the superscript.

B(B(1))=B2(1)=4B(B(B(10)))=B3(10)=80 \begin{alignedat}{2} B(B(1)) &= B^2(1) &&= 4 \ B(B(B(10))) &= B^3(10) &&= 80 \end{alignedat}

This pattern may be a bit harder to spot, but we can handle it by expanding things a little.

B4(5)=2B3(5)=22B2(5)=222B(5)=22225=245 \begin{aligned} B^4(5) &= 2 \cdot B^3(5) \ &= 2 \cdot 2 \cdot B^2(5) \ &= 2 \cdot 2 \cdot 2 \cdot B(5) \ &= 2 \cdot 2 \cdot 2 \cdot 2 \cdot 5 \ &= 2^4 \cdot 5 \end{aligned}

The following pattern emerges:

Bn(5)=2n5 B^n(5) = 2^n \cdot 5

Or, more generally:

Bn(m)=2nm B^n(m) = 2^n \cdot m

Behold, exponentiation!

Just as before, we'll consolidate m and n by introducing a new function "C."

C(n)=Bn(n)=2nn C(n) = B^n(n) = 2^n \cdot n

Getting there

Our numbers are starting to grow pretty quickly:

C(3)=233=24C(10)=21010=10240C(100)=2100100=12676506 \begin{alignedat}{2} C(3) &= 2^3 \cdot 3 &&= 24 \ C(10) &= 2^{10} \cdot 10 &&= 10240 \ C(100) &= 2^{100} \cdot 100 &&= 12676506\mathellipsis \end{alignedat}

Passing 100 to our friend "C" produces 126765060022822940149670320537600, which is a whopping 33 digits in length. Switch the 100 to 1000 and we get:

107150860718626732094842504906000
181056140481170553360744375038837
035105112493612249319837881569585
812759467291755314682518714528569
231404359845775746985748039345677
748242309854210746050623711418779
541821530464749835819412673987675
591655439460770629145711964776865
421676604298316526243868372056680
69376000

Coming in at 305 digits. Pretty huge - larger than the number of particles in the universe - but still easily represented here in this article.

Additionally, our "evil B" from earlier is no match for us now.

Bˇ(n)=n2C(n)=2nnBˇ(C(10))=5120Bˇ(C(100))=633825(32 digits)Bˇ(C(1000))=535754(304 digits) \begin{aligned} \check B(n) &= \frac{n}{2} \ C(n) &= 2^n \cdot n \ \check B(C(10)) &= 5120 \ \check B(C(100)) &= 633825\mathellipsis \text{(32 digits)} \ \check B(C(1000)) &= 535754\mathellipsis \text{(304 digits)}\ \end{aligned}

Try as it might, "evil B" can only occasionally knock a single digit off our numbers.

A new challenger approaches, however, that can take them out using its secret weapon - the logarithm.

Cˇ(n)=lg(n)C(n)=2nnCˇ(C(10))=13.321Cˇ(C(100))=106.643Cˇ(C(1000))=1009.965 \begin{aligned} \check C(n) &= \lg(n) \ C(n) &= 2^n \cdot n \ \check C(C(10)) &= 13.321\mathellipsis \ \check C(C(100)) &= 106.643\mathellipsis \ \check C(C(1000)) &= 1009.965\mathellipsis \ \end{aligned}

Our numbers are barely able to escape the mighty logarithm. We'll need something stronger.

To new heights

We have a function "C" which raises 2 to the power "n" and multiplies it by "n"

C(n)=2nnC(3)=233=24C(10)=21010=10240 \begin{alignedat}{2} C(n) &= 2^n \cdot n \ C(3) &= 2^3 \cdot 3 &&= 24 \ C(10) &= 2^{10} \cdot 10 &&= 10240 \ \end{alignedat}

This function has a little sibling which does the same thing, but does not multiply by "n". It won't produce numbers quite as big, but will be a little easier for us to work with.

C˙(n)=2nC˙(3)=8C˙(10)=1024 \begin{aligned} \dot C(n) &= 2^n \ \dot C(3) &= 8 \ \dot C(10) &= 1024 \end{aligned}

We can apply "little C" multiple times.

C˙(n)=2nC˙(C˙(n))=2C˙(n)=22nC˙(C˙(C˙(n)))=2C˙(C˙(n))=22C˙(n)=222n \begin{alignedat}{2} \dot C(n) &= 2^n \ \dot C(\dot C(n)) &= 2^{\dot C(n)} &&= 2^{2^n} \ \dot C(\dot C(\dot C(n))) &= 2^{\dot C(\dot C(n))} \ &= 2^{2^{\dot C(n)}} &&= 2^{2^{2^{n}}} \end{alignedat}

Just as before, we can use our trusty friend the superscript.

C˙5(n)=22222n\dot C^5(n) = 2^{2^{2^{2^{2^n}}}}

Repeated applications of "little C" result in these fairly alien "towers" of 2s. In particular:

C˙m(n)=2222nm copies of 2\dot C^m(n) = \underbrace{2^{2^{2^{\cdot^{\cdot^{\cdot^{2^n}}}}}}}_{\text{m copies of 2}}

Once again we can consolidate m and n:

D(n)=C˙n(n)=2222nn copies of 2D(n) = \dot C^n(n) = \underbrace{2^{2^{2^{\cdot^{\cdot^{\cdot^{2^n}}}}}}}_{\text{n copies of 2}}

Just as we removed the trailing end for "C", we'll remove the trailing n for "D" to simplify things.

C(n)=2nnC˙(n)=2nD(n)=2222nn copies of 2D˙(n)=2222n copies of 2 \begin{aligned} C(n) &= 2^n \cdot n \ \dot C(n) &= 2^n \ D(n) &= \underbrace{2^{2^{2^{\cdot^{\cdot^{\cdot^{2^n}}}}}}}{\text{n copies of 2}} \ \dot D(n) &= \underbrace{2^{2^{2^{\cdot^{\cdot^{\cdot^{2}}}}}}}{\text{n copies of 2}} \end{aligned}

These "towers of exponents" are referred to as "tetrations" and are typically represented using Knuth's up-arrow notation.

D˙(5)=22222=25 \dot D(5) = 2^{2^{2^{2^2}}} = 2 \uparrow \uparrow 5

They're bizarre-looking, and grow...really quickly. How quickly?

D˙(2)=22=4D˙(3)=222=16D˙(4)=2222=65536D˙(5)=22222=265536 \begin{alignedat}{2} \dot D(2) &= 2^2 &&= 4 \ \dot D(3) &= 2^{2^2} &&= 16 \ \dot D(4) &= 2^{2^{2^2}} &&= 65536 \ \dot D(5) &= 2^{2^{2^{2^2}}} &&= 2^{65536} \end{alignedat}

At just 5 items in, we're produced a number that is 19,729 digits in length. Much larger than anything we've seen so far, but still tangible. In fact, I can print this number at size 11 font with 1" margins in just 7 sheets of paper (about 3,000 digits per page).

a print preview showing the very long number (20035299...) with "Total: 7 pages"

Why stop there?

D˙(6)=222222=???\dot D(6) = 2^{2^{2^{2^{2^2}}}} = \text{???}

What is this number? Concretely, it's 2 raised to the giant number we just saw. How much larger does that make it?

While we could print D(5) on 7 pages of paper, we'll need 7 pages of paper just to print the number of digits in D(6). What if we wanted to print D(6) itself? We'll need about D(5) pages.

More specifically, we'll need D(5) / 3,000 pages, but D(5) is so massive the / 3,000 does absolutely nothing to it.

How about D(7)? We'll need D(5) / 3,000 pages to print its digits, and D(6) / 3,000 pages to print the number itself. There's a pattern here, but not one that translates well into physical sheets of paper. Simply put, the number's big.

In fact, our function generates numbers so big that "evil C" is quickly drowned by them.

Cˇ(n)=lg(n)Cˇ(D˙(2))=lg(22)=2Cˇ(D˙(3))=lg(222)=22Cˇ(D˙(4))=lg(2222)=222Cˇ(D˙(5))=lg(22222)=2222Cˇ(D˙(6))=lg(222222)=22222 \begin{alignedat}{2} \check C(n) &= \lg(n) \ \check C(\dot D(2)) &= \lg{(2^2)} &&= 2 \ \check C(\dot D(3)) &= \lg{(2^{2^2})} &&= 2^2 \ \check C(\dot D(4)) &= \lg{(2^{2^{2^2}})} &&= 2^{2^2} \ \check C(\dot D(5)) &= \lg{(2^{2^{2^{2^2}}})} &&= 2^{2^{2^2}} \ \check C(\dot D(6)) &= \lg{(2^{2^{2^{2^{2^2}}}})} &&= 2^{2^{2^{2^2}}} \end{alignedat}

Try as it might, "evil C" can only knock off a single item from our ever-growing tower of exponents.

A tower of exponents is a real force to be reckoned with.

But not big enough

We have a function "D" which generates a tower of 2s with a height of "n."

D˙(n)=2222n copies of 2 \dot D(n) = \underbrace{2^{2^{2^{\cdot^{\cdot^{\cdot^{2}}}}}}}_{\text{n copies of 2}}

We can apply this function to itself.

D˙(D˙(n))=D˙(2222n copies of 2)=2222(2222n copies of 2) copies of 2 \begin{aligned} \dot D(\dot D(n)) &= \dot D(\underbrace{2^{2^{2^{\cdot^{\cdot^{\cdot^{2}}}}}}}{\text{n copies of 2}}) \ &= \underbrace{2^{2^{2^{\cdot^{\cdot^{\cdot^{2}}}}}}}{(\underbrace{2^{2^{2^{\cdot^{\cdot^{\cdot^{2}}}}}}}_{\text{n copies of 2}})\text{ copies of 2}} \end{aligned}

In the previous section, we saw how D(n-1) dictated the number of digits for D(n). Well, D(D(n)) grows not on the level of exponents, but on the level of the number of exponents in the tower.

While D(6) was practically impossible to imagine, D(D(6)) is pure nightmare fuel. Let's continue.

Just as earlier, we can use a superscript to simplify things:

D˙m(n)=2222(2222() copies of 2) copies of 2}m times \left. \dot D^m(n) = \underbrace{2^{2^{2^{\cdot^{\cdot^{\cdot^{2}}}}}}}{(\underbrace{2^{2^{2^{\cdot^{\cdot^{\cdot^{2}}}}}}}{(\cdot^{\cdot^{\cdot}}) \text{ copies of 2}})\text{ copies of 2}} \right} \text{m times}

And we can consolidate m and n like so:

E(n)=D˙n(n)=2222(2222() copies of 2) copies of 2}n times \begin{aligned} E(n) &= \dot D^n(n) \ &= \left. \underbrace{2^{2^{2^{\cdot^{\cdot^{\cdot^{2}}}}}}}{(\underbrace{2^{2^{2^{\cdot^{\cdot^{\cdot^{2}}}}}}}{(\cdot^{\cdot^{\cdot}}) \text{ copies of 2}})\text{ copies of 2}} \right} \text{n times} \end{aligned}