# Big Numbers

## Some Very Big Numbers

**Googol **= 10^{100} = 10 000 000 000 000 000 000
000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000
000 000 000 000 000 000 000 000 000.

The number of particles in the universe is less than a googol.

**Googolplex** = 10^{googol} = 10^{10100} (=
10^10^100).

**100 factorial** = 100! = 1 x 2 x 3 x ... x 100 = 9.3326...
x 10^{157} =

93 326 215 443 944 152 681 699 238 856 266 700 490 715 968 264 381 621
468 592 963 895 217 599 993 229 915 608 941 463 976 156 518 286 253 697
920 827 223 758 251 185 210 916 864 000 000 000 000 000 000 000 000.

Can you figure out why 100 factorial ends with 24 zeros?

**Skewe's number:** In 1933, Stanley Skewes used the number 10^{101034} (=
10^10^10^34) in a proof involving prime numbers. G. H. Hardy said it was "the
largest number which has ever served any definite purpose in mathematics".

**Graham's number:** In 1971, Ronald Graham used a much larger number
in a proof involving combinatorics. The number is so large that it takes
a page just to describe how to write the number. Graham's number, G, is
the 64th term in a rapidly-growing sequence denoted by g(n) (in other words,
G = g(64)). Just the first term of the sequence, g(1), is incomprehensibly
large. Martin Gardner called it "the
largest number ever used in a serious mathematical proof".
The Guiness Book of World Records listed it as the largest useful number.

**TREE(3):** In or before 2006, Harvey Friedman introduced
the function TREE(n), a rapidly-growing sequence involving, you guessed
it, trees. The first terms are TREE(1)=1 and TREE(2)=3. But then it explodes,
TREE(3) is incomprehensibly larger than Graham's number. Friedman later
introduced even more rapidly growing functions, SCG(n) and SSCG(n), related
to subcubic graphs.

## Tetration

Multiplication is just repeated addition: for example, 2 x 3 = 2 + 2 +
2. Exponentiation is just repeated multiplication: for example, 2^{3} =
2 x 2 x 2. But, what is repeated exponentiation called? It is called tetration.
For example, 2 tetrated to 3, represented as ^{3}2, is equal to
2^{22} = 2^2^2 = 2^{4} = 16. The word
"tetration" comes from "tetra" (meaning "four")
because it is the fourth operation in this series: addition, multiplication,
exponentiation, tetration.

Tetration of even quite small numbers produces extremely large numbers. This may be why it is not very useful in practice. Mathematicians and scientists almost never use tetration, and probably a majority of scientists have never even heard of tetration.

Example tetrations:

^{2}2 |
= | 2^{2} |
= | 2^{2} |
= | 4 |

^{3}2 |
= | 2^{22} |
= | 2^{4} |
= | 16 |

^{4}2 |
= | 2^{222} |
= | 2^{16} |
= | 65536 |

^{5}2 |
= | 2^{2222} |
= | 2^{65536} |
= | a big number with thousands of digits |

^{2}3 |
= | 3^{3} |
= | 3^{3} |
= | 27 |

^{3}3 |
= | 3^{33} |
= | 3^{27} |
= | 7 625 597 484 987 |

^{4}3 |
= | 3^{333} |
= | 3^{7625597484987} |
= | a big number with trillions of digits |

^{2}4 |
= | 4^{4} |
= | 4^{4} |
= | 256 |

^{3}4 |
= | 4^{44} |
= | 4^{256} |
= | 13 407 807 929 942 597 099 574 024 998 205 846 127 479 365 820 592 393 377 723 561 443 721 764 030 073 546 976 801 874 298 166 903 427 690 031 858 186 486 050 853 753 882 811 946 569 946 433 649 006 084 096 |

^{2}5 |
= | 5^{5} |
= | 5^{5} |
= | 3125 |

^{3}5 |
= | 5^{55} |
= | 5^{3125} |
= | a big number with thousands of digits |

## Beyond Tetration

The next operation beyond tetration is called pentation. Pentation is repeated tetration. You can imagine how big those numbers must be!

