Как пишется число грэма

Какое на свете самое больше число, которое что–то означает? В этой статье я попытаюсь рассказать о цифровом монстре, называемом число Грэма,

This article is about the very large number named after Ronald Graham. For the investing term named after Benjamin Graham, see Graham number.

Graham’s number is an immense number that arose as an upper bound on the answer of a problem in the mathematical field of Ramsey theory. It is much larger than many other large numbers such as Skewes’s number and Moser’s number, both of which are in turn much larger than a googolplex. As with these, it is so large that the observable universe is far too small to contain an ordinary digital representation of Graham’s number, assuming that each digit occupies one Planck volume, possibly the smallest measurable space. But even the number of digits in this digital representation of Graham’s number would itself be a number so large that its digital representation cannot be represented in the observable universe. Nor even can the number of digits of that number—and so forth, for a number of times far exceeding the total number of Planck volumes in the observable universe. Thus Graham’s number cannot be expressed even by physical universe-scale power towers of the form .

However, Graham’s number can be explicitly given by computable recursive formulas using Knuth’s up-arrow notation or equivalent, as was done by Ronald Graham, the number’s namesake. As there is a recursive formula to define it, it is much smaller than typical busy beaver numbers. Though too large to be computed in full, the sequence of digits of Graham’s number can be computed explicitly via simple algorithms; the last 13 digits are …7262464195387. With Knuth’s up-arrow notation, Graham’s number is , where

Graham’s number was used by Graham in conversations with popular science writer Martin Gardner as a simplified explanation of the upper bounds of the problem he was working on. In 1977, Gardner described the number in Scientific American, introducing it to the general public. At the time of its introduction, it was the largest specific positive integer ever to have been used in a published mathematical proof. The number was described in the 1980 Guinness Book of World Records, adding to its popular interest. Other specific integers (such as TREE(3)) known to be far larger than Graham’s number have since appeared in many serious mathematical proofs, for example in connection with Harvey Friedman’s various finite forms of Kruskal’s theorem. Additionally, smaller upper bounds on the Ramsey theory problem from which Graham’s number derived have since been proven to be valid.

Context[edit]

Graham’s number is connected to the following problem in Ramsey theory:

Connect each pair of geometric vertices of an n-dimensional hypercube to obtain a complete graph on 2ⁿ vertices. Colour each of the edges of this graph either red or blue. What is the smallest value of n for which every such colouring contains at least one single-coloured complete subgraph on four coplanar vertices?

In 1971, Graham and Rothschild proved the Graham–Rothschild theorem on the Ramsey theory of parameter words, a special case of which shows that this problem has a solution N*. They bounded the value of N* by 6 ≤ N* ≤ N, with N being a large but explicitly defined number

where in Knuth’s up-arrow notation; the number is between 4 → 2 → 8 → 2 and 2 → 3 → 9 → 2 in Conway chained arrow notation.^[1] This was reduced in 2014 via upper bounds on the Hales–Jewett number to

which contains three tetrations.^[2] In 2019 this was further improved to:^[3]

The lower bound of 6 was later improved to 11 by Geoffrey Exoo in 2003,^[4] and to 13 by Jerome Barkley in 2008.^[5] Thus, the best known bounds for N* are 13 ≤ N* ≤ N».

Graham’s number, G, is much larger than N: , where . This weaker upper bound for the problem, attributed to an unpublished work of Graham, was eventually published and named by Martin Gardner in Scientific American in November 1977.^[6]

Publication[edit]

The number gained a degree of popular attention when Martin Gardner described it in the «Mathematical Games» section of Scientific American in November 1977, writing that Graham had recently established, in an unpublished proof, «a bound so vast that it holds the record for the largest number ever used in a serious mathematical proof.» The 1980 Guinness Book of World Records repeated Gardner’s claim, adding to the popular interest in this number. According to physicist John Baez, Graham invented the quantity now known as Graham’s number in conversation with Gardner. While Graham was trying to explain a result in Ramsey theory which he had derived with his collaborator Bruce Lee Rothschild, Graham found that the said quantity was easier to explain than the actual number appearing in the proof. Because the number which Graham described to Gardner is larger than the number in the paper itself, both are valid upper bounds for the solution to the problem studied by Graham and Rothschild.^[7]

Definition[edit]

Using Knuth’s up-arrow notation, Graham’s number G (as defined in Gardner’s Scientific American article) is

where the number of arrows in each subsequent layer is specified by the value of the next layer below it; that is,

where

and where a superscript on an up-arrow indicates how many arrows there are. In other words, G is calculated in 64 steps: the first step is to calculate g₁ with four up-arrows between 3s; the second step is to calculate g₂ with g₁ up-arrows between 3s; the third step is to calculate g₃ with g₂ up-arrows between 3s; and so on, until finally calculating G = g₆₄ with g₆₃ up-arrows between 3s.

Equivalently,

and the superscript on f indicates an iteration of the function, e.g., . Expressed in terms of the family of hyperoperations , the function f is the particular sequence , which is a version of the rapidly growing Ackermann function A(n, n). (In fact, for all n.) The function f can also be expressed in Conway chained arrow notation as , and this notation also provides the following bounds on G:

Magnitude[edit]

