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:

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 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 «torres d'esponentes» de la forma a ^{ b ^{ c ^{ \cdot ^{ \cdot ^{ \cdot}}}}} 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:

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:

: 
\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}

: 
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,

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

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*1 con cuatro fleches ente los treses; el segundu pasu consiste en calcular *g*2 con *g*1 fleches ente los treses, el tercer pasu consiste en calcular *g*3 con *g*2 fleches ente los treses, y asina socesivamente hasta calcular finalmente *G* = *g*64, que tien *g*63 fleches ente los treses.

Equivalentemente, 

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

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

### 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*1) de la socesión rápido creciente de 64 términos. Primero, espresemos el númberu por aciu la tetración (\uparrow\uparrow):

: 
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 ))


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

:3 \uparrow \uparrow \uparrow 3 \ = \ 3 \uparrow \uparrow (3 \uparrow \uparrow 3).

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

: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}.

Por tanto,

: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)

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

:
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


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

: 
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} 


La magnitú d'esti primer términu, *g*1, ye tan grande que práuticamente escapa a la comprensión humana. Inclusive'l *númberu de torres* presentes nesta fórmula pa *g*1 ye enforma mayor que'l númberu de 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*64.

## Últimes cifres del númberu de Graham

El númberu de Graham ye una torre d'esponentes» de la forma 3\uparrow\uparrow*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*d*, 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:

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\uparrow3\uparrow...3\uparrow*x* mod 10*d*, 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 pa calcular estes últimes cifres d'esta manera: sía x = 3, depués itérese *d* vegaes l'asignación *x* = 3*x* mod 10*d*. L'últimu valor asignáu a *x* (como númberu en base 10) ta compuestu poles *d* últimes cifres decimales de 3\uparrow\uparrow*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

## Bibliografía
* 
* ; reprinted (revised 2001) in the following book:
* 
* 
* 

## Enllaces esternos
**N'inglés**:
* "" por Geoff Exoo
* 
* Cómo calcular el númberu de Graham
* Numeropedia - the Special Encyclopedia of Numbers