Talk:Graham's number/Archive 1

Archive 1

Archive 2

Archive 3

Digits

I rather like the listing of the last ten digits; it makes the number seem more concrete somehow. Are there any similar tricks we could do to get the first 10 digits? Yours hopefully, Agentsoo 09:34, 29 July 2005 (UTC)

Not by any method I know of, but then again, I don't know much. A method to calculate the first ten digits may exist, but if it did, it would certainly be a lot more complicated. Calculating the last digits of the number is quite simple (as the article says, elementary number theory) using modular arithmetic. The powers of the number can go higher and higher but the final digits will cycle, so it is possible to work out. Calculating the first digits would be much more difficult, if possible at all. -- Daverocks 10:12, 8 August 2005 (UTC)

Number of digits

How many digits does this large number have?? 66.32.246.115

This large number has a large number of digits. ;) Okay, take the common logarithm of Graham's number, round it down to the nearest whole number, and then add 1. That's the number of digits. I'd write it out in full for you, but there aren't enough particles in the known universe... :) -- Oliver P. 00:26, 9 Mar 2004 (UTC)

So how about the number of digits of THAT number (namely, the number you are saying you'd write down)??

How many times would you have to take the logarithm of the number acquired in the previous step (starting with Graham's number) before you get a number that can be written using the particles in the known universe? :) Fredrik 00:37, 9 Mar 2004 (UTC)

Even the number of times you take the logarithm, to get a writeable numbers, is too large to write. That is, you don't just take a logarithm once, or twice, or even a million times; if you took the logarithm $2^{10^{80}}$ times (about as many as you could write with all the particles in the universe) you still wouldn't be even in the ball park of being able to write out the result - even if you had any particles left over to do it 8^) In fact, even the number of times you had to take the logarithm, is so large that the number of times you had to take its logarithm, is too large to write - and so on, and so on, 65 layers deep... Securiger 16:49, 3 May 2004 (UTC)

I don't see any way to visualise the magnitude of the number.... my only conclusion is 'whoa this is large'. Can't we find some kind of magnitude comparison to help out to fathom G? — Sverdrup 00:42, 9 Mar 2004 (UTC)

Well, if you'll allow me to define numbers in O notation, then Graham's number is O(A⁶⁴). This grows faster than exponentiation, iterated exponentiation, iterated iteration of exponentiation, etc. So Graham's number simply cannot be written this way, or any related way. Conway's chained arrow notation, however, is sufficient to write Graham's number. --67.172.99.160 02:35, 19 March 2006 (UTC)

'Sides, this oughtn't desterb us any more'n Pi does. --VKokielov 00:36, 4 February 2007 (UTC)

Pi is infinitely specific; I can still round it to 3. The closest I can come to visualizing Graham's number is ∞-1 (i.e. less than ∞, but still more than I could ever even hope to imagine). --WikiMarshall 06:17, 26 June 2007 (UTC)

Think of a number, any number. Is it even bigger than G? If you picked randomly, almost surely yes. Graham's number is way, way, smaller than infinity. Feezo (Talk) 08:55, 26 June 2007 (UTC)

Impossible. You can't pick a random natural number in such a way that every natural number is equally likely. There is no uniform probability distribution over unbounded sets. A similar, but mathematically legitimate, way to make the point is to say that nearly all of the natural numbers are larger than Graham's number. Maelin (Talk | Contribs) 09:24, 26 June 2007 (UTC)

I don't think that is mathematically legitimate to say nearly all natural numbers are larger either. It's using the word nearly to compare a finite quantity to infinity. Now, it'd be nice to think that since Graham's number is so obnoxiously large, that it's nearer to infinity, but infinity doesn't work that way. Fulvius (talk) 07:39, 30 October 2008 (UTC)

Given any positive number n, the number of naturals that are greater than n is infinite, while the number of naturals less than n is simply n (including 0). So it is logically correct to say that nearly all natural numbers are larger than any given n, i.e., all but n of them are larger than n. | Loadmaster (talk) 17:42, 11 December 2008 (UTC)

Is there anybody who can even comprehend this? —Preceding unsigned comment added by 63.230.49.232 (talk) 19:15, 5 October 2007 (UTC)

That depends on how you define 'comprehend'. Nobody can grasp the real magnitude of this number, not even Graham himself, but maybe some mathematicians are able to understand what's involved when you deal with such numbers. That number just happened to have a certain property that made it useful for that proof, but it could well be that it is totally useless for any other purpose, because it's not like you could start calculating stuff with it or even analyze it. Normal people like me can just say "Wow!" and have to accept the fact that we simply don't understand and will never succeed in doing so.83.79.48.238 (talk) 18:04, 6 February 2008 (UTC)

What makes the largeness of the number interesting is the way that it is defined using the up-arrow notation in iteration, i.e. chained-arrow notation, where the result of each tier becomes the number of arrows in the next tier. Seeing as 3^^^^3, the very first of 64 tiers, is already incomparably larger than a googolplex because each single arrow iterates a whole new dimension of stacking exponents, the second tier then has this --much larger than a googolplex-- number of arrows. That's only the second tier; then, the absurd result of that calculation becomes the number of arrows for the third tier. At this point, it would seem almost arbitrary whether there are 3 tiers, or 64, or Graham's number of tiers; keep in mind that each and every single additional arrow vastly enlarges the result in iteration. Fulvius (talk) 07:39, 30 October 2008 (UTC)

• Perhaps this ought to go elsewhere, but why 64? And why was this number chosen, just because it was unbelievably large and the answer must be less than it (and where did the 6, later refined to 11 come from?), or because it made some sort of sense? I guess it would help if I understood what the problem was asking... Mavrisa (talk) 23:28, 28 October 2009 (UTC)

What makes this number remarkable was that it was used in a legitimate proof. Ronald Graham answered the question given in this article with this least upper bound, and technically could not prove the actual solution was less than it, only that it was less than or equal to it. That is, we could not, at that point, say that G-1 was an upper bound, because it was technically possible that the actual solution was exactly G. As it turns out, this upper bound vastly overestimated the actual size of the number, which is no surprise to anybody, and we now have a much smaller upper bound. But for a while, this was the best upper bound anybody had proved. How Graham went about proving this, I have no idea, as I have no education in Ramsey theory.

The lower bound was proven separately by different mathematicians, and for a while strong evidence suggested that the solution was in fact 6. This evidence turned out to be wrong, however, as it was later proven that the solution was at least 11, and probably much greater.

As it stands, this problem still has not been solved exactly, although the upper bound has been improved to a somewhat more reasonable (though still enormous) value, and the lower bound has been improved to 11. Thus, Graham's Number has only historical (and nostalgic) significance. Eebster the Great (talk) 01:49, 29 October 2009 (UTC)

The article states that "the best known bounding estimate for the solution N* is 11 ≤ N* ≤ G. That ought to be corrected to reflect the business about this G being the larger bound published by Martin Gardner and branded "Graham's number". EDIT: Hmmm... The situation is somewhat odd, since the number G was never published by Graham, but only by Gardner (who attributed it to Graham). If we give precedence to what Graham himself published, then it's his bound N (which is less than G) that's the best "known" upper bound. But for now, I propose leaving the article as-is.

r.e.s. (talk) 16:28, 30 October 2009 (UTC) (Edited my comment.)

I've now edited the article in an attempt to reflect this situation as best we know it. I suggest the recent Talk section "Why use G if N is a better bound?", or the older section "Martin Gardner's version vs. Graham's published version", for any further discussion about this.

— r.e.s. 15:02, 24 November 2009 (UTC)

An amusing exercise for the student

Obviously Graham's number is divisable by three, and hence not prime. And since all powers of three are odd, obviously Graham's number minus one is even, and hence not prime. Question: is Graham's number minus two prime? Prove your result. Securiger 16:49, 3 May 2004 (UTC)

• So, Graham's number is odd? 130.126.161.117 20:09, 19 October 2007 (UTC)

  Yes, that can be proven. An integer is odd if it has no 2's in its prime factorization. Graham's number's prime factorization is 3^(huge number). Georgia guy 21:13, 19 October 2007 (UTC)

• Securiger, I know enough to know that Graham's number minus 2 is not prime. Given that it is a number of the form 3^3^3^3^3^3^3^3... with at least 2 3's, its final digit is a 7. A number ending in 7 will end in 5 if you subtract 2, and apart from the single digit 5, a number ending in 5 is not prime because it has 5 as a factor. Therefore, Graham's number minus 2 is not prime. And, Graham's number minus 3, which is even, is not prime. Georgia guy 22:26, 8 Mar 2005 (UTC)

Interesting excercise, but I don't quite follow this. How do you prove that $3\uparrow \uparrow n$ for $n>1$ ends in a 7? It's clear to me that if you take the last digit of the sequence $3^{0},3^{1},3^{2},\ldots ,3^{n}$ you get the sequence that is the infinite repetition of {1, 3, 9, 7}, so $3\uparrow \uparrow 3=3^{3^{3}}=3^{27}$ must end with a 7, which is simple modulo math. But how do you continue from there? —Preceding unsigned comment added by 83.79.48.238 (talk) 18:48, 6 February 2008 (UTC)

All 3^n where n is odd will become evenly divisible by 4 if you add 1. All 3^n where n will become divisible by 4 if you add 1 (3^3, 3^7, 3^11, 3^15) ends in a 7. I know enough information to show that Graham's number ends in a 7 and its next-to-last digit is even. Georgia guy (talk) 19:25, 6 February 2008 (UTC)

Wow

I tried figuring out just how big this number is, and my mind blew a gasket when it got to the 4th Knuth iteration. Yikes. I'm glad there's only 1e87 particles in the universe, otherwise some wacko would already be trying to write it out. --Golbez 06:53, Sep 3, 2004 (UTC)

• No. g₁ is too big to "figure out" in any sense of the word. Even if this wacko could write it out as a power tower with every particle in the universe being a 9 in a reasonably small amount of time, he wouldn't come close to g₁. Hopefully just from that comparison you can tell that you can forget all about g₂. Mavrisa (talk) 01:50, 28 October 2009 (UTC)

Operation needed for Graham's number

Recall from the above the Graham's number is to large to visualize simply with the help of tetration. Try the question "What operation is needed to visualize it??" Please highlight it in the list below, defining each operation as being related to the previous one the way multiplication is related to addition.

1. Addition
2. Multiplication
3. Exponentiation
4. Tetration
5. Pentation
6. Hexation
7. Heptation
8. Oktation
9. Enneation
10. Dekation
11. Hendekation or above

66.245.74.65 23:51, 30 Oct 2004 (UTC)

None of these are even close to sufficient. Regular exponentiation requires 1 Knuth arrow to be represented, and dekation requires 8. Dekation in itself is a very powerful operator that produces large numbers. But for every layer of the 65 layers that Graham's number goes further into, what happens is that the number of arrows is equal to the result of the previous step. $3\uparrow \uparrow 3=3^{3^{3}}=3^{27}=7625597484987$, so we have 7625597484987 arrows already. Which is much, much larger than dekation. The next step will have $3^{7625597484987}$ arrows, a gargantuan number. This is just the number of arrows. And we're doing this 65 times. -- Daverocks 07:42, 19 August 2005 (UTC)

Sorry, I have to correct a fact in my own statement here. You start with $3\uparrow \uparrow \uparrow \uparrow 3$, and this is the number of arrows required for the next step, and so on and so on (one does not start with $3\uparrow \uparrow 3$ as I stated above). -- Daverocks 12:12, 30 August 2005 (UTC)

Could you represent Grahams number as 3^⁶⁴3?

No. You've missed the recursive definition here. In the sequence, $g_{1}=3\uparrow \uparrow \uparrow \uparrow 3$. This is already a huge, huge number. Then, to make the next number, we put that huge number of up arrows between two threes, like this: $g_{2}=3\uparrow ^{(g_{1})}3=3\uparrow ^{(3\uparrow \uparrow \uparrow \uparrow 3)}3$. The number of uparrows in any $g_{i}$ is equal to the actual number $g_{(i-1)}$. So $g_{1}$ is huge, but $g_{2}$ has $g_{1}$ up arrows (which makes it really, really big - much, much bigger than $g_{1}$), and then $g_{3}$ has $g_{2}$ up arrows, etc. Maelin (Talk | Contribs) 08:26, 28 December 2006 (UTC)

Comparison

Is it bigger than googol? Googolplex?

Yes. It is even bigger than googolduplex, googoltriplex, and even googolcentuplex, defining googol(n)-plex as the number 10^10^10^10^...10^10^10^10^googol where there are a total of n 10's. 66.245.110.114 23:55, 6 Dec 2004 (UTC)

Adding to that, one can easily find numbers larger than a googolplex, even though it is also unconceiveably large. However, $9^{9^{9^{9^{9^{9}}}}}$ is larger, and can be written with fewer symbols. Remember that a googolplex is $10^{10^{100}}$, which requires 7 symbols to be written down. The above-mentioned number only requires 6. -- Daverocks 10:30, 8 August 2005 (UTC)

BTW, isn't $9^{9^{9^{9}}}$ already larger than $10^{10^{100}}$ ? --FvdP 20:56, 19 August 2005 (UTC)

Actually, FvdP, you're probably right. -- Daverocks 12:05, 30 August 2005 (UTC)

Definately right in fact; stacking new power layers is much more powerful than incresing the numbers of lower layers. (which is why the procedure for G gets so very large very fast.) For example, $9^{9^{9^{9}}}=9^{9^{387,420,489}}$ which is clearly larger than $10^{10^{100}}$

Still informally but with more precision, here is another way to see it, by taking twice the logarithm on each side: $\log 9^{9^{9^{9}}}=9^{9^{9}}\log 9$ so $\log \log 9^{9^{9^{9}}}=9^{9}\log 9+\log \log 9\approx 9^{9}\log 9$, while similarly, $\log \log 10^{10^{100}}\approx 100\log 10$. There is (almost) no more dispute which is greater ;-) You see here how the actual numbers in the lower exponentiation layers just seem to evaporate and play no significant role in the proof. --FvdP 22:08, 23 December 2005 (UTC)