To convey the difficulty of appreciating the enormous size of Graham’s number, it may be helpful to express—in terms of exponentiation alone—just the first term (g₁) of the rapidly growing 64-term sequence. First, in terms of tetration () alone:

where the number of 3s in the expression on the right is

Now each tetration () operation reduces to a power tower () according to the definition

where there are X 3s.

Thus,

becomes, solely in terms of repeated «exponentiation towers»,

and where the number of 3s in each tower, starting from the leftmost tower, is specified by the value of the next tower to the right.

In other words, g₁ is computed by first calculating the number of towers, (where the number of 3s is ), and then computing the n^th tower in the following sequence:

      1st tower:  3
     
      2nd tower:  3↑3↑3 (number of 3s is 3) = 7625597484987
     
      3rd tower:  3↑3↑3↑3↑...↑3 (number of 3s is 7625597484987) = …
     
      ⋮
     
 g1 = nth tower:  3↑3↑3↑3↑3↑3↑3↑...↑3 (number of 3s is given by the n-1th tower)

where the number of 3s in each successive tower is given by the tower just before it. Note that the result of calculating the third tower is the value of n, the number of towers for g₁.

The magnitude of this first term, g₁, is so large that it is practically incomprehensible, even though the above display is relatively easy to comprehend. Even n, the mere number of towers in this formula for g₁, is far greater than the number of Planck volumes (roughly 10¹⁸⁵ of them) into which one can imagine subdividing the observable universe. And after this first term, still another 63 terms remain in the rapidly growing g sequence before Graham’s number G = g₆₄ is reached. To illustrate just how fast this sequence grows, while g₁ is equal to with only four up arrows, the number of up arrows in g₂ is this incomprehensibly large number g₁.

Rightmost decimal digits[edit]

Graham’s number is a «power tower» of the form 3↑↑n (with a very large value of n), so its rightmost decimal digits must satisfy certain properties common to all such towers. One of these properties is that all such towers of height greater than d (say), have the same sequence of d rightmost decimal digits. This is a special case of a more general property: The d rightmost decimal digits of all such towers of height greater than d+2, are independent of the topmost «3» in the tower; i.e., the topmost «3» can be changed to any other non-negative integer without affecting the d rightmost digits.

The following table illustrates, for a few values of d, how this happens. 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 of this table:

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)

The particular rightmost d digits that are ultimately shared by all sufficiently tall towers of 3s are in bold text, and can be seen developing as the tower height increases. For any fixed number of digits d (row in the table), the number of values possible for 33↑…3↑x mod 10^d, as x ranges over all nonnegative integers, is seen to decrease steadily as the height increases, until eventually reducing the «possibility set» to a single number (colored cells) when the height exceeds d+2.

A simple algorithm^[8] for computing these digits may be described as follows: let x = 3, then iterate, d times, the assignment x = 3^x mod 10^d. Except for omitting any leading 0s, the final value assigned to x (as a base-ten numeral) is then composed of the d rightmost decimal digits of 3↑↑n, for all n > d. (If the final value of x has fewer than d digits, then the required number of leading 0s must be added.)

Let k be the numerousness of these stable digits, which satisfy the congruence relation G(mod 10^k)≡[G^G](mod 10^k).

k=t-1, where G(t):=3↑↑t.^[9] It follows that, g₆₃ ≪ k ≪ g₆₄.

The algorithm above produces the following 500 rightmost decimal digits of Graham’s number (OEIS: A133613):

...02425950695064738395657479136519351798334535362521
   43003540126026771622672160419810652263169355188780
   38814483140652526168785095552646051071172000997092
   91249544378887496062882911725063001303622934916080
   25459461494578871427832350829242102091825896753560
   43086993801689249889268099510169055919951195027887
   17830837018340236474548882222161573228010132974509
   27344594504343300901096928025352751833289884461508
   94042482650181938515625357963996189939679054966380
   03222348723967018485186439059104575627262464195387

References[edit]

Bibliography[edit]

• Gardner, Martin (November 1977). «Mathematical Games» (PDF). Scientific American. 237 (5): 18–28. Bibcode:1977SciAm.237e..18G. doi:10.1038/scientificamerican1177-18.; reprinted (revised) in Gardner (2001), cited below.
• Gardner, Martin (1989). Penrose Tiles to Trapdoor Ciphers. Washington, D.C.: Mathematical Association of America. ISBN 978-0-88385-521-8.
• Gardner, Martin (2001). The Colossal Book of Mathematics: Classic Puzzles, Paradoxes, and Problems. New York, NY: Norton. ISBN 978-0-393-02023-6.
• Graham, R. L.; Rothschild, B. L. (1971). «Ramsey’s Theorem for n-Parameter Sets» (PDF). Transactions of the American Mathematical Society. 159: 257–292. doi:10.2307/1996010. JSTOR 1996010. The explicit formula for N appears on p. 290. This is not the «Graham’s number» G published by Martin Gardner.
• Graham, R. L.; Rothschild, B. L. (1978). «Ramsey Theory». In Rota, G-C (ed.). Studies in Combinatorics (MAA Studies in Mathematics). Vol. 17. Mathematical Association of America. pp. 80–99. ISBN 978-0-88385-117-3. On p. 90, in stating «the best available estimate» for the solution, the explicit formula for N is repeated from the 1971 paper.