To write bigger numbers, people have invented new notations to represent tetration, pentation, hexation, and beyond.

Knuth's up-arrow (↑) notation:

a↑b | = | a↑^{1}b |
= | a^{b} |
exponentiation |

a↑↑b | = | a↑^{2}b |
= | ^{b}a |
tetration |

a↑↑↑b | = | a↑^{3}b |
pentation | ||

a↑↑↑↑b | = | a↑^{4}b |
hexation | ||

etc. |

Reading about these notations is fun and mind-bending. Search for these:

- Knuth's up-arrow notation
- Hyper-operations
- Ackermann functions
- Steinhaus-Moser notation
- Conway's chained arrow notation
- Jonathan Bowers' extended operators
- Fast-growing hierarchy

## Beyond Computable Numbers

Bigger still are "non-computable" sequences of numbers such as the Busy Beaver numbers.

Be forewarned, the following paragraphs involve some very abstract concepts. I will merely mention these concepts here, not attempt to explain them. I don't fully understand them myself. My only aim is to give you a taste for these huge numbers.

First, you should know that Turing machines (invented by Alan Turing)
are theoretical computers that simulate real computers. Each Turing machine
has a built-in finite-state computer program and an infinitely long tape.
By definition, anything that can be computed may be computed on a Turing
machine. Also, you should know that Turing proved that it is sometimes *impossible* to
decide whether a given Turing machine will run forever or eventually halt
(this is called the halting problem).

The mathematical operations above, such as tetration, are all computable
on a Turing machine. However, there are other well-defined but non-computable
sequences of numbers that grow faster than *any* computable sequence
of numbers.

The Busy Beaver sequence is one such explosive sequence. A Busy Beaver is a Turing machine that eventually halts but runs for more steps than most other Turing machines of the same number of states. The Busy Beaver function, BB(n), gives the maximum number of steps run by the Busiest Beaver with n states. But only some of these numbers can be determined because of the undecidablity of the halting problem. The first few Busy Beaver numbers are known: BB(1) = 1, BB(2) = 6, BB(3) = 21, BB(4) = 107, and BB(5) = 47,176,870. But BB(6) may be uncomputable, so mathematicians may never know how big it is!

If you really want to understand these difficult concepts, you'll need to read up on it elsewhere.

## Infinity, ∞

Georg Cantor showed that there are many levels of infinity: some infinities are larger than other infinities. He defined two infinite sets to be the same size if there is a way to arrange the members of the first set in one-to-one correspondence with the members of the second set. You might expect that the infinity of positive integers {1, 2, 3, ...} to be twice as big as the infinity of even positive integers {2, 4, 6, ...}, but these two infinities are the same size because they can be put in one-to-one correspondence like this: 1 → 2, 2 → 4, 3 → 6, etc.

Cantor proved that the infinity of real numbers is greater than the infinity of integers. The integers are countably infinite, but the real numbers are uncountably infinite. No matter how you try to arrange the real numbers in one-to-one correspondence with the integers, you'll always have more real numbers than integers. Cantor's ingenious "diagonal proof" is short and sweet. Here's the gist of the proof. First, imagine listing all real numbers between 0 and 1 in any order you choose. Number the list with all the positive integers in order, 1, 2, 3, etc.

Now construct the real number X by choosing all the digits on the diagonal as shown (X = .8731...). Then construct the real number Y by changing every digit in X to any other digit (for example, Y = .9842...). Y differs from every real number on the list by at least one digit, so Y is a real number that is not on the list. Therefore, the infinity of real numbers must be greater than the infinity of positive integers. To prove it for all integers, positive and negative, simply renumber the list with all integers in this order: 0, 1, -1, 2, -2, 3, -3, etc.

Mathematicians have explored levels of infinity beyond Cantor's infinities.

References

- David Wells.
*The Penguin Dictionary of Curious and Interesting Numbers* - Martin Gardner. "Mathematical Games."
*Scientific American*. Nov. 1977. (Graham's Number) - Rudy Rucker.
*Infinity and the Mind* - Robert Munafo. "Large Numbers." Web.
- Scott Aaronson. "Who Can Name the Bigger Number?" Web.