En matematiko, nombro de Graham, nomita pro Ronald Graham, estas granda nombro kiu estas supera baro por solvaĵo de certa problemo en teorio de Ramsey.

Ĉi tiu nombro ekhavis iun popularan atenton kiam Martin Gardner priskribis ĝin en sekcio "Matematikaj ludoj" de Scienca Ameriko en novembro de 1977, skribante ke "En nepublikigita pruvo, Graham ĵus fondis ... baron tiel vastan ke ĝi tenas la rikordon por la plej granda nombro iam uzata en serioza matematika pruvo." La libro de mondaj rikordoj de Guiness de 1980 ripetis la pretendon de Gardner, aldoninte la popularan intereson al ĉi tiu nombro.

Nombro de Graham estas multe pli granda ol aliaj konataj grandaj nombroj tiaj kiel guglo kaj gugloplekso, kaj eĉ pli granda ol nombro de Skewes kaj nombro de Moser, aliaj konataj pli grandaj nombregoj. Ne ebla, en la limigoj de nia universo, signifi la nombron de Graham, aŭ iun moderan proksimumado de ĝi, en kutima cifereca sistemo Eĉ potencaj turoj de formo ${\displaystyle a^{b^{c^{\cdot ^{\cdot ^{\cdot }}}}}}$ netaŭgas por ĉi tiu celo, kvankam ĝi povas esti facile priskribita per rikura formulo uzanta notacion de Knuth aŭ iun ekvivalentan, kiel estis farite de Graham.

Specifaj entjeroj malproksime pli grandaj ol nombro de Graham poste aperis en multaj seriozaj matematikaj pruvoj, ekzemple, kun diversaj finiaj formoj de Friedman de teoremo de Kruskal.

Problemo de Graham

La nombro de Graham aperis el la sekva problemo en branĉo de matematiko sciata kiel teorio de Ramsey:

Konsideru n-dimensian hiperkubon, kaj trakonektu ĉiun paron de ĝiaj verticoj por ricevi plenan grafeon sur 2ⁿ verticoj. Tiam kolorigu ĉiun lateron de ĉi tiu grafeo ruĝe aŭ nigre. Kio estas la plej malgranda valoro de n por kiu ĉiu ebla ĉi tia kolorigo nepre enhavas samkoloran plenan subgrafeon de 4 verticoj kiu kuŝas en unu 2-dimensia ebeno en la fonta hiperkubo?

Graham kaj Rothschild en 1971 pruvis ke ĉi tiu problemo havas solvaĵon N* kaj donis kiel la baroj pritakson 6 ≤ N* ≤ N, kie N estas certa eksplicite difinita tre granda nombro. Tamen, Graham en nepublikigita laboro reviziis ĉi tiun superan baron al esti multe pli granda nombro. La reviziita supera baro de Graham estis poste publikigita kaj ĝuste ĝi estas la nombro de Graham.

La suba baro de la problemo estis poste plibonigita de Exoo en 2003, kiu montris ke la solvaĵo al estas minimume 11, kaj provizis eksperimentan indikaĵon sugestantan ke ĝi estas minimume 12. Tial, la plej bonaj sciataj baroj por la solvaĵo N* estas 11 ≤ N* ≤ G, kie G estas nombro de Graham.

Difino de nombro de Graham

Per notacio de Knuth, nombro de Graham G (kiel estas difinita en artikolo de Gardner en Scienca Ameriko) estas

${\displaystyle \left.{\begin{matrix}&3\underbrace {\uparrow \dots \dots \dots \dots \uparrow } 3\\&3\underbrace {\uparrow \dots \dots \dots \uparrow } 3\\G\equiv &\underbrace {\qquad \vdots \qquad } \\&3\underbrace {\uparrow \dots \uparrow } 3\\&3\uparrow \uparrow \uparrow \uparrow 3\end{matrix}}\right\}{\text{64 tavoloj}}}$

kie kvanto de la sagoj en ĉiu tavolo krom la plej suba estas valoro de la sekva pli suba tavolo.

Aŭ ekvivalente

G = g₆₄

kie ${\displaystyle g_{1}=3\uparrow \uparrow \uparrow \uparrow 3}$ kaj

${\displaystyle g_{n}=3\uparrow ^{g_{n-1}}3}$ por n>1

aŭ

G = f⁶⁴(4)

kie ${\displaystyle f(n)=3\uparrow ^{n}3}$

kie supra indico sur supren-sago indikas la kvanton de sagoj kaj supra indico sur f indikas ripeton de apliko de funkcio. La funkcio f estas speciala okazo de la hiperoperatora familio de funkcioj, f(n) = hyper(3, n+2, 3), kaj povas ankaŭ esti esprimita per ĉena indikila skribmaniero de Conway kiel ${\displaystyle f(n)=3\rightarrow 3\rightarrow n}$. La lasta skribmaniero ankaŭ provizas jenajn barojn por G:

${\displaystyle 3\rightarrow 3\rightarrow 64\rightarrow 2<G<3\rightarrow 3\rightarrow 65\rightarrow 2}$

Dekumaj ciferoj de nombro de Graham