External links[edit]

• OEIS sequence A133613 (Graham’s number)
• Sbiis Saibian’s article on Graham’s number
• «A Ramsey Problem on Hypercubes» by Geoff Exoo
• Mathworld article on Graham’s number
• How to calculate Graham’s number
• Conceptualizing Graham’s number
• Some Ramsey results for the n-cube prepublication mentions Graham’s number
• Padilla, Tony; Parker, Matt. «Graham’s Number». Numberphile. Brady Haran. Archived from the original on 2014-05-27. Retrieved 2013-04-08.
• Archived at Ghostarchive and the Wayback Machine: Ron Graham. «What is Graham’s Number? (feat Ron Graham)» (video). Numberphile. Brady Haran.
• Archived at Ghostarchive and the Wayback Machine: Ron Graham. «How Big is Graham’s Number? (feat Ron Graham)» (video). Numberphile. Brady Haran.
• The last 16 million digits of Graham’s number by the Darkside communication group

This article is about the very large number named after Ronald Graham. For the investing term named after Benjamin Graham, see Graham number.

Graham’s number is an immense number that arose as an upper bound on the answer of a problem in the mathematical field of Ramsey theory. It is much larger than many other large numbers such as Skewes’s number and Moser’s number, both of which are in turn much larger than a googolplex. As with these, it is so large that the observable universe is far too small to contain an ordinary digital representation of Graham’s number, assuming that each digit occupies one Planck volume, possibly the smallest measurable space. But even the number of digits in this digital representation of Graham’s number would itself be a number so large that its digital representation cannot be represented in the observable universe. Nor even can the number of digits of that number—and so forth, for a number of times far exceeding the total number of Planck volumes in the observable universe. Thus Graham’s number cannot be expressed even by physical universe-scale power towers of the form .

However, Graham’s number can be explicitly given by computable recursive formulas using Knuth’s up-arrow notation or equivalent, as was done by Ronald Graham, the number’s namesake. As there is a recursive formula to define it, it is much smaller than typical busy beaver numbers. Though too large to be computed in full, the sequence of digits of Graham’s number can be computed explicitly via simple algorithms; the last 13 digits are …7262464195387. With Knuth’s up-arrow notation, Graham’s number is , where

Graham’s number was used by Graham in conversations with popular science writer Martin Gardner as a simplified explanation of the upper bounds of the problem he was working on. In 1977, Gardner described the number in Scientific American, introducing it to the general public. At the time of its introduction, it was the largest specific positive integer ever to have been used in a published mathematical proof. The number was described in the 1980 Guinness Book of World Records, adding to its popular interest. Other specific integers (such as TREE(3)) known to be far larger than Graham’s number have since appeared in many serious mathematical proofs, for example in connection with Harvey Friedman’s various finite forms of Kruskal’s theorem. Additionally, smaller upper bounds on the Ramsey theory problem from which Graham’s number derived have since been proven to be valid.

Context[edit]

Graham’s number is connected to the following problem in Ramsey theory:

Connect each pair of geometric vertices of an n-dimensional hypercube to obtain a complete graph on 2ⁿ vertices. Colour each of the edges of this graph either red or blue. What is the smallest value of n for which every such colouring contains at least one single-coloured complete subgraph on four coplanar vertices?

In 1971, Graham and Rothschild proved the Graham–Rothschild theorem on the Ramsey theory of parameter words, a special case of which shows that this problem has a solution N*. They bounded the value of N* by 6 ≤ N* ≤ N, with N being a large but explicitly defined number

where in Knuth’s up-arrow notation; the number is between 4 → 2 → 8 → 2 and 2 → 3 → 9 → 2 in Conway chained arrow notation.^[1] This was reduced in 2014 via upper bounds on the Hales–Jewett number to

which contains three tetrations.^[2] In 2019 this was further improved to:^[3]

The lower bound of 6 was later improved to 11 by Geoffrey Exoo in 2003,^[4] and to 13 by Jerome Barkley in 2008.^[5] Thus, the best known bounds for N* are 13 ≤ N* ≤ N».

Graham’s number, G, is much larger than N: , where . This weaker upper bound for the problem, attributed to an unpublished work of Graham, was eventually published and named by Martin Gardner in Scientific American in November 1977.^[6]

Publication[edit]

The number gained a degree of popular attention when Martin Gardner described it in the «Mathematical Games» section of Scientific American in November 1977, writing that Graham had recently established, in an unpublished proof, «a bound so vast that it holds the record for the largest number ever used in a serious mathematical proof.» The 1980 Guinness Book of World Records repeated Gardner’s claim, adding to the popular interest in this number. According to physicist John Baez, Graham invented the quantity now known as Graham’s number in conversation with Gardner. While Graham was trying to explain a result in Ramsey theory which he had derived with his collaborator Bruce Lee Rothschild, Graham found that the said quantity was easier to explain than the actual number appearing in the proof. Because the number which Graham described to Gardner is larger than the number in the paper itself, both are valid upper bounds for the solution to the problem studied by Graham and Rothschild.^[7]

Definition[edit]

