Ver la fonte de Númberu de Graham

El '''númberu de Graham''', que recibe'l so nome de [[Ronald Graham]], ye un [[númberu grande]] que ye una [[cota cimera]] de la solución d'un determináu problema na [[teoría de Ramsey]]. Esti númberu consiguió cierta fama popular cuando [[Martin Gardner]] escribió na seición «Mathematical Games» (''Xuegos Matemáticos'') de la revista ''[[Scientific American]]'' en payares de 1977:
{{cita|Nuna demostración ensin publicar, Graham estableció apocayá ... una cota tan vasta que tien el rexistru de ser el mayor númberu enxamás usáu nuna demostración matemática seria.<ref>N'inglés nel orixinal: ''In an unpublished proof, Graham has recently established ... a bound so vast that it holds the record for the largest number ever used in a serious mathematical proof.''</ref>}}
El [[Llibru Guinness de los récores]], na so edición de 1980, repitió l'afirmación de Gardner, lo que contribuyó al interés popular d'esti númberu. El númberu de Graham ye enforma mayor qu'otros conocíos númberos grandes tales como'l [[gúgol]], el [[gúgolplex]] ya inclusive'l [[númberu de Skewes]] y el [[númberu de Moser|de Moser]]. Ello ye que ye imposible, daes les llimitaciones d'espaciu y materia del nuesu [[universu]], denota'l númberu de Graham o un aproximamientu razonable del mesmu nun [[sistema de numberación]] convencional. Inclusive les «[[tetración|torres d'esponentes]]» de la forma <math>a ^{ b ^{ c ^{ \cdot ^{ \cdot ^{ \cdot}}}}}</math> revélense inútiles pa esti propósitu, anque'l númberu puede ser descritu con fórmules recursives per aciu de la [[notación flecha de Knuth]] o fórmules equivalentes, como fixo Graham. Los diez últimos díxitos del númberu de Graham son ...2464195387. Anguaño, considéraselu como'l númberu representáu matemáticamente más grande de toos.

Dende'l descubrimientu y usu del númberu de Graham, emplegáronse númberos tovía mayores n'otres demostraciones matemátiques, por casu, rellacionaes coles variaes formes finites de Friedman del [[teorema de Kruskal]].

== Problema de Graham ==

El númberu de Graham ta rellacionáu col siguiente problema perteneciente a la caña de les matemátiques conocida como la [[teoría de Ramsey]]:

{{teorema|Considérese un [[hipercubo]] ''n''-dimensional, y conéctese cada par de [[Vértiz (teoría de grafos)|vértices]] pa llograr un [[grafo completu]] con <math>2^n</math> vértices. Darréu, coloréese caúna de les arestes de negru o de colloráu. ¿Cuál ye'l menor valor de ''n'' pal cual toa manera de colorear les arestes necesariamente da llugar a un subgrafo completu d'un solu color con 4 vértices que formen un planu?}}

Graham y Rothschild [1971] demostraron qu'esti problema tien una solución, ''N*'', y dieron como acotación de la mesma 6 ≤ ''N*'' ≤ ''N'', siendo ''N'' un númberu determináu, definíu explícitamente y bien grande; sicasí, Graham (nun trabayu ensin publicar) revisó esta cota cimera a l'alza. Esta cota cimera revisada por Graham foi darréu publicada (y moteyada ''númberu de Graham'') por Martin Gardner en [''Scientific American'', "Mathematical Games", payares de 1977].

La cota inferior foi darréu ameyorada por Exoo [2003], quien amosó que la solución ye siquier 11 y apurrió evidencia esperimental que suxería que yera siquier 12. Con esto, la estimación más conocida pa la solución ''N*'' ye 11 ≤ ''N*'' ≤ ''G'', onde ''G'' ye'l númberu de Graham.

= Definición del númberu de Graham ==

Por aciu la [[notación flecha de Knuth]], el númberu de Graham, ''G'', tal como se define nel artículu de Gardner en ''Scientific American'', equival a:

:<math> 
\left. 
 \begin{matrix} 
 G &=&3\underbrace{\uparrow \uparrow \cdots\cdots\cdots\cdots\cdots \uparrow}3 \\
 & &3\underbrace{\uparrow \uparrow \cdots\cdots\cdots\cdots \uparrow}3 \\ 
 & &\underbrace{\qquad\;\; \vdots \qquad\;\;} \\ 
 & &3\underbrace{\uparrow \uparrow \cdots\cdot\cdot \uparrow}3 \\
 & &3\uparrow \uparrow \uparrow \uparrow3
 \end{matrix} 