La nombro de Graham estas potenca turo de formo ${\displaystyle 3\uparrow \uparrow n}$ kun tre granda valoro de n, tiel ĝiaj la lastaj (dekstraj aŭ la plej malgrande signifaj) dekumaj ciferoj devas kontentigi certajn propraĵojn komunajn al ĉiuj ĉi tiaj turoj. Unu el ĉi tiuj propraĵoj estas ke ĉiuj ĉi tiaj turoj de alto pli granda ol donita valoro d havas la saman vicon de d plej dekstraj dekumaj ciferoj. Ĉi tio estas speciala okazo de pli ĝenerala propraĵo: La d plej dekstraj dekumaj ciferoj de ĉiuj ĉi tiaj turoj de alto pli granda ol d+2, estas sendependa de la plej supra 3 en la turo; kio estas, la plej supra 3 povas esti ŝanĝita al ĉiu la alia nenegativa entjero sen afekto de la d plej dekstraj ciferoj.

Jena tabelo ilustras, por kelkaj valoroj de d, kiel ĉi tio okazas. Por donita alto de turo kaj nombro de ciferoj d, la plena limigo de d-ciferaj nombroj (10^d de ilin) faras ne okazi; anstataŭe, certa pli malgranda subaro de valoroj ripetas sin en ciklo. La longo de la ciklo kaj iu el la valoroj (en krampoj) estas montritaj por ĉiu okazo:

Kvanto de ciferoj d	${\displaystyle 3\uparrow x}$	${\displaystyle 3\uparrow 3\uparrow x}$	${\displaystyle 3\uparrow 3\uparrow 3\uparrow x}$	${\displaystyle 3\uparrow 3\uparrow 3\uparrow 3\uparrow x}$	${\displaystyle 3\uparrow 3\uparrow 3\uparrow 3\uparrow 3\uparrow x}$
1	4 (1, 3, 9, 7)	2 (3, 7)	1 (7)
2	20 (01, 03, ..., 87, ..., 67)	4 (03, 27, 83, 87)	2 (27, 87)	1 (87)
3	100 (001, 003, ..., 387, ..., 667)	20 (003, 027, ...387, ..., 587)	4 (027, 987, 227, 387)	2 (987, 387)	1 (387)

Ekzemple, por d=1 konsiderante ke ${\displaystyle 3\uparrow x=3^{x}}$, estas:

3⁰=1

3¹=3

3²=9

3³=27

3⁴=81

3⁵=243

3⁶=729

3⁷=2187

...

kaj la lasta unu cifero estas 1, 3, 9, 7, kaj denove 1, 3, 9, 7, kaj tiel plu kiel estas skribite en la tabelo.

Por ${\displaystyle 3\uparrow 3\uparrow x=3^{(3^{x})}}$ estas:

${\displaystyle 3\uparrow 3\uparrow 0=3^{1}=3}$

${\displaystyle 3\uparrow 3\uparrow 1=3^{3}=27}$

${\displaystyle 3\uparrow 3\uparrow 2=3^{9}=19683}$

${\displaystyle 3\uparrow 3\uparrow 3=3^{27}=7625597484987}$

...

kaj la lasta unu cifero estas 3, 7, kaj denove 3, 7, kaj tiel plu kiel estas skribite en la tabelo.

La apartaj plej dekstraj d ciferoj kiuj estas definitive komunigitaj per ĉiuj sufiĉe altaj turoj de 3 estas montritaj per grasa tiparo pli supre, kaj videblas kiel ili ellaboriĝas kiam la turo plialtiĝas. Por ĉiu fiksita kvanto de ciferoj d (linio en la tabelo), la kvanto de valoroj eblaj por ${\displaystyle (3\uparrow 3\uparrow ...3\uparrow ''x'')mod10^{d}}$, kie x estas nenegativa entjero, estas malgrandiĝanta kiam la alto pligrandiĝas, ĝis la sola nombro kiam la alto superas d+2.

Simpla algoritmo ^[1] por komputado de ĉi tiuj ciferoj povas esti sekva: estu komence x = 3, tiam ripetu d fojojn, la asignon x := 3^x mod 10^d. La fina valoro asignita al x estas tiam la d plej dekstraj dekumaj ciferoj de ${\displaystyle 3\uparrow \uparrow n}$ por ĉiu n>d. Se la fina valoro de x havas malpli ol d dekumajn ciferojn necesas aldoni la kondukajn 0.

Ĉi tiu algoritmo produktas jenajn 100 plej dekstraj dekumaj ciferoj de nombro de Graham (aŭ ĉiu turo de pli ol 100 nombroj 3):

94042482650181938515625357963996189939679054966380 03222348723967018485186439059104575627262464195387

Referencoj

Vidu ankaŭ

• Teorio de Ramsey
• Notacio de Knuth
• Hiperoperatoro
• Ĉena indikila skribmaniero de Conway
• Granda nombro
• Guglo
• Gugloplekso
• Nombro de Skewes
• Nombro de Moser
• Teoremo de Kruskal
• Finia formo de Friedman

Eksteraj ligiloj

• Kiel kalkuli nombron de Graham
• Problemo de Ramsey sur hiperkuboj de Geoff Exoo
• Nombro de Graham je Mathworld
• Speciala enciklopedio de nombroj