Is it bigger than a Googolplex to the power of a Googolplex, Googolplex times? - I mean that the "to the power of" is itself to the power of another Googolplex and so on, a Googolplex times. User:Mekhatronic —Preceding undated comment added 04:21, 9 May 2009 (UTC).

Of course it's bigger. The number you describe is just $X\uparrow \uparrow X$, where $X$ is googolplex. This number is bigger than $3\uparrow \uparrow \uparrow 3$, but much smaller than $3\uparrow \uparrow \uparrow \uparrow 3=g_{1}$ - G's much much smaller ancestor. Replacing 3 with googolplex doesn't really get you much further in this case. Basically, any number you can easily describe without using recursion would be insignificant compared to G. Owen× ☎ 13:13, 9 May 2009 (UTC)

Well, be careful with that last statement. n(4) and TREE[3] are obviously much larger than G, and they aren't defined using recursion. How about "The largest number definable in first order arithmetic using fewer than one googol symbols?" That number is big. You could probably also define larger numbers with the busy beaver function, although nobody knows how high you have to get. Even Moser's number, though much smaller than G, can easily be used to define a larger number by putting a two in a Mosergon (though I suppose this is recursion to some extent). And of course, you can easily define infinite quantities like $\omega$ and $\aleph _{0}$ without recursion.

But using elementary operators and relatively small integers certainly won't get you anywhere close to G, if that's what you mean. Eebster the Great (talk) —Preceding undated comment added 02:37, 11 May 2009 (UTC).

I reckon that it's fair to say: "if a googleplex is a millimetre, then Graham's Number is the universe" in terms of visualizing a linear number line Eugene-elgato (talk) 23:39, 10 June 2009 (UTC)

That's really not fair to say, though. The more important concept to get across is that no such visualization will ever get closer to Graham's number to any meaningful extent. I could also say "If ten is a centimeter, then a googolplex is a meter," but you wouldn't say that was a useful visualization, either, for the simple reason that it is inaccurate. Even if g₆₃ were a Planck length, the observable universe would not be close enough to g₆₄=G for it to be a useful method of approximation. Eebster the Great (talk) 07:58, 11 June 2009 (UTC)

That statement is indeed wrong. If 10 is a centemeter, then a meter is 1000, not a googolplex. Georgia guy (talk) 13:04, 11 June 2009 (UTC)

"for the simple reason that it is inaccurate" That was his point. Comparing anything to G in the scale of our universe will be massively inaccurate, just as his example was. --Golbez (talk) 18:18, 24 June 2009 (UTC)

to visualize a string, it IS fair to say that if an atom were the solar system, then a string would be an atom. So what about then saying if a string were a googolplex, G would be the length of the universe? Actually, even if this isn't enough, I'm not sure what Golbez means, because if not a googolplex, then something like the Shannon number, from chess permutations etc....there's got to be some way of visualizing it. Eugene-elgato (talk) 19:35, 9 July 2009 (UTC)

These are all "small" numbers, in the sense that f(X)=log(log(log(X)))<3. Any ratio between real physical sizes will fall into this category. Whether it's atoms, strings, the universe or a can of beans, they all fall under f(X)<0.4. Googolplex gets you as high as 2. For g₁, G's miniscule relative, f(g₁) is a number whose description isn't much different from that of g₁ itself. In fact, the number of times you'd have to apply the log function to it to get a number you can describe with simple exponentiation is itself staggering. Owen× ☎ 20:04, 9 July 2009 (UTC)

notation

Are you saying that even if you used the notation like 10^10^100^100000000 etc, there isnt enough ink or hdd space in the universe to express graham's #? 69.142.21.24 05:20, 5 September 2005 (UTC)

That is correct. Graham's number is far too large to simply be expressed in powers of powers of powers. Even if one takes the exponentiation operator to a higher level, such as tetration or many (actually, an incomprehensible number of) hyper operators above this, it would still not be even close to sufficient to expressing Graham's number with all the matter in the known universe. -- Daverocks 12:32, 19 September 2005 (UTC)

I love that everyone is trying to conceptualize the number by comparing it to "large" numbers like a googlplex or the number of particles in the universe. :) One must understand the up-arrow notation to gain the needed insight. Fulvius (talk) 08:12, 30 October 2008 (UTC)

Largest number with an article

I assume from the above discussion that this is the largest number to have a serious Wikipedia article devoted to it. Is that correct? CDThieme 03:02, 8 October 2005 (UTC)

Well, the greatest integer. We have plenty of articles about infinite numbers, and Graham's number is finite. Factitious 19:51, 10 October 2005 (UTC)

Can numbers be infinite? I don't think so, a number is a number. Infinite is a concept. Rbarreira 19:24, 20 December 2005 (UTC)

See Aleph-null, for instance. Factitious 22:32, 21 December 2005 (UTC)

There are larger finite integers in math. In Friedman's Block Subsequence Theorem, n(4), the lower bound for the length of the string for four letters, is far, far larger than Graham's number.Mytg8 14:42, 4 May 2006 (UTC)

Numbers are concepts. -- SamSim 20:06, 17 January 2007 (UTC)

Indeed. We consider a complex number a number, even though it is certainly a different critter than an integer. Ordinals and cardinals simply extend our concept of "number" even further. And then there are matrices, tensors, and so on, which can also be thought of as different kinds of numbers. — Loadmaster (talk) 01:55, 25 June 2009 (UTC)

Years in Hell

Imagine being in Hell for a Graham's Number of years. (It's said that people stay in hell for all eternity...) If someone was taken out of Hell after that many years, what could they say and how would they feel? Think about and imagine this. --Shultz 00:15, 2 January 2006 (UTC)

Nonsense. The universe is only 13,700,000,000 years old, a number that can be written in comma format with only 4 periods of digits. Graham's number is far too large to write in comma form with even millions of such periods. Georgia guy 01:10, 2 January 2006 (UTC)

This reminds me of a scene in the 1976 Australian movie The Devil's Playground. The novelist Thomas Keneally played a priest who was leading young seminarians in a 3-day silent retreat, and he gave them a little spiel before the retreat began. He spoke about the length of eternity, and he likened it to a huge metal sphere, as large as the Earth, somewhere out there in space. Once every century, a small bird flies past and brushes the sphere lightly with its wing. When the sphere has been completely worn away by the action of the bird, eternity would hardly have even begun. The lesson presumably being, be good otherwise you're a very, very long time in Hell. Anybody care to work out how long this would take? Please state all your assumptions. This might be a hopelessly small approximation of the size of Graham's number, but it must be somewhere along the track. JackofOz 03:24, 19 May 2007 (UTC)