Using Knuth’s up-arrow notation, Graham’s number G (as defined in Gardner’s Scientific American article) is

where the number of arrows in each subsequent layer is specified by the value of the next layer below it; that is,

where

and where a superscript on an up-arrow indicates how many arrows there are. In other words, G is calculated in 64 steps: the first step is to calculate g₁ with four up-arrows between 3s; the second step is to calculate g₂ with g₁ up-arrows between 3s; the third step is to calculate g₃ with g₂ up-arrows between 3s; and so on, until finally calculating G = g₆₄ with g₆₃ up-arrows between 3s.

Equivalently,

and the superscript on f indicates an iteration of the function, e.g., . Expressed in terms of the family of hyperoperations , the function f is the particular sequence , which is a version of the rapidly growing Ackermann function A(n, n). (In fact, for all n.) The function f can also be expressed in Conway chained arrow notation as , and this notation also provides the following bounds on G:

Magnitude[edit]

To convey the difficulty of appreciating the enormous size of Graham’s number, it may be helpful to express—in terms of exponentiation alone—just the first term (g₁) of the rapidly growing 64-term sequence. First, in terms of tetration () alone:

where the number of 3s in the expression on the right is

Now each tetration () operation reduces to a power tower () according to the definition

where there are X 3s.

Thus,

becomes, solely in terms of repeated «exponentiation towers»,

and where the number of 3s in each tower, starting from the leftmost tower, is specified by the value of the next tower to the right.

In other words, g₁ is computed by first calculating the number of towers, (where the number of 3s is ), and then computing the n^th tower in the following sequence:

      1st tower:  3
     
      2nd tower:  3↑3↑3 (number of 3s is 3) = 7625597484987
     
      3rd tower:  3↑3↑3↑3↑...↑3 (number of 3s is 7625597484987) = …
     
      ⋮
     
 g1 = nth tower:  3↑3↑3↑3↑3↑3↑3↑...↑3 (number of 3s is given by the n-1th tower)

where the number of 3s in each successive tower is given by the tower just before it. Note that the result of calculating the third tower is the value of n, the number of towers for g₁.

The magnitude of this first term, g₁, is so large that it is practically incomprehensible, even though the above display is relatively easy to comprehend. Even n, the mere number of towers in this formula for g₁, is far greater than the number of Planck volumes (roughly 10¹⁸⁵ of them) into which one can imagine subdividing the observable universe. And after this first term, still another 63 terms remain in the rapidly growing g sequence before Graham’s number G = g₆₄ is reached. To illustrate just how fast this sequence grows, while g₁ is equal to with only four up arrows, the number of up arrows in g₂ is this incomprehensibly large number g₁.

Rightmost decimal digits[edit]

Graham’s number is a «power tower» of the form 3↑↑n (with a very large value of n), so its rightmost decimal digits must satisfy certain properties common to all such towers. One of these properties is that all such towers of height greater than d (say), have the same sequence of d rightmost decimal digits. This is a special case of a more general property: The d rightmost decimal digits of all such towers of height greater than d+2, are independent of the topmost «3» in the tower; i.e., the topmost «3» can be changed to any other non-negative integer without affecting the d rightmost digits.

The following table illustrates, for a few values of d, how this happens. 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 of this table:

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)

The particular rightmost d digits that are ultimately shared by all sufficiently tall towers of 3s are in bold text, and can be seen developing as the tower height increases. For any fixed number of digits d (row in the table), the number of values possible for 33↑…3↑x mod 10^d, as x ranges over all nonnegative integers, is seen to decrease steadily as the height increases, until eventually reducing the «possibility set» to a single number (colored cells) when the height exceeds d+2.

A simple algorithm^[8] for computing these digits may be described as follows: let x = 3, then iterate, d times, the assignment x = 3^x mod 10^d. Except for omitting any leading 0s, the final value assigned to x (as a base-ten numeral) is then composed of the d rightmost decimal digits of 3↑↑n, for all n > d. (If the final value of x has fewer than d digits, then the required number of leading 0s must be added.)

Let k be the numerousness of these stable digits, which satisfy the congruence relation G(mod 10^k)≡[G^G](mod 10^k).

k=t-1, where G(t):=3↑↑t.^[9] It follows that, g₆₃ ≪ k ≪ g₆₄.

The algorithm above produces the following 500 rightmost decimal digits of Graham’s number (OEIS: A133613):

...02425950695064738395657479136519351798334535362521
   43003540126026771622672160419810652263169355188780
   38814483140652526168785095552646051071172000997092
   91249544378887496062882911725063001303622934916080
   25459461494578871427832350829242102091825896753560
   43086993801689249889268099510169055919951195027887
   17830837018340236474548882222161573228010132974509
   27344594504343300901096928025352751833289884461508
   94042482650181938515625357963996189939679054966380
   03222348723967018485186439059104575627262464195387

References[edit]

Bibliography[edit]