\right \} \text{64 files}
</math>
: 
onde'l númberu de fleches en cada fila, empezando pola fila cimera, vien especificáu pol valor de la fila darréu inferior, esto ye,

:<math>G = g_{64},\text{ onde }g_1=3\uparrow\uparrow\uparrow\uparrow 3,\ g_n = 3\uparrow^{g_{n-1}}3,</math>

onde un superíndice nuna flecha cimera indica cuántes fleches hai. N'otres pallabres, ''G'' calcúlase al traviés de 64 pasos: el primer pasu consiste en calcular ''g''<sub>1</sub> con cuatro fleches ente los treses; el segundu pasu consiste en calcular ''g''<sub>2</sub> con ''g''<sub>1</sub> fleches ente los treses, el tercer pasu consiste en calcular ''g''<sub>3</sub> con ''g''<sub>2</sub> fleches ente los treses, y asina socesivamente hasta calcular finalmente ''G'' = ''g''<sub>64</sub>, que tien ''g''<sub>63</sub> fleches ente los treses.

Equivalentemente, 

:<math>G = f^{64}(4),\text{ onde }f(n) = 3 \uparrow^n 3,</math>

onde un superíndice na ''f'' indica la [[función iterada|iteración de la función]]. La función ''f'' ye un casu especial de la familia de funciones [[hiperoperador|hiper()]], <math>f(n) = \text{hiper}(3,n+2,3)</math>, y tamién puede espresase por aciu la [[notación de fleches encadenaes de Conway]] como <math>f(n) = 3 \rightarrow 3 \rightarrow n</math>. Esta última notación establez les siguientes cotes pa ''G'':
 
<math> 3\rightarrow 3\rightarrow 64\rightarrow 2 < G < 3\rightarrow 3\rightarrow 65\rightarrow 2.\, </math>

=== Magnitú del númberu de Graham ===

Col fin de faer notar la dificultá d'entender la enorme magnitú del númberu de Graham, pue ser útil espresar (por aciu la mera exponenciación) namái'l primer términu (''g''<sub>1</sub>) de la socesión rápido creciente de 64 términos. Primero, espresemos el númberu por aciu la [[tetración]] (<math>\uparrow\uparrow</math>):

:<math> 
g_1 
= 3 \uparrow \uparrow \uparrow \uparrow 3 
= 3 \uparrow \uparrow \uparrow (3 \uparrow \uparrow \uparrow 3) 
= 3 \uparrow\uparrow (3 \uparrow\uparrow (3 \uparrow\uparrow \ \dots \ (3 \uparrow\uparrow 3) \dots ))
</math>

onde'l númberu de treses na espresión de la derecha ye 

:<math>3 \uparrow \uparrow \uparrow 3 \ = \ 3 \uparrow \uparrow (3 \uparrow \uparrow 3).</math>

Agora cada tetración (<math>\uparrow\uparrow</math>) amenorgar a una torre» de exponenciaciones (<math>\uparrow</math>) según la definición

:<math>3 \uparrow\uparrow X \ = \ 3 \uparrow (3 \uparrow (3 \uparrow \dots (3 \uparrow 3) \dots )) \ = \ 3^{3^{\cdot^{\cdot^{\cdot^{3}}}}} \quad \text{onde hai X treses}.</math>

Por tanto,

:<math>g_1 = 3 \uparrow\uparrow (3 \uparrow\uparrow (3 \uparrow\uparrow \ \dots \ (3 \uparrow\uparrow 3) \dots )) \quad \mathrm{onde'l~~n\acute umero~de treses~~ye}\, \quad 3 \uparrow \uparrow (3 \uparrow \uparrow 3)</math>

, namái emplegando «torres d'esponentes», convertir en 

:<math>
g_1 = 
 \left. 
 \begin{matrix}3^{3^{\cdot^{\cdot^{\cdot^{\cdot^{3}}}}}}\end{matrix}
 \right \} 
 \left. 
 \begin{matrix}3^{3^{\cdot^{\cdot^{\cdot^{3}}}}}\end{matrix}
 \right \}
 \dots 
 \left. 
 \begin{matrix}3^{3^3}\end{matrix}
 \right \}
 3
 \quad \mathrm{onde'l~~n\acute umero~de torres~~ye} \quad 
 \left. 
 \begin{matrix}3^{3^{\cdot^{\cdot^{\cdot^{3}}}}}\end{matrix}
 \right \}
 \left. 
 \begin{matrix}3^{3^3}\end{matrix}
 \right \}
 3
</math>

y onde el númberu de treses en cada torre, empezando pola torre asitiada más a la izquierda, vien especificáu pol valor de la torre asitiada darréu a la so derecha. Espandiendo verticalmente, esto conviértese en