On 10 seconds' reflection, I realised that even if the bird removed only one elementary particle each time it flew past, that would still only add up, eventually, to the number of elementary particles in something the size of the Earth. The number of elementary particles in the Universe is way, way higher than that, and Graham's number is way, way higher again. So, it is indeed a hopelessly small approximation. Scrap the calculation. Unless you just want some mental exercise, that is. :) JackofOz 03:42, 19 May 2007 (UTC)

The 1970 short story "Been a Long, Long Time" by R. A. Lafferty uses essentially the same idea for a cosmic clock. See my web page for a discussion about such a device in relation to the Infinite monkey theorem. — Loadmaster (talk) 02:03, 25 June 2009 (UTC)

The movie scene mentioned above is evidently retelling an ancient illustration of the length of a kalpa in Buddhism.--r.e.s. (talk) 17:48, 26 June 2009 (UTC)

Shultz' proposition seems invalid to me, since 'hell' is a religious concept that is not necessarily bound to our universe. You'd have to define the concept 'time' in the context 'hell' first, which hardly seems possible in a meaningful way. And even if you do that, Georgia guy's reply is still invalid, because that defnition of 'time' will not be comparable to our universe's definition of 'time'. (Yes, I know that the bible as well as other sources have citations that hint at hell being bound to our universe (for example that there is sulfur in hell), however I believe those sources merely tried to explain the unknown in known terms in order to make it more graspable. I believe hell is not bound to (but still may or may not interact with) our universe.) —Preceding unsigned comment added by 83.79.48.238 (talk) 18:30, 6 February 2008 (UTC)

Spoken like a scientist. In response to the original questions, I'd propose: "That sucked a lot." and "Like shit."--Hawkian (talk) 21:55, 17 June 2008 (UTC)

Because ∞ > G > 0, even Graham number of years in hell means totally nothing in comparison to eternity in hell. 91.94.189.135 (talk) 11:07, 18 August 2008 (UTC)

If hell exists, it's got to be somewhere in the universe, right? The universe is just that: everything. Well, unless hell isn't made of matter (like, any type of matter), or if it isn't in the universe after all, won't the entire universe - including hell, if it's in the universe - decay in approximately 10^36 years? And any writable power of 10 is worthless in comparison to Graham's number. So, if hell is tied to the universe and made of matter, it is impossible to spend a Graham's number of years in hell - at least, as we know it. Besides, Graham's number is finite.

That said, if the thought of spending any number of years or eternity in hell is scary to you, think about how scary the same amount of time would be in nothingness. Clem (talk) 03:25, 25 April 2009 (UTC)

Letter

Since this is obviously too large a number to write down, is there a letter to represent it in common usage?

"Graham's Number" is used to refer to it.--Lkjhgfdsa 20:29, 19 April 2006 (UTC)

There's nothing like e or π. If context of the discussion is known one might use G. Kaimiddleton 07:50, 20 April 2006 (UTC)

Upper bound of something

You know with this nummer being so large, how on earth was it proven to be the upper bound of that question?

• Maybe even more specific: does anyone know where to find the proof. I can find a zillion articles about Grahams number, how big it is and why. But the proof itself I can not find. Is it available in public domain? Pukkie 07:37, 2 June 2006 (UTC)

It may important to note that you might have misunderstood the story- Graham's Number wasn't proven to be the upper bound of that question, the upper bound of the question was proven to be what became known as Graham's number.--Hawkian (talk) 21:58, 17 June 2008 (UTC)

• That's a good question. According to the magazine article that announced the discovery back in 1977, the proof was unpublished. As far as I know, it has never been published. Very odd. Of course, Friedman has never published his proof of n(4) either...  :-) Mytg8 15:48, 2 June 2006 (UTC)

Colloquial statement of the problem

Can someone clarify this for me? The problem connected to Graham's number is described as: "Take any number of people, list every possible committee that can be formed from them, and consider every possible pair of committees. How many people must be in the original group so that no matter how the assignments are made, there will be four committees in which all the pairs fall in the same group, and all the people belong to an even number of committees." What does this mean? I understand the first part, taking n people and listing all 2^n committees, and then considering all (2^n choose 2) pairs. I don't understand anything else except that all people are in an even number of committees. Thanks. :) CecilPL 20:57, 12 May 2006 (UTC)

• That's a tricky question, I find it hard to be both correct and coloquial. I'll give it a try:

"Take a number of people, list every possible committee that can be formed from them, and consider every possible pair of committees. Now assign every pair of committees to one of two secretaries. How many people must be in the original group so that no matter how the assignments are made there will always be a secretary with a group of four committees where all the people belong to an even number of these four committees." Pukkie 10:52, 7 June 2006 (UTC)

I do think that's better. Any one object to it replacing the description in the article? --Michael C. Price ^talk 08:19, 23 June 2006 (UTC)

There is a serious problem with the 'colloquial statement', both in its old form and in the new one. It yields only a necessary condition for the four points to be complanar, not a sufficient one. This means that, at least a priori, there is good reason to assume that a lower number is sufficient for guaranteeing a monochromatic 4-set satisfying the 'colloquial statement' than the original one.

I've tried to find the origin of the 'colloquial statement'. It is found also in the mathworld article on Graham's number, which refers to some popular articles I do not have access to. It also refers to the original article, in Transactions of the American Mathematics Society. I added a reference to this, but didn't find the 'colloquial statement' there. Could someone please search the source of it; since it is rather nice, it would prefer improvement to deletetion.

A short but technical explanation of the trouble: Adopt the article notation. Note, that there are 6 sub-2-sets of any given 4-set of vertices. Thus, let n=6, and choose the four vertices in such a way that each one of the six coordinates will be 1 in exactly one of these six 2-sets, and 0 in its complement. Explicitly, you may pick the four vertices A, B, B, and D with coordinates

(1,1,1,0,0,0), (1,0,0,1,1,0), (0,1,0,1,0,1), and (0,0,1,0,1,1),

respectively. This set does not lie in one plane; if you consider the vectors ${\overline {AB}}=(0,-1,-1,1,1,0)$, ${\overline {AC}}=(-1,0,-1,1,0,1)$, and ${\overline {AD}}=(-1,-1,0,0,1,1)$, you'll find that they are linearly independent. Thus it is not a 4-set of the kind Graham and Rotschild discuss.

On the other hand, if we give the 'colloquial' interpretation, we should consider A, B, C, and D as four committees with three members each, formed within a set of six people (one for each coordinate). If the six people are named a, b,..., f, then we find that A consists of a, b, and c, which we briefly may write as A=abc. Similarly, B=ade, C=bdf, and D=cef. Thus, each person is a member of an even number (namely 2) of the committees.

This is not so interesting for the case n=6, of course; but the construction could easily be extended to many millions of 4-sets, if e.g. n=30. JoergenB 18:54, 26 September 2006 (UTC)

You are right, I will delete the colloquial version. If someone has a good way to say 'in the same plane' colloquially we can put the corrected version back. Pukkie 08:20, 21 October 2006 (UTC)

But???

Think of this all hypothetically... What if one could create a Solar System-sized computer that was made ONLY to store Graham's number in exponential form. all calculations could be routed from a diffrent computer. can it be done? —Preceding unsigned comment added by Geobeedude (talk • contribs)

• No, it can't. Even the number of Knuth arrows is too large to be stored that way. --Ixfd64 18:23, 19 May 2006 (UTC)
• More to point, if I recall my calculations correctly, the number of digits reaches beyond the number of particles in the universe by the 4th iteration. So by the time you hit the 64th, ... well let's put it this way. Let's say you stored it in decimal (It would be binary, but let's go with this for simplicity). You need at least one particle for each digit, because that's how the computer's memory works. Even if it's so much as an electron in an electrical field, that digit has to be "stored" by something. So you would have to use the entire universe's worth of particles just to store the digits of the 4th iteration - let alone the 64th. You would need an unimaginably large number of *universes* to even begin writing the number down. --Golbez 08:12, 20 June 2006 (UTC)
  • No, even the first iteration, g₁ is greater than the greatest number storable using every particle in the universe as a binary digit. Think about it, look at that giant monster of a cross-cross-braced number the article states is equal to g₁, and take the trinary log of it. That's the number of trinary digits it takes to store it, so the number of binary digits neccessary is much greater. Now ask yourself, is that number, which is essentially indistinguishable from g₁ because it is so gigantic, greater than 10^80? I rest my case.
    • Indeed g₁ is way too large to represent by anything. I tried explaining it to a friend in order to wrap my own head around it (well, I say wraped my head around it. What does that entail? I have no idea.):
      Imagine a power tower of 3s (so 3^3^3^3^3^3^3... etc.) with 7625597484987 3's in it. Considering 3^3^3 is 7625597484987, the number that must result from THAT power tower is already mind blowing in itself. Take the result and call this insanely large number "k". Now imagine a power tower of 3s with k 3s in it. That's g₁. —Preceding unsigned comment added by Mavrisa (talk • contribs) 23:39, 27 October 2009 (UTC)
      • No, "a power tower of 3s with k 3s in it" is $3\uparrow \uparrow k\,\!$, whereas $g_{1}=3\uparrow \uparrow \uparrow k\,\!$. To see this, note that your k is $k=3\uparrow \uparrow 3\uparrow \uparrow 3=3\uparrow \uparrow \uparrow 3\,\!$ and that $g_{1}=3\uparrow \uparrow \uparrow \uparrow 3=3\uparrow \uparrow \uparrow 3\uparrow \uparrow \uparrow 3=3\uparrow \uparrow \uparrow k\,\!$.

— r.e.s. 14:23, 27 November 2009 (UTC)

In fact, all discussion in this thread up to this point except that talking about knuth's up arrow can replace "G" with "g₁" and still be essentially correct. Even this is far, far too great to begin comprehending in any normal sense. That is the size of the OPERATOR used in g₂... —Preceding unsigned comment added by 24.165.184.37 (talk) 03:20, 11 March 2008 (UTC)

Sorry, forgot to signEebster the Great (talk) 00:08, 9 April 2008 (UTC)

numbers larger than Graham's number

It seems that Graham's number is no longer the largest number used in serious mathematical proofs. See some of the work by Harvey Friedman, for example. He mentions numbers like n(4) and TREE[3]. [1] [2] Should we mention these numbers in the article? --Ixfd64 18:28, 19 May 2006 (UTC)

• Maybe but just mentioning them is a bit short. Also: I do not understand TREE[3]. How big is this in Conway chained arrow notation? Pukkie 11:36, 30 May 2006 (UTC)

I read the above papers some time ago. As I recall, this number can only be descibed with more than 2^1024 symbols in any notation.Mytg8 16:45, 20 June 2006 (UTC)

Well, you could create a new notation that asks for the number of symbols required in your case, couldn't you?? Georgia guy 16:49, 20 June 2006 (UTC)

What is n() or TREE()?

Well, we could try Jonathan Bowers' array notation. --Ixfd64 22:35, 21 June 2006 (UTC)

Actually, In Graham's and Rotschild's original article, they prove much more general statements. The Graham number estimate is just one of the first one deducible from their proof, out of an infinite series. JoergenB 18:05, 26 September 2006 (UTC)

According to the original 1977 Scientic American article that announced the number, Martin Gardner stated that the proof for what is called Graham's number was unpublished. AFAIK, the proof has never been published. I'm not familiar with that 1971 Graham and Rothschild paper; perhaps it was an earlier estimate but it's not the same number. A Usenet discussion of this topic-http://groups.google.com/group/sci.math/browse_thread/thread/3f2bec34954af48c/28b726a9fe028bcb?lnk=gst&q=%22graham%27s+number%22&rnum=3#28b726a9fe028bcbMytg8 04:24, 27 September 2006 (UTC)

I do not have access to the SciAm article, but certainly consider Graham's and Rotschild's as the original... When you write Martin Gardner stated that the proof for what is called Graham's number was unpublished, I hope you mean something like 'the proof of the fact that this number indeed is an upper bound'. (A number in itself does not have a proof, not even in Gödel's theory.) Does he really claim this to be unpublished; and doesn't he mention the G&R article Ramsey's theorem for n-parameter sets at all?