• Gardner, Martin (November 1977). «Mathematical Games» (PDF). Scientific American. 237 (5): 18–28. Bibcode:1977SciAm.237e..18G. doi:10.1038/scientificamerican1177-18.; reprinted (revised) in Gardner (2001), cited below.
• Gardner, Martin (1989). Penrose Tiles to Trapdoor Ciphers. Washington, D.C.: Mathematical Association of America. ISBN 978-0-88385-521-8.
• Gardner, Martin (2001). The Colossal Book of Mathematics: Classic Puzzles, Paradoxes, and Problems. New York, NY: Norton. ISBN 978-0-393-02023-6.
• Graham, R. L.; Rothschild, B. L. (1971). «Ramsey’s Theorem for n-Parameter Sets» (PDF). Transactions of the American Mathematical Society. 159: 257–292. doi:10.2307/1996010. JSTOR 1996010. The explicit formula for N appears on p. 290. This is not the «Graham’s number» G published by Martin Gardner.
• Graham, R. L.; Rothschild, B. L. (1978). «Ramsey Theory». In Rota, G-C (ed.). Studies in Combinatorics (MAA Studies in Mathematics). Vol. 17. Mathematical Association of America. pp. 80–99. ISBN 978-0-88385-117-3. On p. 90, in stating «the best available estimate» for the solution, the explicit formula for N is repeated from the 1971 paper.

External links[edit]

• OEIS sequence A133613 (Graham’s number)
• Sbiis Saibian’s article on Graham’s number
• «A Ramsey Problem on Hypercubes» by Geoff Exoo
• Mathworld article on Graham’s number
• How to calculate Graham’s number
• Conceptualizing Graham’s number
• Some Ramsey results for the n-cube prepublication mentions Graham’s number
• Padilla, Tony; Parker, Matt. «Graham’s Number». Numberphile. Brady Haran. Archived from the original on 2014-05-27. Retrieved 2013-04-08.
• Archived at Ghostarchive and the Wayback Machine: Ron Graham. «What is Graham’s Number? (feat Ron Graham)» (video). Numberphile. Brady Haran.
• Archived at Ghostarchive and the Wayback Machine: Ron Graham. «How Big is Graham’s Number? (feat Ron Graham)» (video). Numberphile. Brady Haran.
• The last 16 million digits of Graham’s number by the Darkside communication group

Если долго всматриваться в бездну, бездна начнёт всматриваться в тебя.

Ницше

Число Грэма (число Грехема, англ. Graham’s number) — ебически огромное число, которое вывел внезапно Рональд Грэм как верхний предел в хуй никому не упёршейся проблемы с раскрашенными гиперкубами из теории Рамсея. То есть, предупреждая вопросы отдельных личностей «почему именно столько, а не столько плюс адын» — это не просто взятая от балды величина, это решение конкретной задачи.

Суть[править]

Проблема с кубами в теории Рамсея состоит в том, что это никакая не проблема, а одна из задач в комбинаторике, где любят переставлять или красить мелкие части одного большого множества и смотреть, что интересного может получиться. В нашем случае предлагается взять n-мерный кубик, соединить его вершины линиями, и каждое получившееся ребро покрасить одним цветом из двух — либо синим, либо красным. Суть в том, чтобы понять, до какого значения n можно, по-разному закрашивая рёбра, избежать ситуации, когда одна плоскость в кубе закрашена одним цветом. То есть, мы не хотим, чтобы получался одноцветный конвертик, как на картинке. Математики посидели-позакрашивали — видят, что в обычном кубике это сделать легче лёгкого. Добавили ещё измерение (получился тессеракт), снова позакрашивали — получилось, избежать конвертика можно. Добавили пятое, шестое, седьмое — всё отлично! Но тут пришёл Грэм и сказал, что они занимаются хуитой, и он-де сразу сейчас посчитает, при каком количестве измерений одноцветный конвертик будет получаться по-любому. ИЧСХ, посчитал-таки, однако искомым решением это назвать нельзя.

Дело в том, что теорема предлагает найти наименьшее количество измерений с нарушением условия появления одноцветной плоскости. Но хитрый Грэм подумал и решил, что считать по порядку никакого терпения не хватит. Он подозревал, что количество измерений будет большим, но не бесконечным, поэтому, применив специальное кунг-фу из комбинаторики, посчитал сразу максимальное количество этих самых измерений. Этим приёмом он не нашёл решения теоремы, но обозначил верхнюю границу поисков. То есть, если вдруг начнёте решать эту задачу с гиперкубами, то размерности больше числа Грэма можете не брать. И на сегодняшний день та самая минимальная размерность гиперкуба лежит между 13-ю измерениями и, собственно, числом Грэма. Таким образом, число Грэма — это верхний предел количества измерений гиперкуба, при котором точно невозможно избежать подграфа, закрашенного одним цветом.

Популярность[править]

Хотя ныне в математике используются числа, которые в 100500 раз больше, чем число Грэма, все они не настолько известны по ряду причин. Во-первых, на число Грэма обратил внимание широкой публики такой популяризатор матана, как Мартин Гарднер, написав колонку в научном журнале, где сказал, что Грэм совсем охуел придумывать такие числа. А в 1980 году число и вовсе попало в книгу рекордов Гиннесса, где ему был приписан рекорд как самому большому числу, когда-либо использовавшемуся в математическом доказательстве. В довесок ко всему, сам «способ» вычисления этой величины довольно понятен простому смертному (это просто перемноженные по несложному алгоритму тройки). После этого все мало-мальски знакомые с матаном стали фапать на это число, пытаясь как-то представить себе и объяснить другим масштаб этого числа. Но не тут-то было…