:<math> 
g_1 
= 3 \uparrow \uparrow \uparrow \uparrow 3 
= 3 \uparrow \uparrow \uparrow (3 \uparrow \uparrow \uparrow 3) 
= 3 \uparrow \uparrow \uparrow 
 \left( 
 \underbrace{3^{3^{\cdot^{\cdot^{\cdot^{3}}}}}}_{3^{3^3}\text{copies de 3}}
 \right)
= \left.
 \begin{matrix}
 \underbrace{3^{3^{\cdot^{\cdot^{\cdot^{3}}}}}}_{\underbrace{3^{3^{\cdot^{\cdot^{\cdot^{3}}}}}}_{3^{3^{\cdot^{\cdot^{\cdot^{3}}}}}\text{copies de 3}}\text{copies de 3}} \\
 \vdots \\
 \underbrace{3^{3^{\cdot^{\cdot^{\cdot^{3}}}}}}_{\underbrace{3^{3^{\cdot^{\cdot^{\cdot^{3}}}}}}_{3^{3^3}\text{copies de 3}}\text{copies de 3}}\text{copies de 3}
 \end{matrix}
 \right \}
 \left. \underbrace{3^{3^{\cdot^{\cdot^{\cdot^{3}}}}}}_{3^{3^3}\text{copies de 3}}
 \right. \text{files} 
</math>

La magnitú d'esti primer términu, ''g''<sub>1</sub>, ye tan grande que práuticamente escapa a la comprensión humana. Inclusive'l ''númberu de torres'' presentes nesta fórmula pa ''g''<sub>1</sub> ye enforma mayor que'l númberu de [[volume de Planck|volúmenes de Planck]] nos que podría estremase l'universu observable. Y cabo sorrayar que, dempués d'esti términu, queden otros 63 más nesta socesión rápido creciente antes de llegar al númberu de Graham, ''G'' = ''g''<sub>64</sub>.

== Últimes cifres del númberu de Graham ==

El númberu de Graham ye una torre d'esponentes» de la forma 3<math>\uparrow\uparrow</math>''n'' (con un valor bien grande de ''n''), polo que les sos últimes cifres en base decimal tienen de satisfaer ciertes propiedaes comunes a cualquier torre d'esti tipu. Una d'estes propiedaes ye que ''toles torres d'esti tipu d'altor mayor que d presenten la mesma socesión de d cifres decimales asitiaes nos últimos llugares''. Este ye un casu especial d'una propiedá más xeneral: les ''d'' últimes cifres decimales de toles torres d'esti tipu d'altor mayor que ''d''+2 son ''independientes'' del "3" asitiáu na parte cimera de la torre, esto ye, el 3 asitiáu enriba del tou puede camudase por cualesquier otru enteru non negativu ensin afectar les ''d'' últimes cifres decimales.

La siguiente tabla ilustra, pa unos pocos valores de ''d'', cómo asocede esto. Pa un altor dau de la torre y un númberu de cifres ''d'', nun se presenta'l conxuntu enteru de númberos naturales de ''d'' cifres (de los qu'hai 10<sup>''d''</sup>, cuntando los que tienen ceros iniciales), sinón que se presenta un subconxuntu amenorgáu de valores que se repite cíclicamente. El llargor del ciclu y dalgunos de los sos valores (ente paréntesis) amosar en caúna de les celdes de la tabla:

{| {{tablaguapa}} style="text-align:center" cellpadding="5"
|+ Númberu de valores posibles de 3<math>\uparrow</math>3<math>\uparrow</math>...3<math>\uparrow</math>''x'' cuando s'ignoren toles cifres menos les ''d'' últimes<br />
! width="150pt" | Númberu de cifres (''d'') !! width="40pt" | 3<math>\uparrow</math>''x'' !! width="60pt" | 3<math>\uparrow</math>3<math>\uparrow</math>''x'' !! width="80pt" | 3<math>\uparrow</math>3<math>\uparrow</math>3<math>\uparrow</math>''x'' !! width="100pt" | 3<math>\uparrow</math>3<math>\uparrow</math>3<math>\uparrow</math>3<math>\uparrow</math>''x'' !! width="120pt" | 3<math>\uparrow</math>3<math>\uparrow</math>3<math>\uparrow</math>3<math>\uparrow</math>3<math>\uparrow</math>''x''
|-
! 1 
| 4<br />(1,3,9,'''7''') || 2<br />(3,'''7''') || style="background:#05FFD3;" | 1<br />('''7''')|| style="background:#05FFD3;" | 1<br />('''7''') || style="background:#05FFD3;" | 1<br />('''7''')
|-
! 2
| 20<br />(01,03,...,'''87''',...,67) || 4<br />(03,27,83,'''87''') || 2<br />(27,'''87''') || style="background:#05FFD3;" | 1<br />('''87''') || style="background:#05FFD3;" | 1<br />('''87''')
|-
! 3
| 100<br />(001,003,...,'''387''',...,667) || 20<br />(003,027,...'''387''',...,587) || 4<br />(027,987,227,'''387''')|| 2<br />(987,'''387''') || style="background:#05FFD3;" | 1<br />('''387''')
|}