The reference is interesting; I'll try to analyse the relationship between the original G&R number and the Gardner-Graham one as soon as I get the time. The representations are different, but that doesn't automatically mean that the numbers are. Actually, as G&R define their estimate, it is a power of 2 rather than a power of 3, which does indicate that the numbers are not quite the same:-) However, even so, it would be a surprise if the older number was smaller, for obvious reasons. Thus, I'll have to correct my corrections; but we also have a potential candidate for a larger number than the GG one, from the horse's own mouth. JoergenB 23:03, 28 September 2006 (UTC)

As I wrote in the posting that began the cited sci.math thread in 2004, the upper bound published by Graham & Rothschild in 1971 is much smaller than the one that appears to have been strangely attributed to Graham by Gardner in 1977. It seems obvious that Gardner's was a misattribution unless Graham & Rothschild had it wrong in 1971 -- and afaik no publication has made that claim. (In fact, Exoo's 2003 paper refers to the 1971 value -- not Gardner's -- as "Graham's number".) But maybe it's best to just accept the popular misattribution, and continue referring to the so-called "Graham's number" by that name, even though it's apparently not Graham's at all. --r.e.s. (Talk) 00:45, 29 September 2006 (UTC)

The correct thing to do is of course to go through the proof of G&R, and deduce the estimate from that :-(. Also, there is a slight vagueness in their article; what they write is precisely (my emphasis) '... the best estimate for $N^{*}$ we obtain this way is roughly

$N^{*}\leq F(F(F(F(F(F(F(12,3),3),3),3),3),3),3).$'

Now, I do not know what 'roughly' means, without further investigations. I'll have to read the whole stuff, sometime, I fear.

Another question to you people who have the SciAm article: Could you please check whether the secretary parable is there, and if so, if there were other conditions added? 'Our' article is still defect, and I haven't yet got any reaction to my comment in the section on the colloquial statement of the problem (supra). It is clear that this cannot be left in an erroneous form, and I'd prefer a correction to a deletion. JoergenB 10:12, 29 September 2006 (UTC)

I have an old Xerox copy and here are some quotes from the SciAm article-"Mathematical Games";volume 237 pp 18-28 November 1977--if they'll help anything. The article is on Ramsey graph theory, author Martin Gardner, and is informal-as you would expect from a popular journal. He goes into some history of Ramsey Graphs, then p.24 brings up Ronald L. Graham, "...one of the nation's top combinatorialists...(who) has made many significant contributions to generalized Ramsey theory... unquote. Then a couple paragraphs later ...this suggests the following Euclidean Ramsey problem: What is the smallest dimension of a hypercube such that if the lines joining all pairs of corners are two-colored, a planar K_4 will be forced? ...The existence of an answer when the forced monochromatic K_4 is planar was first proved by Graham and Bruce L. Rothschild in a far reaching generalization of Ramsey's theorem that they found in 1970. *(the 1971 paper?)* (continuing) Finding the actual number, however, is something else. In an unpublished proof Graham has recently established an upper bound, but it is a bound so vast that it holds the record for the largest number ever used in a serious mathematical proof. End quote.

The 1971 G&R article indeed was 'received by the editors' 1970. Math articles may have considerable time lags.JoergenB 21:34, 29 September 2006 (UTC)

Gardner then proceeds to describe the usual description of the number using Knuth's arrows, starting with 3^^^^3, continued for 2^6 layers(as he terms it). Back to quote: It is this bottom layer that Graham has proved to be an upper bound for the hypercube problem, unquote. No mention of secretaries, committees, etc. But wait, there appears to be another, earlier, estimate :-)http://www.math.ucsd.edu/~fan/ron/papers/78_02_ramsey_theory.pdf p.11?Mytg8 19:41, 29 September 2006 (UTC)

Interesting! But this 'new old' G&R paper is markedly longer. Well, we have some reading to do, I guess. JoergenB 21:34, 29 September 2006 (UTC)

One more link- http://groups.google.com/group/sci.math.research/browse_thread/thread/dfe28ba0cb00f7bc/5ade381fadaf1485?lnk=st&q=%22graham%27s+number%22&rnum=12#5ade381fadaf1485 In this 2002 topic and response to Exoo, author tchow says he asked Graham himself about the number and Graham said the theorem was unpublished.Mytg8 15:03, 30 September 2006 (UTC)

I recently added a mention of numbers (like TREE(3)) that appear in connection with Friedman's finite forms of Kruskal's theorem. This seems appropriate to me, because TREE(3) is a specific number known to be far larger than G, and is explicitly involved in serious proofs. By this same criterion, I deleted someone's mention of the Busy Beaver function, because there's no citing of a proof involving a *specific* BB value that's known to exceed G. (But I misstated a parenthetical comment in saying that "a particular n for which BB(n) > G is not known" — of course BB(G) > G, for example, and I had in mind n that are not "large numbers"!) The largest lower bound I've seen for any particular BB(n) (with n not large) is in Dewdney's book, which states that Σ(12) ≥ 6x, where x is a power tower of height 167, consisting of 166 copies of 4096 topped by a 4 — miniscule compared to G. Has anyone seen a larger-than-G lower bound for some BB(n) (with n not large)?
r.e.s. (talk) 04:47, 27 June 2008 (UTC)

It seems worth mentioning here that S. Ligocki recently pointed out (in a section of the Busy Beaver article and its Talk page) that a paper by Green[1964] implies that $\Sigma (2k)>3\uparrow ^{k-2}3\quad (k\geq 2)\,\!$. E.g., this gives $\Sigma (12)>3\uparrow ^{4}3=g_{1}\,\!$, where g₁ is the first term in the sequence for Graham's number — which certainly makes the bound cited by Dewdney look very puny. Of course, for not-very-large values of k these lower bounds are all tiny compared to G. (I suppose an obvious question is "How many TM states are required to compute the function $f(n)=3\uparrow ^{n}3\,\!$?", so we could get a not-very-large known value of k for which Σ(k) > G.)
— r.e.s. 15:30, 25 November 2009 (UTC)

That is a question I'm very interested in right now. In fact I think that vast swaths of the fast-growing hierarchy could be implemented which would put Graham's number to shame. Glad to hear it interests other folks too :) Cheers, — sligocki (talk) 19:39, 25 November 2009 (UTC)