Эпичность[править]

…, ведь число риальнэ БОЛЬШОЕ. Нет, правда. На самом деле, оно больше любых самых смелых фантазий. Представьте себе цифру, написанную самым мелким шрифтом. Таким мелким, что на атоме можно нарисовать миллионы таких цифр. Представьте себе пространство, заполненное этими цифрами во всех трёх измерениях, вплотную друг к другу. Так вот, места, чтобы вместить десятичную запись числа Грэма, потребуется гораздо больше всей наблюдаемой Вселенной. Мало того, оно не вместится даже в количество Вселенных, равное количеству цифр, помещённых в нашу Вселенную. И так далее… ну ты понел. Продолжать можно, пока клавиатура не сотрётся. А когда сотрётся, сходить за новой и убить тоже. Кстати, до сих пор мы говорили только о количестве цифр, из которых состоит число Грэма, а не о самом числе (например, миллиард секунд — это почти 32 года, но в самом числе «миллиард» всего 10 цифр, которые можно пересчитать за 10 секунд)! Никакие гуголы с гуголплексами тут даже рядом не стояли.

Но все эти эпитеты и аналогии всё равно не отражают масштаба трагедии. По-настоящему заклинить свой МНУ ты можешь, попытавшись вникнуть в принцип вычисления этого числа. А чтобы не пугать честной норот простынёй непонятных знаков, мы положим его под половицу.

Мякотка числа также в том, что, несмотря на невозможность записать число полностью, вполне возможно вычислить его последние цифры. Нерды от матана, сперва немного охуев от масштаба числа, взяли себя в руки и высчитали более 500 цифр с конца этого числа. Вот десять самых последних: …2464195387. А какая цифра первая? Ну, калькулятор вам в руки, только имейте в виду, что тепловая смерть Вселенной прервёт ваши вычисления в самом начале.

Moar[править]

Но время идёт, математики не сидят сложа руки, и невозможное для осознания число Грэма больше не является чем-то особенным. В настоящее время самым большим числом является величина под названием «Число Райо» (Rayo’s number). У него даже есть формула и алгоритм вычисления, только вот посчитать как-то не удаётся: мощностей не хватает (и вряд ли когда-нибудь хватит). Поэтому, чтобы хоть как-то его определять, для него придумали следующую языковую конструкцию: «Самое маленькое число, большее, чем любое конечное число, определённое выражением на языке теории множеств с использованием гугола символов или меньше». Аплодисменты.

Видеота[править]

Годное видео про сабж. Видеоряд доставляет…

О сабже с 18-й минуты

Интересные факты[править]

• Онотоле знает все цифры этого числа. Но вам не скажет.
• Результат степенной башни из гуголплексов в гуголплекс этажей неизмеримо меньше числа Грэма.

См. также[править]

• Четвёртое измерение
• Квадратура круга

Ссылки[править]

• Подробнейшее описание, написанное доставляющим языком
• Число Райо — победитель конкурса в MIT
• Джон Литлвуд о записи самых больших чисел (п. 15), 1948 год
• Ещё одна попытка объяснить вычисление числа Грэма

«Не учишь матан – пойдёшь на метан» © Луговский
Науки	Высшая математика • Евгеника • Матан • Российская • Сопромат • Философия (Детерминизм)
Достижения	TeX • Атомная бомба • Биореактор • Большой адронный коллайдер • ГМО • Двести двадцать • Корчеватель • Кубик Рубика • Нанотехнологии • Палата мер и весов • Резонатор Гельмгольца • Роботы • Термоядерный синтез • Чернобыль • Экзоскелет • Фукусима
Теории и открытия	Геометрия Лобачевского • Звездчатый многоугольник • Квантовая механика • Когнитивная психология • Популяционная теория Мальтуса • Радиация • Тёмная энергия • Теория большого взрыва (сериал) • Теория относительности • Теория разбитых окон • Теория струн • Четвёртое измерение • Чёрная дыра • Эволюция • Элементарные частицы • Энтропия
Мемы	265 • xkcd • Бритва Оккама • Деление на ноль (Яценюк) • Дигидрогена монооксид • Задача Льва Толстого • Задача Эйнштейна • Закон Мерфи • Закон Парето • Квадратно-гнездовой способ мышления • Квадратура круга • Коробочка фотонов • Кот Шрёдингера • Матановая капча • Критерий Поппера • Метод научного тыка • Пик нефти • Поймать льва в пустыне • Простые числа • Рекурсия • Сферический конь в вакууме • Теорема Абеля — Галуа • Теорема Ферма • Число Грэма • Число Эрдёша
Люди и организации	Организации (ИТМО • МФТИ • НМУ) • Байрон • Белоненко • Березовский • Вассерман • Вербицкий • да Винчи • Декарт • Докинз • Инженер • Кэрролл • Лаборатория • Лейбниц • Луговский (цитатник) • Паскаль • Перельманы (Григорий • Яков) • Переслегин • Пятисемиты • Саган • Тейлор • Тесла • Технофашисты • Фейнман • Хайям • Хокинг • Эшер
Паранаука	Science freaks/Научное фричество • Scorcher.ru • Артефакт • Великая тайна воды • Вечный двигатель • Гомеопатия • ГСМ • Информационное поле Вселенной • Квадратно-гнездовой способ мышления • Научный креационизм (аргументы) • НЛП • Принцип Арнольда • Соционика • Телегония • Торсионные поля • ХУЯС • Электронный голосовой феномен
Фрики и шарлатаны	Sherak • Британские учёные • Бронников • Гаряев • Жданов • Катющик • Лотов • Лысенко • Малахов • Мулдашев • Мухин • Никонов • Олег Т. • Петрик • Протопопов • РАЕН • Скляров • Стерлигов • Фоменко • Чащихин • Чернобров • Чудинов • Чурляев • Чуров
Срачи	Бесполезная наука • Взлетит или не взлетит? • Дети индиго • Луносрач • Наука vs религия • Пирамидосрач • Плутоносрач • Физики vs лирики • Шмель летать не должен

