A la Ktina (классический арифмост)

[wrest]

nnosipov в сообщении #1429829 писал(а):

Понятна ли теперь идея вычисления?

Нет, не понятна, знаний не хватает. Надо идти и у Виноградова спрашивать.

[nnosipov]

wrest в сообщении #1429833 писал(а):

Надо идти и у Виноградова спрашивать.

Про теорему Эйлера там прочитайте. С ее помощью можно получить простейшую версию алгоритма. Потом, как сам алгоритм станет ясен, обсудим как его оптимизировать.

[Yadryara]

nnosipov в сообщении #1429829 писал(а):

Здесь немножко повезло.

Штука в том, что так будет везти и дальше. Например, $7$ последних цифр башни из чисел равных $2019$ для любого количества этажей, начиная с $7$ — $1001179$. Совпадает с Вашим ответом?

[nnosipov]

Yadryara в сообщении #1432180 писал(а):

Штука в том, что так будет везти и дальше.

Выигрыш есть, но он очень скромный.

Yadryara в сообщении #1432180 писал(а):

Совпадает с Вашим ответом?

Совпадает. А таки все 2019 цифр поместить здесь? В память, так сказать, уходящего года.

[Yadryara]

До конца года лично я пас. $19$ цифр: $3935880226871001179$

[nnosipov]

Yadryara в сообщении #1432306 писал(а):

До конца года лично я пас. $19$ цифр: $3935880226871001179$

У меня 19-я цифра равна $1$. Окей, выложим под НГ хвостик этого 10-адического монстра. Как бы его посимпатичней нарисовать (как в TeX красиво изобразить степенную башню с бесконечным числом этажей)?

[Yadryara]

nnosipov в сообщении #1432368 писал(а):

У меня 19-я цифра равна $1$.

У Вас правильно. Это я уже утомился просто. Кстати, в Альфе это можно проверить непосредственно, а PARI перестаёт справляться уже с гораздо меньшими числами.

[nnosipov]

Yadryara в сообщении #1429816 писал(а):

И это не говоря уже о том, что конечно же nnosipov прав, что нельзя вот так просто отбросить огромное количество старших цифр, как это сделали вы!

А вот и можно

Вообще, с вычислением последних цифр этой тетрации я, мягко выражаясь, попал впросак. Дело в том, что каждый год я предлагаю своим студентам задачу типа той, что обсуждалась выше: найти последние $2019$ цифр степенной башни из $2019$ этажей, каждый из которых равен числу $2019$. Некоторые неленивые студенты приносят решение этой задачи, но из-за собственной лени я его не смотрю, а просто проверяю ответ. (В качестве оправдания скажу, что идея решения таких задач очень подробно описана в моей методичке, и я наивно полагал, что добросовестный студент просто запрограммирует соответствующий не слишком сложный алгоритм. Чего тут, собственно, проверять?) Ответ обычно сходится. Все довольны, все хорошо. Но на днях я решил-таки проверить корректность одного такого решения с правильным ответом. Решение сводилось к вычислению следующей рекуррентной последовательности:

$$A_1=2019, \quad A_{j+1}=2019^{A_j} \bmod{10^{2019}} \quad (j=1,2,\dots).$$

Ответом было $A_{2019}$. Вот так просто, да (а чего там мудрить, пришпандорим к рекуррентной формуле нужный модуль, и все дела!). Само вычисление на компьютере занимало часы (в отличие от минут при правильном подходе), но это неважно. Самое забавное в том, что ответ правильный! Разумеется, никаких обоснований корректности ответа не было (кроме дежурных слов про теорему Эйлера). По-хорошему, такое решение не стоило бы засчитывать до тех пор, пока не будет предъявлено полное обоснование того, что число $A_{2019}$, вычисленное по столь простому рекуррентному правилу, действительно дает то, что требуется найти.

Конечно, все дело в том, что модуль, равный степени десятки, специфичен. В следующем году студентов ждет сюрприз --- степенную башню нужно будет вычислять по случайному модулю (не слишком многозначному, правда). Вот здесь соответствующая последовательность, вычисленная по простому рецепту выше, уже будет давать чушь, а не правильный ответ, почти всегда.

Upd. На самом деле вычисление $A_{2019}$ занимает десятки минут, а не часы (Maple, i3).