The point about the fast-growing hierarchy is no doubt correct. This is easy to see, because a not-very-long program (in just about any programming language) can be written to compute a function that dominates $f_{\Gamma _{0}}\,\!$, for example (e.g. Friedman's TREE); consequently, completely ignoring efficiency issues, it would be tedious but straightforward to convert such a program into a suitable TM that would not have a very large number of states.

— r.e.s. 16:14, 26 November 2009 (UTC)

Graham's number tower image

Isn't there a convenient way of expressing Graham's number by simply writing out the 64-layer arrow tower? That will knock some sense into those people.

The first layer is 3^^^^3, which denotes the number of arrows in the below layer, with that number (an insane number of arrows) denoting the number of arrows below that layer, and this recursive operations continues for 64 layers.

The number in the second layer is already way larger than the number of particles in the universe...

(And if i'm not mistaken, Graham's Number is the upper bound for the number of dimensions required for a standard hypercube, when its corners are 2-colored, forces a tetrahedron? (Grr...Wikipedia does not have an article describing the Ramsey graphs)Doomed Rasher 22:58, 3 October 2006 (UTC)

How large is 3^^^^3?

I've been trying to come to grips with Graham's Number and have been truly awestruck by how staggeringly, inconceivably huge it is. But it's obvious from the various questions that few people have any idea of the scale of it. I've tried working out some idea of 3^^^^3 but I can't get anywhere (probably due to my infamiliarity with Knuth arrow notation). How big is g₁? g₂? How many in the sequence can be represented in some kind of mainstream notation? -Maelin 11:52, 12 October 2006 (UTC)

Take a look at Ackerman_function#Ackermann_numbers where there is an example of 4^^^^4. Kaimiddleton 21:35, 14 October 2006 (UTC)

Oops, I notice there's an error there, currently. Look at this edit for a correct (though poorly formatted) version. Kaimiddleton 21:48, 14 October 2006 (UTC)

At least 3^^^3 is easier to picture. This would be 3^3^3...3^3 repeated 7625597484987 times. If you were to write this number using a centimeter for each "3^", it would reach about halfway to the sun. (Try entering "7625597484987 centimeters to AU" in Google.) --Zachm (talk) 02:02, 8 September 2008 (UTC)

question on notation

wouldn't $g_{n}=3\uparrow ^{g_{n-1}}3$ be the same as $g_{n}=3\uparrow ^{68}3$ ? —The preceding unsigned comment was added by 199.90.15.3 (talk) 17:42, 11 December 2006 (UTC).

No. Remember, the number of up-arrows in each term g_n is equal to the actual number, g_n-1. So we have $\textstyle g_{1}=3\uparrow ^{4}3=3\uparrow \uparrow \uparrow \uparrow 3=3\uparrow \uparrow \uparrow (3\uparrow \uparrow \uparrow 3)$ which is very big. Then, $\textstyle g_{2}=3\uparrow ^{g_{1}}3=3\uparrow ^{(3\uparrow ^{4}3)}3$, that is, there are g₁ up-arrows between the threes in g₂. That makes g₂ quite colossally big. Then g₃ has that many up-arrows between its 3s, and so on.

With Knuth up-arrows, each new up-arrow blows you way out of the ball park. $\textstyle 3\uparrow \uparrow \uparrow 3$ is huge, but $\textstyle 3\uparrow \uparrow \uparrow \uparrow 3$ makes it look tiny by comparison. And in the sequence g_n by which Graham's number is defined, you're not adding one up arrow each time, you're adding inconceivably huge numbers of up arrows each time. And you do that 64 times. Graham's number is big. Maelin (Talk | Contribs) 22:06, 11 December 2006 (UTC)

The current definition of g_1 is wrong.

Actually, g_1 is much, much more larger than currently explained in the article. Please someone fix it.

$g_{1}=3\uparrow \uparrow \uparrow \uparrow 3=3\uparrow \uparrow \uparrow (3\uparrow \uparrow \uparrow 3)=3\uparrow \uparrow \uparrow (3\uparrow \uparrow (3\uparrow \uparrow 3))$

$=3\uparrow \uparrow \uparrow (3\uparrow \uparrow (3^{27}))$

$=3\uparrow \uparrow \uparrow 3^{3^{.^{.^{.^{3}}}}}$ (there are $3^{27}$ 3's in the exponent)

$=3\uparrow \uparrow 3\uparrow \uparrow 3...\uparrow \uparrow 3$ (there are $3^{3^{.^{.^{.^{3}}}}}$ 3's here (there are $3^{27}$ 3's in the exponent))

$=3^{3^{.^{.^{.^{3}}}}}$ (there are $3^{3^{.^{.^{.^{3}}}}}$ 3's in the exponent (there are $3^{3^{.^{.^{.^{3}}}}}$ 3's in the exponent (...(there are 3 3's in the exponent)...))).

The last line above contains $3^{3^{.^{.^{.^{3}}}}}$ parentheses (there are $3^{27}$ 3's in the exponent in this line.) --Acepectif 18:10, 17 January 2007 (UTC)

I found out why the current article defines g_1 wrong. The current definition is $3\uparrow \uparrow \uparrow 3$, while g_1 requires four arrows. I'll try to fix it then. --Acepectif 20:19, 17 January 2007 (UTC)

Although my final result above is good in the sense that it doesn't contain any arrow, it looks too clumsy, using a more-than-astronomical number of parentheses. As it seems impratical (if not impossible) to use only exponentiation to express g_1, I decided to put some arrows there. --Acepectif 20:34, 17 January 2007 (UTC)

I've been trying to represent that properly but I can't get the formula to display correctly. My best attempt is here. The brace at the side is way too tall but I can't figure out how to fix it. If anybody can see what the problem is please fix is and feel free to put it into the article. Maelin (Talk | Contribs) 01:02, 18 January 2007 (UTC)

I've given up on getting it to render properly in TeX, so instead I doctored it up from the original output. I've put up an image of what I was originally trying to accomplish here. If anybody knows how to get it to display like this in TeX then please show us how. Maelin (Talk | Contribs) 06:46, 19 January 2007 (UTC)

Okay, I've changed the definition section and put in a definition of g₁ that I hope is clear and understandable. Maelin (Talk | Contribs) 09:02, 20 January 2007 (UTC)

I like what Maelin is trying to do. In the meantime I've opted to include a second recursive step to explain things. It's not as succinct as I believe it could be, but it at least makes mathematical sense and (I think) conveys enough "bigness". -- SamSim 13:07, 18 January 2007 (UTC)

SamSim, your version is too abstract for me to put g_1 into some semi-conceivable form (I know that's the point, but I thought I had caught on to something). I may have fouled up a bit with my version, but is it true that $3\uparrow \uparrow \uparrow \uparrow 3$ = a power tower of $3^{27}$ threes $3^{27}$ times = a power tower of $3^{205891132094649}$ threes, or is the actual number of threes too large to write? Ashibaka (tock) 18:59, 18 January 2007 (UTC)

I'm afraid it's not true. $3\uparrow \uparrow \uparrow \uparrow 3$ is actually equal to power tower of (a power tower of (a power tower of (... ... (a power tower of 3^27 threes) ... threes) threes) threes, where there are actually (a power tower of 3^27 threes) "power towers". As you can see this is pretty unwieldy. My crazy thing with f's is one way of expressing this; Maelin's LaTeX'd version is also correct, minor formatting difficulties aside - if that can be fixed, I am in favour of using it as a replacement. -- SamSim 13:51, 19 January 2007 (UTC)

Oh, I see my problem. I was reading the ellipses wrong, so my equation is simply a power tower of (a power tower of 3^27 threes) threes, which is (3^27)-2 power towers too few. Ashibaka (tock) 22:55, 19 January 2007 (UTC)

I think this is all correct and rendered correctly now! Excellent work, folks. Hooray for maths. -- SamSim 14:23, 20 January 2007 (UTC)

What's the point in having such a verbose definition? Why isn't $3\uparrow \uparrow \uparrow \uparrow 3$ sufficient? If someone wants to find out what that actually means, they can go and look at the article on Knuth arrow notation. The only thing that obscenity serves to do is confused people and clutter up the page. Inquisitus 09:20, 6 February 2007 (UTC)

The point is to give people an idea of how large it is. It's not about defining Knuth arrow notation, it's about giving an impression of the size of the first number in the g sequence is. Maelin (Talk | Contribs) 23:22, 6 February 2007 (UTC)

In that case would it not be a better idea to keep the actual definition concise and readable, and have the current rendering as an aside, perhaps in a separate section? -- Inquisitus 10:23, 7 February 2007 (UTC)

I don't think it's confusing or it clutters up the page. The equation does give the "concise and readable definition" with Knuth arrows. It's just an alternate and interesting way of looking at the number without arrows. Maybe the underbraces could be changed to an overbraces so you read the expression more naturally (from the top down). I think it can be extended to not only represent G_1 but Graham's number itself, but don't have the time to do it myself. Mytg8 15:46, 7 February 2007 (UTC)

I like the extra detail given in the definition. As an encyclopedia, wikipedia needs more to be explanatory rather than concise, as one might have in an advanced math text. However, I do think the word "threes" is weird and ambiguous. I think it should be removed. Other than that, I think expressing g₁ with nested exponentiation is useful. Kaimiddleton 06:15, 9 February 2007 (UTC)

I've moved the large rending to its own subsection to keep things tidier, it could probably do with a bit of a clean up still though. Also, I agree that the 'threes' and 'layers' should be removed from the rending as they make it rather confusing. Inquisitus 09:17, 13 February 2007 (UTC)

Why can't this be...

((6628186054241871761051728642144797485889866738756864194627932674204612481132879281240720140750840325559008576910490612741357798194746021808214 8510938844709284883675387902470250878557607543139203723695055306418868995491259871239807975904046447471772644936318562205668469072142054280062341134 6656785162817900551337542270334990205437212700131838846883)^7625597484987)^64

Easily said IMO (I'm not sure if I'm right, but it must be close :b). --hello, i'm a member | talk to me! 00:42, 11 July 2007 (UTC)

I'm not sure where you got that number from, but it looks like you have misunderstood either the Knuth up-arrows or the recursive definition. If you take a number, $\textstyle x=a\uparrow ^{(n)}b$, and then add just one more up arrow to make $\textstyle y=a\uparrow ^{(n+1)}b$, this new number y is, in comparison to x, astonishingly enormous. Unless x is something very small (say, less than 50), the second number will be phenomenally huge. Up arrows make things get very big, very fast. Then the recursive definition means that in the first iteration, g₁, we already get an inconceivably huge number. We then put that inconceivably huge number of up arrows into the second iteration, g₂. One arrow makes things blow up rapidly. We're putting in an inconceivably huge number of up arrows. g₂ is totally beyond the possibility of human comprehension. And then we repeat the process 63 more times. Graham's number is big.

If you've got some programming experience, try writing a program to calculate g₁ based on the recursive definition of up arrows. This should give you an idea of how big it is. Maelin (Talk | Contribs) 03:52, 11 July 2007 (UTC)

Bailey Notation

The article states the Bailey Notation is 4?3&62, shouldn't this be 4?3&64 ? The page on Bailey Notation claims it is 4?3&63 but I think this is wrong too. That page seems confused about the number of iterations in the construction. Bailey Notation is AfD anyway so this may not matter. If everyone thinks I'm right and the page on Bailey Notation isn't deleted I'll correct it. Smithers888 23:13, 7 October 2007 (UTC)

Add "layers" to the Definition of Graham's number section

The first PNG in that section could be made clearer by adding "layers" after 64, similar to what's done under Magnitude of Graham's number. It took me ages to figure out what it meant, and how it was 'equivalent' to the second given definition. I tried to do it, but my attempts were futile. --63.246.162.38 21:25, 13 October 2007 (UTC)

Done. --r.e.s. 22:23, 14 October 2007 (UTC)

Thanks--63.246.162.38 11:13, 23 October 2007 (UTC)

Question

Very interesting article. I wonder: while the number could not be expressed using exponentation, due to their being too many digits in the exponent, I wonder if the number could be rendered by way of tetration? -- Anonymous Dissident^Talk 11:12, 4 November 2007 (UTC)

Tetration is expressed with two upward arrows, here we have many.--Patrick 11:21, 4 November 2007 (UTC)

Too many to fit into the observable universe? -- Anonymous Dissident^Talk 11:28, 4 November 2007 (UTC)

Yes.

$G=\left.{\begin{matrix}3\underbrace {\uparrow \ldots \uparrow } 3\\\underbrace {\vdots } \\3\uparrow \uparrow \uparrow \uparrow 3\end{matrix}}\right\}{\text{64 layers}}$

i.e., to express the number of arrows we need 63 layers.--Patrick 07:38, 5 November 2007 (UTC)

Even $g_{2}$ already meets this criterion. Tetration doesn't really get us much closer than exponentation in any meaningful way for expressing G. Owen× ☎ 00:48, 6 November 2007 (UTC)

Upper Most Calculation

While trying to work this out (I still don't believe it's not possible to write out. Maybe you just think it is, just remember Fermat's Last Theorem does have a solution) I came to the conclusion that I need a bigger computer. Mine can only calculate up to $3e91023$ which comes out to be 1.0185171539798541759013048468071e43429.

That number has thousands of digits, but that is a small enough number to get a writeable number by taking its base 10 logarithm just once, which Graham's number is much too large for. Georgia guy (talk) 18:32, 7 February 2008 (UTC)

Agreeing with Georgia guy, a bigger computer will not help you with that. You have to understand that even if you manage to take all of the universe's approx. $10^{80}$ atoms and manage to arrange them in the way that gives you the most powerful computer possible, it will still not be powerful enough to calculate Graham's number. Even if every single of those atoms can display a million digits, you don't have enough atoms to display Graham's number. -- However, it's maybe not correct to state that "You cannot write down Graham's number", because at least in theory, every finite number can be written down using finite resources, and Graham's number is finite. The problem is that it isn't practically feasible, because the resources in time and matter exceed by very far anything that our universe offers. 85.0.177.231 (talk) 22:56, 9 February 2008 (UTC)

I'd like to know where we came up with the number of atoms in an ever-expanding universe. It seems to be much to small a number, and in any case, it's just a guess since we've explored so little. Not only that, but one 70 kilogram human contains about 7e27 atoms, so 6.5 billion humans (not taking into account those who are more (or less) than 70 kg) contain quite a few atoms (4.55e37, by my count), not nearly 10e80, but then take into account the number of atoms in earth, then the solar system, etc... Take into account super dense masses, stars, not to mention atoms floating in space, with no stellar masses associated with it. Then you can parse your statement, everyone says particles, not atoms, so wouldn't you have to count protons, neutrons, and electrons? Those number would make our hearts stop, if we could even wrap our tiny little brains around them. 75.44.29.49 (talk) 20:01, 12 February 2008 (UTC)

An expanding universe does not imply that the number of atoms is increasing, but I'm not denying that possibility either. But since you wonder where this number came from, check Observable_universe. As you can read there, this number is only for the observable universe, I guess that makes quite a difference, but this all is just a very rough guess anyway. As for the 'atom' vs 'particle', you might want to know that someone edited the article with the edit summary saying this: Changed "particles" to "atoms" in the leading paragraph to match the ending, as the number of particles (including virtual particles andQuantum Foam) could make a cup of tea contain infinite particles. jlh (talk) 00:32, 20 February 2008 (UTC)

As an excersize, try calculating g₁=$3\uparrow \uparrow \uparrow \uparrow 3$. To do this, try calculating just $3\uparrow \uparrow \uparrow 3$. This number is equal to a power tower of threes more than seven trillion stories high. By comparison, a power tower of threes just four stories high is $3^{7625597484987}$, far greater than your piddly $10^{80}$. So $3\uparrow \uparrow \uparrow 3$ is incredibly, incomprehensibly large. Adding the fourth arrow to make g₁ makes the number far larger, like the difference between 3 and $3\uparrow \uparrow \uparrow 3$, but greater. Obviously the degree to which this number is greater than the number of atoms in the observable universe, and even every permutation thereof, is vast and unimaginable. THAT is just g₁. g₂ has that many arrows . . . Eebster the Great (talk) 03:45, 10 September 2008 (UTC)

It's not physically possible to display the 1st layer.

It's not possible to compare the first layer with anything physical (elementary particles, atoms, paper clips).

However, as a side note, there're ways to iterate even bigger (but useless) numbers.

Like extending the iteration steps from 64 to 3^^^^4 times.

and taking the output from that operation (say, k)

and performing it on 3^(k-1)3, and iterating it k times.

and performing the above sequence k times.

Anything's possible. —Preceding unsigned comment added by 203.116.59.13 (talk) 05:58, 15 February 2008 (UTC)

But there's a limit as to what is useful, which is what makes Graham's Number special. 137.205.17.105 (talk) 17:10, 28 February 2008 (UTC)

Ridiculous understatement

The following sentence, from the introduction, is a ridiculous understatement:

"It is too large to be written in scientific notation because even the digits in the exponent would exceed the number of atoms in the observable universe so it needs its own special notation to write down."

While true, it is somewhat akin to saying that a googolplex is too large to write down in the form $\,1+1+1+1+...+1$. Graham's number is incredibly much larger than this sentence implies. I'll try to come up with a suitable replacement, but if someone else has an idea it would be nice to put that in. 75.52.241.166 (talk) 02:29, 19 February 2008 (UTC)

A very impressive statement (in the context of normal numbers) is not a ridiculous understatement.--Patrick (talk) 08:20, 19 February 2008 (UTC)

I agree with you that it's a massive understatement, but then again, I don't think it's likely that one could ever come up with a phrase that is not a massive understatement. It's very very very difficult to grasp the magnitude of Graham's number. I, for one, am not able to fully grasp it and neither can the English language, in my opinion. This being said, I'm not against replacing that statement with something better, if you can find something; good luck! jlh (talk) 00:38, 20 February 2008 (UTC)

I'll take a stab at it:

"It is too large to be written in scientific notation, since the number of digits in the exponent would exceed the number of atoms in the universe. In fact, the number of times one would have to take the number of digits to reduce it to a reasonable size (it doesn't matter how you define 'reasonable size') is itself unimaginably large."

This remains a dreadful understatement, but it's better. It will also hopefully get into some people's heads from this statement that 10^10^10^10... does not begin to describe Graham's number. --69.140.102.13 (talk) 21:34, 13 March 2008 (UTC)

I should perhaps clarify: if no one has any comment after a few days, I'll put it in. So if you have anything against putting it in, speak now (preferably). --69.140.102.13 (talk) 14:48, 14 March 2008 (UTC)

"the number of times one would have to take the number of digits" is not very clear.--Patrick (talk) 15:15, 14 March 2008 (UTC)

I agree that it is a little vague. Do you have any suggestion for how to improve on it? Please, feel free to write your own version. I just thought I'd take the initiative, since no one else seemed to be willing to do so. --69.140.102.13 (talk) 17:08, 14 March 2008 (UTC)

Alright, I'll take another crack at it. Placing this at the end of the paragraph instead of where it currently is:

"There is no concise way to write Graham's number, or any reasonable approximation, using conventional mathematical operators. Even power towers (of the form $a^{b^{c^{\cdot ^{\cdot ^{\cdot }}}}}$) are useless for this purpose. It can be most easily notated by recursive means using Knuth's up-arrow notation or the Hyper operator."

Again, comments welcome. --70.124.85.24 (talk) 11:47, 25 March 2008 (UTC)

In a couple days, if no one has any negative comments, I'll modify accordingly. So if you have any problems with it, please speak now to avoid editing wars. --70.124.85.24 (talk) 21:56, 28 March 2008 (UTC)

Sounds good, just go ahead and make the change. You'll never appease everyone anyway so be bold and edit. Owen× ☎ 22:08, 28 March 2008 (UTC)

Done. --70.124.85.24 (talk) 15:35, 30 March 2008 (UTC)

How about "number of cubic nanometers in the visible universe cubed"? I know it doesn't even get close but it's as large as can be intuitively understood. --222.101.9.201 (talk) 01:14, 17 May 2008 (UTC)

As opposed to "the number of atoms in the universe"? This is like standing on a step ladder to get a closer view of the stars. One is 10^80, the other is 10^105. Even the number of different permutations to arrange all the universe's atoms in order, 10^(10^82), doesn't get us any closer. Owen× ☎ 14:04, 17 May 2008 (UTC)

Confusing sentence

"More recently Geoff Exoo of Indiana State University has shown (in 2003) that it must be at least 11 and provided proof that it is larger."

Is the "provided proof that it is larger" necessary? Isn't that implicit with "at least 11"?-Wafulz (talk) 03:34, 20 March 2008 (UTC)

No, because it could be exactly 11. But if he provided proof that it was larger, couldn't you condense it to: "...it must be greater than' 11"? -- trlkly 18:28, 21 March 2008 (UTC)

They probably meant that he only has specific examples up to 11. Black Carrot (talk) 00:11, 12 April 2008 (UTC)

Does anyone have a reference on that? That is, a reference other than his webpage? Black Carrot (talk) 00:19, 12 April 2008 (UTC)

3^^^^3 is already "inconceivably large"

someone has to put the size of this number in words, I just start to comprehend how big this number is, its driving me loopy. Its 3^3^3 how many times? aaaahhhh!! Please help me someone! --LeakeyJee (talk) 14:41, 2 June 2008 (UTC)

That's the problem, really. Its size is totally incomprehensible. If you try to break it down into a building-up process where you have a comprehensibly large increase at each step, you need to repeat it an incomprehensible number of times. Maelin (Talk | Contribs) 04:53, 3 June 2008 (UTC)

ok, what if we raised the number of particles in the universe to the power of itself, then that number to the power of itself, then that number to the power of itself, etc. until you had done this as many times as there are particles in the universe? Are we getting close-ish here? --LeakeyJee (talk) 07:38, 8 June 2008 (UTC)

Nope. The number you describe is less than $3\uparrow \uparrow 5$, so you're not even really approaching $g_{1}$, much less $g_{64}$. If you can define it without multiple steps of recursion, chances are you're nowhere near G. Owen× ☎ 13:34, 8 June 2008 (UTC)

Ummm... I hate to disagree, but LeakeyJee's number, denoting $P$ as the number of particles in the universe, is larger than $P\uparrow \uparrow P$, which is much larger than $3\uparrow \uparrow 5$. Still not very large compared to Graham's number, though. Here's LeakeyJee's number to just two levels (he/she specifies $P$ levels): $(P^{P})^{(P^{P})}=P^{PP^{P}}=P^{P^{P+1}}$. Unfortunately, I don't know how to analyze the size of such a number.--70.124.85.24 (talk) 16:22, 8 June 2008 (UTC)

Here's a more rigorous way to define LeakeyJee's number, $N$, in terms of $P$, the number of particles in the universe:

$F(X)=X^{X}$

$N=F^{P}(P)$

Hope that helps.--70.124.85.24 (talk) 16:29, 8 June 2008 (UTC)

You are incorrect. Leakeyjee's number uses a left-associative power tower: ((...(P^P)^P)...)^P which is much smaller than P^^P. In fact, LeakeyJee's number is smaller than P^(P^P). If we correct LeakeyJee's description to be right-associative, like this:

if we raised the number of particles in the universe to the power of itself, then itself to that power...

Then we get P^^P, which is still tiny compared to 3^^^3. Owen× ☎ 22:07, 8 June 2008 (UTC)

No, 70.124.85.24 has it right, and you're misquoting LeakeyJee, who said "... then that number to the power of itself", which leads to the analysis I posted below. My a_n is just Fⁿ(P).--r.e.s. (talk) 22:32, 8 June 2008 (UTC)

The answer is NO! -- your (LeakeyJee's) number is much less than even 3^^3^^4, let alone 3^^^4 or the stupendously larger starting term g_1 (3^^^^3) in the recursion for Graham's number.

Here's a quick analysis for the number in question, which is a_P in the sequence defined by

a_0 = P

a_(n+1) = (a_n)^(a_n).

To get a very conservative bound, just notice that

(b^^a)^(b^^a) < b^^(a+2) for any integers a > 0, b > 1.

so

a_0 = P

a_1 = a_0 ^ a_0 = P^P

a_2 = a_1 ^ a_1 = (P^P)^(P^P) < P^^4

a_3 = a_2 ^ a_2 < (P^^4)^(P^^4) < P^^6

a_4 = a_3 ^ a_3 < (P^^6)^(P^^6) < P^^8

...

a_P < P^^(2P).

Then, since P is presumed to be less than, oh, say 10^200 (< 3^^4), we have

a_P < 3^^(4P+2)

because

P < 3^^4

P^P < (3^^4)^(3^^4) < 3^^6

P^P^P < (3^^4)^(3^^6) < 3^^8

...

P^P^P^...P^P (x P's) < 3^^(2(x+1))

...

P^^(2P) = P^P^P^...P^P (2P P's) < 3^^(2(2P+1)).

Thus we have the very conservative bounds

a_P < 3^^(4P+2) < 3^^3^^4 < 3^^^4.

(BTW, P < 10^186 < 3^^4 even if we imagine P to be the number of little cubes that subdivide a big cube, where the big cube has edge-length equal to something like the "diameter of the universe" and the little cubes have edge-length equal to something like the Planck length.)

--r.e.s. (talk) 03:03, 9 June 2008 (UTC)

Thanks for taking over the problem. I knew someone would be able to compare this number to Graham's if I laid the groundwork of clarifying what exactly the number in question was. I just wanted to let you know that your work didn't fall on deaf ears. I'm wading through the math, and might understand it all in a couple of weeks. :) --70.124.85.24 (talk) 03:20, 9 June 2008 (UTC)

As for the original poster's idea that "someone has to put the size of this number in words" ... As others have mentioned, there probably is no way to convey a sense of the enormous size of numbers like g_1 (3^^^^3), let alone g_64. The mathematician H. Friedman has (somewhat arbitrarily, I suppose) suggested 2^^^^5 as a benchmark "incomprehensibly large" number, 2^^^^5 being the 5th Ackermann number in a particular streamlined version of the Ackermann hierarchy. I think an effectively equivalent benchmarking can be given in terms of 3^...^3: The size of 3^^3 is considered comprehensible, the size of 3^^^3 is in a kind of gray area of comprehensibility, and 3^^^^3 is incomprehensibly large. Although 3^^^^3 may be less than 2^^^^5 (I'm not sure), imo it's effectively in the same ballpark of literally being "incomprehensibly large".

--r.e.s. (talk) 20:56, 8 June 2008 (UTC)

haha "LeakeyJee's" number - I love it! Someone should start a new page for it. Thanks for all the comments here everyone, much appreciated, even though much of it is far above my head! --LeakeyJee (talk) 15:35, 9 June 2008 (UTC)

Oh man, I agree, that's great. —Preceding unsigned comment added by Hawkian (talk • contribs) 22:19, 17 June 2008 (UTC)

Revised introduction

The article stated that Graham's number is "often described as the largest finite number that has ever been seriously used in a mathematical proof. Guinness World Records even listed Graham's number as the World Champion largest number." However, that first sentence is a mangled version of what appears in Martin Gardner's 1977 Sci. Am. article ("it holds the record for the largest number ever used in a serious mathematical proof"), and which was repeated in the 1980 Guinness Book of World Records (see this page for an image of the book's entry: "The highest number ever used in a mathematical proof is a bounding value published in 1977 and known as Graham's number."). The hype-laden expression "World Champion largest number" appears in The Penguin Dictionary of Curious and Interesting Numbers (1998) by David Wells, and I've edited the introduction to remove this silliness. I also added a citation of Gardner's Sci. Am. article, and reworded the introduction accordingly. Also, I added a remark about Harvey Friedman's work, and added a link to his finite form of Kruskal's Tree Theorem, which mentions TREE(3) and a lower bound for it (the same lower bound as for Friedman's n(4)). r.e.s. (talk) 19:47, 23 June 2008 (UTC)

Martin Gardner's version vs. Graham's published version

The number that Martin Gardner popularized as "Graham's number" (and which is taken to be the subject of the present article) is much larger than the actual best known upper bound published by Graham & Rothschild in 1971. The latter number is, according to links posted in previous discussions,

$N=\left.{\begin{matrix}\underbrace {2\uparrow \uparrow \uparrow \uparrow \uparrow \uparrow \uparrow \uparrow \uparrow \uparrow \uparrow \uparrow 3} \\\underbrace {2\uparrow \dots \dots \dots \dots \uparrow 3} \\{\vdots }\\\underbrace {\qquad \qquad \qquad \quad \qquad } \\{2\uparrow \dots \dots \dots \dots \dots \uparrow 3}\end{matrix}}\right\}{\text{7 layers}}$

where there are 12 up-arrows in the first layer. I've added a comment to this effect in the section on "Graham's Problem", as it would be easy to confuse these two numbers. A possible explanation for Gardner's version being larger (i.e. worse) than the one already published by G&H in 1971, is that an unpublished proof by Graham might naturally have given the weaker (larger) bound. Of course, "practically speaking", N* is just as incomprehensibly large as G.
r.e.s. (talk) 00:44, 24 June 2008 (UTC)

Here's something curious I just noticed concerning Gardner's 2001 "revised version" of the original 1977 article (in which he apparently coined the term "Graham's number") ... According to quotations posted previously in the above section on "numbers larger than Graham's number" — taken directly from a photocopy of Gardner's November 1977 Sci. Am. article — Gardner wrote the following:
"In an unpublished proof Graham has recently established an upper bound, but it is a bound so vast that it holds the record for the largest number ever used in a serious mathematical proof."
However, in Gardner's 2001 book, "The Colossal Book of Mathematics: Classic Puzzles, Paradoxes, and Problems" (which can be previewed online), he says the chapter on Ramsey Theory "first appeared in Scientific American in 1977" — but the original sentence has evidently been changed to omit explicit reference to an unpublished proof (recent or otherwise):
"Graham has established an upper bound, but it is a bound so vast that it holds the record for the largest number ever used in a serious mathematical proof." (p. 449)
r.e.s. (talk) 16:09, 24 June 2008 (UTC)

TREE(Graham's number)

Just think about it... —Preceding unsigned comment added by 98.165.149.229 (talk) 02:46, 24 July 2008 (UTC)

If I were capable of comprehending the magnitude of TREE(3) (which I'm not), I would leave Graham's number out of the picture entirely — because it's so tiny in comparison — and rather try to comtemplate the size of, say, TREE(TREE(3)), which is also impossible. These are futile exercises.
r.e.s. (talk) 17:32, 24 July 2008 (UTC)

What is this Tree function? There doesn't appear to be a Wikipedia page about it, and, for obvious reasons, it would be futile to Google. --69.91.95.139 (talk) 23:02, 26 July 2008 (UTC)

The article has links in two places to the definition of Friedman's TREE function at Kruskal's theorem.
--r.e.s. (talk) 04:04, 27 July 2008 (UTC)

Thanks for the link.

I wish I could say that page helped my comprehension, but that would be a lie. I guess it's just too far over my head. Oh well. --69.91.95.139 (talk) 01:06, 29 July 2008 (UTC)

Since this area is supposed to be about Graham's number, here's an informal page about TREE on my personal website, which might help.
--r.e.s. (talk) 20:07, 29 July 2008 (UTC)

Thanks. That's a bit better. Now I just need a couple months to spare. ;) --69.91.95.139 (talk) 00:34, 30 July 2008 (UTC)

You're doing that just to horrify the mathematicians aren't you? 128.253.213.124 (talk) 11:41, 24 August 2008 (UTC)

Proof that it's not the biggest number

"holds the record for the largest number ever used in a serious mathematical proof" does not in any way suggest that it is "the largest finite number possible" So adding a proof that it isn't is neither necessary or even interesting. I removed the section. Theresa Knott | The otter sank 09:53, 3 August 2008 (UTC)

While I'm a full believer of WP:AGF, I don't think it really applies here; CallumBrowne was a clear vandal, as shown by previous vandalizing edits such as this one, which, while not the same IP address, use the same fictional mathematician.

Not to mention, of course, the fact that CallumBrowne didn't seem to understand that the layered exponential number is only $G_{1}$, not Graham's number itself. ;) --69.91.95.139 (talk) 12:22, 3 August 2008 (UTC)

Yes I came to much the same conclusion once I looked into his edits more thoroughly. Theresa Knott | The otter sank 13:22, 3 August 2008 (UTC)

How to write it in a relatively small number of symbols

If we create a new operation $\Uparrow$ which bears the same relationship to $\uparrow$ as times bears to plus, Graham's number becomes quite straightforward to write down.

$g_{1}=3\uparrow \uparrow \uparrow \uparrow 3=3\Uparrow 4$

$g_{2}=3\Uparrow (3\Uparrow 4)$

$g_{3}=3\Uparrow (3\Uparrow (3\Uparrow 4))$

$g_{4}=3\Uparrow (3\Uparrow (3\Uparrow (3\Uparrow 4)))$

$g_{5}=3\Uparrow (3\Uparrow (3\Uparrow (3\Uparrow (3\Uparrow 4))))$

$...$

$g_{64}=3\Uparrow (3\Uparrow (3\Uparrow (3\Uparrow 3\Uparrow (3\Uparrow (3\Uparrow (3\Uparrow 3\Uparrow (3\Uparrow (3\Uparrow (3\Uparrow 3\Uparrow (3\Uparrow (3\Uparrow (3\Uparrow 3\Uparrow (3\Uparrow (3\Uparrow (3\Uparrow 3\Uparrow (3\Uparrow (3\Uparrow (3\Uparrow 3\Uparrow (3\Uparrow (3\Uparrow (3\Uparrow 3\Uparrow (3\Uparrow (3\Uparrow (3\Uparrow 3\Uparrow (3\Uparrow (3\Uparrow (3\Uparrow 3\Uparrow (3\Uparrow (3\Uparrow (3\Uparrow 3\Uparrow (3\Uparrow (3\Uparrow (3\Uparrow 3\Uparrow (3\Uparrow (3\Uparrow (3\Uparrow 3\Uparrow (3\Uparrow (3\Uparrow (3\Uparrow 3\Uparrow (3\Uparrow (3\Uparrow (3\Uparrow 3\Uparrow (3\Uparrow (3\Uparrow (3\Uparrow 3\Uparrow (3\Uparrow (3\Uparrow (3\Uparrow 4)))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))$

A little lengthy perhaps but not too bad.

Of course it's still just as impossible to calculate but we do know that it's an odd number and that it's composite. -- Derek Ross | Talk 17:50, 6 August 2008 (UTC)

That's not creating a new operation — it's just using a different symbol for f as defined in the article:

"$G=f^{64}(4)$, where $f(n)={\text{hyper}}(3,n+2,3)$ and hyper() is the hyper operator." In other words, operationally, $f=3\Uparrow$. (On the other hand, the notation $m\Uparrow n$ is a shorthand for the special case of hyper(m,n+2,m) with two of the arguments equal.) However, since Knuth arrows are used in Gardner's original definition of G, I think they should be used here instead of the hyper() function (and they're better-known, anyway); so, I'll revise the quoted sentence to be something like the following:

"$G=f^{64}(4)$, where, in terms of Knuth arrows, $f(n)=3\uparrow ^{n}3$, and superscripts indicate iteration."
--r.e.s. (talk) 20:03, 6 August 2008 (UTC)

Fair enough. -- Derek Ross | Talk 00:44, 7 August 2008 (UTC)

Can we write some of the digits?

We all know that Pi is an irrational number that has an infinite number of digits, but we can still write down the first digits. Is there some maths you can do to work out the first few digts of this number, or possibly the last few? That would be very interesting.--81.157.65.210 (talk) 20:26, 3 September 2008 (UTC)

With knowledge on powers of 3, the last digit of Graham's number is a 7 and the next to last digit is even (i.e. the number ends in 07, 27, 47, 67, or 87.) Georgia guy (talk) 21:33, 3 September 2008 (UTC)

The last 10 digits of Graham's number are: ...2464195387. This used to be mentioned in an older rev of the article, you can still find it in the history. Not sure why it was removed. The first few digits are much more difficult to calculate. Owen× ☎ 21:38, 3 September 2008 (UTC)

Addendum: I guess these digits are disputed. I have a copy of the Conway & Guy book, but can't find any mention of the last digits of Graham's number. Can someone shed some light? Owen× ☎ 22:29, 3 September 2008 (UTC)

Addendum 2: If these digits are a mistake, it certainly is a well-propagated mistake. Here are a few of many web references available: [3], [4], [5], [6]. Owen× ☎ 22:46, 3 September 2008 (UTC)

If there is enough interest in this topic, we can revive it in the article. Giftlite (talk) 20:15, 4 September 2008 (UTC)

For almost every other constant, we give at least a few significant digits. For this number, I don't think anyone was able to calculate the most significant digits, but we do have the least significant few. I don't see this as "trivia", and considering the prevalence of citations, it seems notable and referenced enough to quote in the article.

I've restored the sentence showing the last ten digits into the article, this time with references. Not interested in getting into an edit war here; if you have actual sources to dispute this, by all means, let's review and discuss them. The Conway & Guy book you rely on uses a completely different definition for G which is not the normally accepted one in literature, and not the one we use here. Owen× ☎ 20:49, 4 September 2008 (UTC)

For what it's worth ... With the help of a computer program, I was able to confirm that the ten least-significant digits of G are indeed ...2464195387; however, unless a decent reference is found — and there might not be any — maybe they shouldn't be in the article. (The "sources" cited so far give no references at all, and they may have just taken the info from the old WP article, which also gave no references.) Very possibly there's no published source for these digits; rather, a few people have simply figured them out on their own, without explaining the details.
--r.e.s. (talk) 07:57, 5 September 2008 (UTC)

Couldn't you simply put how you did it in the article?--81.157.65.210 (talk) 15:56, 5 September 2008 (UTC)

(I hope you don't mind that I indented your question, since it seems to be addressed to me.)

Before I add to the article, let me post here first to see what people think — I'm not sure about the WP guidelines, but maybe a portion of this can be worked into a separate section. The simplest method is probably the one described on this page, which I've summarized as follows:

The sequence of d least-significant decimal digits of p$\uparrow \uparrow$n, where p is an odd prime and n > d, can be obtained by iterating the function f: x → p^x mod 10^d, with starting value x = p, until f(x) ≡ x mod 10^d. This procedure requires at most d+1 iterations.

I wrote this bare-bones MuPAD program to implement it:

tower_digits:=proc(d,p)
//Returns the d least-significant decimal digits of p^^n (n > d)
//and the height of the shortest tower p^^height with those LSDs;
//p is an odd prime, p^^n is the "power tower" p^p^...p^p (n p's).
local x, oldx, height;
begin
    x := p;
    height := 1;
    while TRUE do
        oldx := x;
        x := powermod(p,x,10^d);
        if x = oldx mod 10^d then break end_if;
        height := height + 1
    end_while;
    return([x,height])
end_proc

E.g., tower_digits(100,3) — the 100 least-significant digits of any tower of 3s of height greater than 100 (this includes G, of course) — took less than one second to execute:

...9404248265018193851562535796399618993967905496638003222348723967018485186439059104575627262464195387

As a double-check, I also worked out a "direct search" program that doesn't use this recursion, but instead uses brute force to compute the period of the sequence of remainders 3ⁿ mod m (n = 0,1,2,..) for various moduli m, then applies to them a certain fixed-point condition that the solution must satisfy. This method also confirms the ten-digit result, but took about 8 hours to run.

A consequence of what's proved on the page linked above is the following interesting property of power towers:
For any fixed odd prime p, all towers p$\uparrow \uparrow$n with n > d have the same d least-significant decimal digits.
--r.e.s. (talk) 20:58, 5 September 2008 (UTC) EDIT: I've revised both the recursion and the program above, which were in error. (The correction doesn't affect the 100-digit result)..--r.e.s. (talk) 13:29, 6 September 2008 (UTC)

Impressive and non intuitive result! So, what is the smallest N for which for all n ≥ N: 3^^n ≡ 3^^(n+1) {mod 10^10}? That is, at which power tower height (of 3s) do the ten last digits "stabilize"? Owen× ☎ 22:33, 5 September 2008 (UTC)

The "stabilization" occurs in that case at height n = 11, as can be seen by iterating the function (3^x mod 10^10) with starting value x = 3. Stabilization of at least d digits is guaranteed to occur at a height of at most d+1, and in some cases it occurs at much smaller heights. With d = 3, for example, all towers of 101's have 101 as their three least-significant digits.
--r.e.s. (talk) 02:30, 6 September 2008 (UTC)

I've had to correct the recursion & program that I originally posted — I just edited them "in-place" above. They had reflected a misunderstanding of mine regarding part of what was proved on the page at the external link. The present version more accurately summarizes the procedure described there, and my previous version should be disregarded.
--r.e.s. (talk) 05:51, 6 September 2008 (UTC)

Yes, a very impressive result. Just out of curiosity (I'm not a mathematician), would anyone be interested in finding the last digits of Friedman's n(4)? http://en.wiki.x.io/wiki/Kruskal%27s_theorem#Friedman.27s_finite_forms Mytg8 (talk) 16:57, 13 November 2008 (UTC)

--
Another interesting property:

The rightmost d digits of 3^3^...3^x are independent of x if the height of the tower (including the x) is at least d+3. In other words, given a tower 3^^n of any height n > 3, the topmost '3' can be changed to any number (nonnegative integer) without affecting the rightmost n-3 decimal digits. E.g., the rightmost digit of 3^3^3^x is independent of x.

Here's an explanation of why this is so ... For a few small values of d, and a few short towers 3^3^...3^x, the following table shows the size of the set of all possible values of 3^3^...3^x when all but the rightmost d digits are ignored (i.e. the residues mod 10^d). For a given height of tower and number of digits d, the full range of d-digit numbers (10^d of them) does not occur — instead, a certain smaller subset of values repeats itself in a cycle. The length of the cycle and some of the values (in parentheses) are shown in each cell.

Number of different possible values of 3^3^ ... 3^x when all but the rightmost d decimal digits are ignored

Number of digits (d)	3^x	3^3^x	3^3^3^x	3^3^3^3^x	3^3^3^3^3^x
1	4 (1,3,9,7)	2 (3,7)	1 (7)	1 (7)	1 (7)
2	20 (01,03,...,87,...,67)	4 (03,27,83,87)	2 (27,87)	1 (87)	1 (87)
3	100 (001,003,...,387,...,667)	20 (003,027,...387,...,587)	4 (027,987,227,387)	2 (987,387)	1 (387)

For any fixed number of digits d (row in the table), the number of values possible for 3^3^...3^x mod 10^d, produced by all possible x, is seen to decrease steadily as the height increases, until eventually reducing the "possibility set" to a single number (colored cells) when the height equals or exceeds d+3.--r.e.s. (talk) 04:19, 7 September 2008 (UTC)