Всё это – часть точного мира чисел
Числа и цифры	+1 • 1.0 • 2.0 • π • 3,5 • 3,62 • 8/64 • 13 • 14/88 • 16 • 19 • 20 • 25 • 28 • 34 • 38 • 40 • 42 • 51 • 57 • 63 • 77 • 80 • 101 • 121 • 128 • 220 • 228 • 265 • 282 • 314 • 322 • 359 • 404 • 410 • 502 • 640 • 646 • 666 • 1111 • 1138 • 1200+ε • 1337 • 1500 • 1812 • 2000 • 2300 • 3310 • 3605 • 3730 • 9000 • 9600 • 12309 • 40 000 • 100500 • 260602 • 13 000 000 • 1 000 000 000 (Сталинский • Золотой) • 1 208 925 819 614 629 174 706 176 • G64 • ∞
Проценты	90% женщин • 95% населения • Инфа 100% • 146%
Время	3 секунды • 5 секунд • Полшестого • 7:40 • 10:10 • 1917 год • 1980-е (1984 год) • 1990-е • 2000-е (2000 год) • 2010-е (2012 год)
Прочее	1 Guy 1 Jar • 2 Girls 1 Cup • ⑨ • Sweet home • 2 в 1 • 3 Guys 1 Hammer • 58 видов геев • Автомобильные номера • Гет • ДЕЕ1991ГР • Деление на ноль • Закон Парето • Код • Матан • Матановая капча • Натуральные числа • Простые числа • Вещественные числа • Рулетка • Сотни нефти • Теорема Ферма • Теория относительности • Чуть более, чем наполовину • Семь чудес света • Квадратура круга • Три обезьяны • Monkey dust

Число Грэма (Грехема, англ. Graham’s number) — большое число, которое является верхней границей для решения определённой проблемы в теории Рамсея. Названо в честь Рональда Грэма (англ.).

Оно стало известно широкой публике после того, как Мартин Гарднер описал его в своей колонке «Математические игры» в журнале Scientific American в ноябре 1977 года, где было сказано: «В неопубликованном доказательстве Грэм недавно установил … границу настолько большую, что ей принадлежит рекорд как наибольшему числу, когда-либо использовавшемуся в серьёзном математическом доказательстве».

В 1980 году Книга рекордов Гиннесса повторила утверждения Гарднера, ещё больше подогрев интерес публики к этому числу. Число Грехема в невообразимое количество раз больше, чем другие хорошо известные большие числа, такие, как гугол, гуголплекс и даже больше, чем число Скьюза и число Мозера. На самом деле, вся наблюдаемая вселенная слишком мала для того, чтобы вместить в себя обыкновенную десятичную запись числа Грехема, предполагая, что запись каждой цифры занимает по меньшей мере объём Планка. Даже степенные башни вида бесполезны для этой цели, хотя это число и может быть записано с использованием рекурсивных формул, таких как стрелочная нотация Кнута или эквивалентных, что и было сделано Грехемом. Последние 500 цифр числа Грехема — это …02425950695064738395657479136519351798334535362521 43003540126026771622672160419810652263169355188780 38814483140652526168785095552646051071172000997092 91249544378887496062882911725063001303622934916080 25459461494578871427832350829242102091825896753560 43086993801689249889268099510169055919951195027887 17830837018340236474548882222161573228010132974509 27344594504343300901096928025352751833289884461508 94042482650181938515625357963996189939679054966380 03222348723967018485186439059104575627262464195387.

В современных математических доказательствах иногда встречаются числа, ещё много бо́льшие, чем число Грехема, например, в работе с конечной формой Фридмана в теореме Краскала.

Проблема Грехема

Число Грехема связано со следующей проблемой в теории Рамсея:

Рассмотрим n-мерный гиперкуб и соединим все пары вершин для получения полного графа с вершинами. Раскрасим каждое ребро этого графа либо в красный, либо в чёрный цвет. При каком наименьшем значении n каждая такая раскраска обязательно содержит раскрашенный в один цвет полный подграф с четырьмя вершинами, все из которых лежат в одной плоскости?

