Что такое число Грэма

Число Грэма — это огромное натуральное число, которое появилось как верхняя граница в задаче Рамсея о раскраске рёбер гиперкуба и долгое время было крупнейшим числом, использованным в математическом доказательстве. Что такое число Грэма, нельзя записать обычными степенями — используют стрелочную нотацию Кнута и строят число через 64 шага рекурсии, где каждый следующий шаг задаёт число стрелок для следующего. Итоговое число обозначают g(64).

$g_{n+1} = 3\uparrow^{g_n}3$

Разбор по случаям

Примеры

Сравнение с гуглом. Гугол — это $10^{100}$, число с сотней нулей, которое ещё можно полностью выписать на бумаге. Число Грэма настолько больше гугола, что даже количество цифр в его записи невозможно ни выписать, ни представить обычными числами.

Уже первый шаг построения — $3\uparrow\uparrow\uparrow\uparrow 3$ — превышает гугол в невообразимое число раз, а всего таких шагов $64$.

Как строится первый шаг g1. Стрелка Кнута означает возведение в степень: $3 \uparrow 3 = 27$.

Двойная стрелка — это башня степеней: $3\uparrow\uparrow 3 = 3^{3^3} = 3^{27}$, что уже больше $7$ триллионов.

Каждая следующая стрелка задаёт ещё один уровень такой рекурсии, а в записи $g_1$ используют четыре стрелки — отсюда и невообразимый размер результата.

Частые ошибки

• Путают число Грэма с гуглплексом, хотя гуглплекс — это $10^{10^{100}}$ и он на порядки меньше первого же шага построения.
• Пытаются представить число Грэма обычной степенью, хотя ни степени, ни башни степеней его не выражают.
• Считают, что раз число известно и названо, его можно полностью записать цифрами — на деле известны лишь последние несколько цифр.

Коротко

Что такое число Грэма, объясняет задача Рамсея о раскраске рёбер гиперкуба: понадобилась оценка настолько огромная, что для неё придумали стрелочную нотацию. Число строят за 64 шага рекурсии; последние его цифры известны точно, а общее их количество представить невозможно.