Les ''d'' cifres asitiaes nos últimos llugares que son comunes a toles torres ''abondo altes''' de treses tán en negrines, y pueden verificase desenvolviendo la torre a midida que aumenta'l so altor. Pa tou númberu fixu de cifres ''d'' (representáu nes files de la tabla), el númberu de valores posibles pa 3<math>\uparrow</math>3<math>\uparrow</math>...3<math>\uparrow</math>''x'' mod 10<sup>''d''</sup>, cuando ''x'' cubre los enteros non negativos, escai progresivamente a midida que aumenta l'altor, hasta amenorgase a un solu valor (nes celdes con fondu azul) cuando l'altor ye mayor que ''d''+2.

Puede describise un algoritmu simple<ref>[http://mathforum.org/library/drmath/view/51625.html The Math Forum @ Drexel ("Last Eight Digits of Z")]</ref> pa calcular estes últimes cifres d'esta manera: sía x = 3, depués itérese ''d'' vegaes l'[[asignación]] ''x'' = 3<sup>''x''</sup> mod 10<sup>''d''</sup>. L'últimu valor asignáu a ''x'' (como númberu en base 10) ta compuestu poles ''d'' últimes cifres decimales de 3<math>\uparrow\uparrow</math>''n'', pa tou ''n'' > ''d''. (Si l'últimu valor de ''x'' namái tien ''d''-1 cifres, basta con añader un 0 a la izquierda.) 

Siguiendo esti algoritmu, los cien últimes cifres del númberu de Graham (o de cualquier torre con más de cien veces trelce) son:

 ...9404248265018193851562535
 7963996189939679054966380
 0322234872396701848518643
 9059104575627262464195387.

== Temes rellacionaes ==
* [[Función de Ackermann]]
* [[Tetración]]
* [[Gúgol]]

== Referencies ==
{{llistaref}}

== Bibliografía ==
* {{cita publicación|autor=Graham, R. L. |autor2= Rothschild, B. L.|títulu=Ramsey's Theorem for n-Parameter Sets |publicación= Transactions of the American Mathematical Society|volume=159|páxines=257–292|añu=1971|doi=10.2307/1996010}}
* {{cita publicación|autor=Gardner, Martin|títulu=Mathematical Games|publicación= Scientific American|volume=237|páxines=18–28|fecha = payares de 1977}}; reprinted (revised 2001) in the following book:
* {{cita llibru|añu=2001|títulu=The Colossal Book of Mathematics: Classic Puzzles, Paradoxes, and Problems|isbn=0393020231|nome=Martin|apellíos=Gardner |enllaceautor= Martin Gardner|editorial=Norton|allugamientu=New York, NY}}
* {{cita llibru|añu=1989|títulu=Penrose Tiles to Trapdoor Ciphers|isbn=0-88385-521-6|nome=Martin|apellíos=Gardner |enllaceautor= Martin Gardner|editorial=Mathematical Association of America|ubicación=Washington, D.C.}}
* {{cita publicación|autor=Exoo, Geoffrey|títulu=A Euclidean Ramsey Problem|publicación= Discrete Computational Geometry|volume=29|páxines=223–227|añu=2003|doi=10.1007/s00454-002-0780-5}}

== Enllaces esternos ==
'''N'inglés''':
* "{{Enllaz rotu|1=A Ramsey Problem on Hypercubes |2=http://isu.indstate.edu/gue/GEOMETRY/cubes.html |date=August 2024 |bot=InternetArchiveBot }}" por Geoff Exoo
* {{MathWorld|GrahamsNumber|El númberu de Graham}}
* [http://www-users.cs.york.ac.uk/susan/cyc/g/graham.htm Cómo calcular el númberu de Graham]
* [https://web.archive.org/web/20090907131112/http://numeropedia2.googlepages.com/SpeciallyLargeNumbers Numeropedia - the Special Encyclopedia of Numbers]




{{Tradubot|Número de Graham}}

{{control d'autoridaes}}
[[Categoría:Grandes númberos]]