Грехем и Ротшильд в 1971 году доказали, что эта проблема имеет решение, N*, и показали что 6 ≤ N* ≤ N, где N — конкретное, точно определённое, очень большое число. На языке стрелочной нотации Кнута оно может быть записано как , где .

Нижняя граница была улучшена Экзу в 2003 году и Баркли в 2008 году, который показал, что N* должно быть не меньше 13. Таким образом, 13 ≤ N* ≤ N.

Предметом настоящей статьи является верхняя граница G, которая много слабее (то есть больше), чем N; а именно , где . Именно эта граница, описанная в неопубликованной работе Грехема, и была описана (и названа числом Грехема) Мартином Гарднером.

Определение числа Грехема

Используя стрелочную нотацию Кнута, число Грехема G может быть записано как

где количество стрелок в каждом слое, начиная с верхнего, определяется числом в следующем слое, то есть

и где верхний индекс у стрелки показывает общее количество стрелок. Другими словами, G вычисляется в 64 шага: на первом шаге мы вычисляем g₁ с четырьмя стрелками между тройками, на втором — g₂ с g₁ стрелок между тройками, на третьем — g₃ с g₂ стрелок между тройками и так далее, в конце мы вычисляем G = g₆₄ с g₆₃ стрелок между тройками.

Это может быть записано как

где верхний индекс у f означает итерации функций. Функция f является частным случаем гипероператоров, , и может быть так же записана при помощи цепных стрелок Конвея как . Последняя запись так же позволяет записать следующие граничные значения для G:

Масштаб числа Грехема

Для того, чтобы осознать невероятный размер числа Грехема, полезно попробовать представить через возведение в степень хотя бы первый член (g₁) стремительно растущей 64-членной последовательности. На языке тетраций означает:

где число троек в выражении справа

Теперь каждая тетрация () по определению разворачивается в «степенную башню» как

, где X — количество 3-ек.

Таким образом,

, где количество троек —

записанное на языке степеней

, где число башен —

и где количество троек в каждой башне, начиная слева, указывается предыдущей башней.

Другими словами, g₁ вычисляется путём вычисления количества башен, n = (где число троек — = 7625597484987), и затем вычисляя n башен в следующем порядке:

      1ая башня:  3

      2ая башня:  3↑3↑3 (количество троек — 3) = 7625597484987

      3я башня:  3↑3↑3↑3↑...↑3 (количество троек — 7625597484987) = ...

      .
      .
      .

 g1 = nая башня:  3↑3↑3↑3↑3↑3↑3↑...↑3 (количество троек задаётся результатом вычисления n-1ой башни)

Масштаб первого члена, g₁, настолько велик, что его практически невозможно осознать, хотя запись выше относительно проста для понимания. Хотя n это всего лишь количество башен в этой формуле для g₁, уже это число много больше количества объёмов Планка, которые содержатся в наблюдаемой вселенной (примерно 8.5*10¹⁸⁵). После первого члена нас ожидает ещё 63 члена стремительно растущей последовательности.

См. также

• теорема Краскала
• функция Аккермана

Литература

• Graham, R. L.; Rothschild, B. L. (1971). «Ramsey’s Theorem for n-Parameter Sets». Transactions of the American Mathematical Society 159: 257-292. DOI:10.2307/1996010. The explicit formula for N appears on p. 290.
• Graham, R. L.; Rothschild, B.L. (1978). «Ramsey Theory», Studies in Combinatorics, Rota, G.-G., ed., Mathematical Association of America, 17:80-99. On p. 90, in stating «the best available estimate» for the solution, the explicit formula for N is repeated from the 1971 paper.
• Gardner, Martin (November 1977). «Mathematical Games». Scientific American 237: 18-28.; reprinted (revised 2001) in the following book:
• Gardner Martin The Colossal Book of Mathematics: Classic Puzzles, Paradoxes, and Problems. — New York, NY: Norton, 2001. — ISBN 0393020231
• Gardner Martin Penrose Tiles to Trapdoor Ciphers. — Washington, D.C.: Mathematical Association of America, 1989. — ISBN 0-88385-521-6
• Exoo, Geoffrey (2003). «A Euclidean Ramsey Problem». Discrete Computational Geometry 29: 223-227. DOI:10.1007/s00454-002-0780-5.

Ссылки

• «Проблема Рамсей о гиперкубах». Geoff Exoo (англ.)
• Weisstein, Eric W. Graham’s number (англ.) на сайте Wolfram MathWorld.
• Как вычислить число Грэма (англ.)
• Numeropedia — the Special Encyclopedia of Numbers (англ.)

Числа с собственными именами
Вещественные	Пи • Золотое сечение • Серебряное сечение • e (число Эйлера) • Постоянная Эйлера — Маскерони • Постоянные Фейгенбаума • Постоянная Гельфонда • Константа Бруна • Постоянная Каталана • Постоянная Апери
Натуральные	Чёртова дюжина • Число зверя • Число Рамануджана — Харди • Число Грэма • Число Скьюза • Число Мозера
Степени десяти	Мириада • Гугол • Асанкхейя • Гуголплекс
Степени тысячи	Тысяча • Миллион • Миллиард • Биллион • Триллион • Квадриллион • … • Центиллион
Степени двенадцати	Дюжина • Гросс • Масса