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


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,

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 g1 con cuatro fleches ente los treses; el segundu pasu consiste en calcular g2 con g1 fleches ente los treses, el tercer pasu consiste en calcular g3 con g2 fleches ente los treses, y asina socesivamente hasta calcular finalmente G = g64, que tien g63 fleches ente los treses.

Equivalentemente, 

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(), , y tamién puede espresase por aciu la notación de fleches encadenaes de Conway como . Esta última notación establez les siguientes cotes pa G:


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

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

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

Por tanto,

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

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

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

 Últimes cifres del númberu de Graham 

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

+ Númberu de valores posibles de 33...3x cuando s'ignoren toles cifres menos les d últimes Númberu de cifres (d)  3x  33x  333x  3333x  33333x 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)

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 33...3x mod 10d, 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 simpleThe Math Forum @ Drexel ("Last Eight Digits of Z") pa calcular estes últimes cifres d'esta manera: sía x = 3, depués itérese d vegaes l'asignación x = 3x mod 10d. L'últimu valor asignáu a x (como númberu en base 10) ta compuestu poles d últimes cifres decimales de 3n, 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

Categoría:Grandes númberos