In this article, we will cover Graham's number, a famous very large number devised by Ronald Graham.
The regular Graham's number
Graham's number was devised as the upper-bound to the following problem in Ramsey theory:
Let N* be the smallest dimension n of a hypercube such that if the lines joining all pairs of corners are two-colored for any n ≥ N*, a complete graph K4 of one color with coplanar vertices will be forced. Find N*.
In a 1971 paper, Graham wrote a proof that the answer exists, and devised an upper bound of F^7(12), where F(n) = 2^^^...^^^3 with n arrows. Martin Gardner found this number difficult to explain, and so he devised an easier-to-explain upper bound which was proven in an unpublished 1977 paper. This upper-bound would become known as Graham's number.
Graham's number is computed in the following way: start with 3^^^^3 (3 hexated to 3), and call this Step 1. Now have 3^^^^3 arrows between 3s, and call this Step 2. Continue until you reach Step 64.
3^3 is just 27, which is still within the range of everyday numbers. 3^^3 is 7,625,597,484,987, which is quite astronomical, but can still be compared to real-world values. 3^^^3, though, as you may remember from the up-arrow article, is a power tower of 7,625,597,484,987 3s! And no, 3^^^^3 is not a power tower of 3s with 3^^^3 terms (that is only 3^^^4), but rather, start with 3 (call that Stage 1), then have a power tower of that many 3s, which is 7,625,597,484,987 (call this Stage 2), and keep iterating the power tower height until -- wait for it -- Stage 3^^7,625,597,484,987. As dizzying as that may seem, 3^^^^3 is vanishingly small compared to the next term in the sequence defining Graham's number:
G2 = 3^^^^^^^^^^^^^^^^^...^^^^^^^^^^^^^^^^^3 w/3^^^^3 ^s
Whoa! We already saw how G1 (with 4 arrows) is incomprehensibly huge, but G2 has that many up-arrows! Then, we have to feed back the number of arrows 62 more times!
The last digits of Graham's number can be found quite easily because it is simply an unfathomably large power tower of threes evaluated top down. To find what the last digit is, we will first take a look at powers of 3. The last digit of a power of 3 falls into the following repeating pattern: 1, 3, 9, 7. We can narrow it down further by observing that 3^N ends in 9 or 1 when N is even, or it end in 3 or 7 if N is odd.
In 3^(3^N), the exponent is always odd being a power of 3, so 3^3^N ends in either 3 or 7. The tens digit of a power of 3 is always even so a double exponential of 3 is of the form 20n + 3 or 20n + 7, which means it leaves a remainder of 3 when divided by 4. And, 3^n ends in ...7 if n is of the form 4n + 3, and so we have just proven that any number of the form 3^(3^(3^N)) including Graham's number ends in a 7.
We can also easily prove the last two digits of Graham's number. We already know that being a power of 3 it must have an even tens digit, which already rules out the tens digit being 1, 3, 5, 7, or 9. Since Graham's number is of the form 3^3^3^3^N, the exponent 3^3^3^N also ends in ...7 and must have an even tens place digit, and 3^7 = 2187. Since 3^20 ends in ...01, multiplying 3^7 by any power of 3^20 will not have any effect on the last two digits. Thus, 3^3^3^3^N will always end in ...87.
Below are the last 2000 digits of Graham's number (or of any power tower of more than 2,000 3s, such as 3^^^3 and all of the steps in Graham's sequence G1, G2, G3, ..., G63).
.................................................................................................................................14675412317888384738009343344165376733605639874152683883713570219486507495966616743619293364588499805610069710479310067941520844536138309110216300174376549196848839204372584196015037847845160671512017198801157547084883939593053650556078872159994750221442214834826814478727073100136553738357774609850586601264007612942335232625531330739420520078395477497625541118998597728808159458657528099886346722334769804780146302789353612329312586963866559329949214911489134763214665431430327265694776188950386753837203350803435869003867421136731651723621132562479975067702942357050569113050659743526552565536542768895266360391135992668989734244822601493574507744556050638326609473542254360350867485534248461062730568553479479128201952057764356476946631666382295000482800518276153635138000943232486790210617024259440292094849419545367418064519308105163357496871638118822504114501587037019405680648005022576853380553030518336809127181149081753948430026808410437955614810483158354472108503840767238233753543331110316978901699965907036875647695714199517294684058268271081207938885760678089057660597351282040660918730710848399211311795791808916067302977686873493263803825518970122110534818861415848748519200985261065252039482322073711493410839168737854403798603368448472052729248390757866617805529414157119366603081892881936678774148231780172812693498573578327095075857659197494703919315296759666923404880302362447049103531780908226116746950774641912877282443305832395092525499355092526168572459565741317934416750148502425950695064738395657479136519351798334535362521430035401260267716226721604198106522631693551887803881448314065252616878509555264605107117200099709291249544378887496062882911725063001303622934916080254594614945788714278323508292421020918258967535604308699380168924988926809951016905591995119502788717830837018340236474548882222161573228010132974509273445945043433009010969280253527518332898844615089404248265018193851562535796399618993967905496638003222348723967018485186439059104575627262464195387
Little Graham
Little Graham (alternatively the Graham-Rothschild number) is a number that was actually the upper bound to the solution of Graham's problem, which was given in a 1971 paper. It is equal to 2^^^^...^^^^3 where the number of arrows is 2^^^^...^^^^3 where the number of arrows is 2^^^...^^^3 where the number of arrows is 2^^^...^^^3 where the number of arrows is 2^^^...^^^3 where the number of arrows is 2^^^^...^^^^3 where the number of arrows is 2^^^^^^^^^^^^3.
We can similarly compute the last digits of this number, as it is an unfathomably large power tower of 2s. First of all we know the last digit is 6 since 2^(2^n) is always a power of 16 for n > 1, and the last two digits are 36 since a power tower of 2s is 2 to the power of a power of 16 if the tower has at least four 2s (2^16 ends in 36, and 36^16 also ends in 36).
Below are the last 1500 digits of Little Graham.
...411007306795766452169059948546984295084677954897147419414424584626135406203311924883352603516638251554628103101148399174681765128725488709395054914768887360790515159482994471285871442041782981051320847138192043888693789338156838860819833987993763076872163876555134739036840488341774253095066634733686297786918919338729260483567876557205804416717502686383259946364075013595547226506200286806464633121047113923501017404622599741520147391330705015300421684067455404821052440528969338781542842721926582686452534126161065407885742400782723207815297543605946147650094389896258515692489298997259791546185349312851385124646335712891813075552585686218748385572790702357023000477900832481664664639629381194362697236973858100812558516375764382111286275124759698067406126529903696708918369779391097965534660253856921246017664146328884328237763538275553531946074883722400053739215628121237852888212099277956138800258050803647824297753686050106977780463952098075388313636151792213947261538720108872408473827009994902503388258698462805689084243927947858473496362865556720247236103821828175132653517811874234624469295321325508674808828319636559141189838590864032603899870131537628336658436847486191414440397801867199446440553402402435833022281121378836687865256680756780796573298891689086155684839595553654091626099604299269691927189062503623574424769420495363221080797961763483968145105115173575459243654693520017384422568887190225094017989855389270912121282841628624570145528696872600159853338098615075353432948736
Graham-Conway Number
The Graham-Conway number is defined the same as Graham's number, except with 4s instead of 3s. Unlike the other two versions of Graham's number, this number can be expressed exactly in BEAF as {4, 65, 1, 2}. Conway himself stated that Ronald Graham had originally defined Graham's number with 4s instead of 3s.
This version of Graham's number has a particular elegance, as the iteration starts with 4 arrows between the 4s, and the number of steps is 64 = 4^3.
Its last digits are ...22302555290411728896.
Going beyond Graham
In this section, we will cover attempts to extend beyond Graham's number.
Kudi-Chan's number was a retort to Graham's number that someone on the Internet made up, which is defined as G^^^^^^^^^^^^^^^^...^^^^^^^^^^^^^^^G where the number of ^s is G^^^^^^^^^^^^^^...^^^^^^^^^^^G where the number of ^s is G^^^^^^^^^^^...^^^^^^^^^^^G ... ... ... where the number of ^s is G^^^^^^^^...^^^^^^^G where the number of ^s is G^^^^G, and where there are Graham's number of steps. Although this isn't a true naive extension by the spirit of the law (it is greater than GG64), it still is a naive extension in that it extends upon Graham's number in a way that is obvious and doesn't add anything new to the large number discussion.
Kudi-Chan's number can be shown to be between GG64 + 63 and GG64 + 64. Computing last digits of this number is the same as computing last digits of Graham's number, only with the last digits of Graham's number as the "radix" value instead of 3. The last 27 digits are ...480910066728082531703617603. These are the same digits that end things like (3^^50)^^50 (the geeggeel), (3^^^3)^^^3, (3^^^^3)^^^^3, or even G^^^^G.
Aarex's Graham Generator is a function that Aarex Tiaokhiao defined to extend beyond Graham's number, defined like so:
Forcal(n) = Forcal1(n) = GForcal_1(n-1)
Forcal#(0) = 1,000,000
Forcal1,b,#(n) = Forcal@,Forcal_@,1,b,#(n-1),b-1,#(1)
The forcal is equal to G1,000,000. In Aarex's Graham Generator, if N is GM, then graham N is GM+1. We could generalize this to: graham N = 3^^^...^^^3 with N ^s. Thus graham one = 27, graham two = 7,625,597,484,987, graham three = 3^^^3, graham four = 3^^^^3 = G1.
But in the next two articles, we will cover notations powerful enough to take us way, way beyond Graham's number...
NEXT >> Chained Arrow Notation