Наивный алгоритм, дающий правильный ответ

[nnosipov]

Мне показалось, что вот этот поворот http://dxdy.ru/post1471189.html#p1471189 сюжета про последние цифры степенных башен тянет на более-менее содержательную задачу (во всяком случае, ее решение не кажется совсем уж очевидным). Итак:

Пусть $a>1$ --- целое число, взаимно простое с $10$. Построим степенную башню с основанием $a$, т.е. рассмотрим последовательность $\{A_j\}$, заданную правилом:

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

Докажите, что для заданных натуральных $n$ и $l \geqslant 2$ следующий алгоритм корректно вычисляет последние $l$ десятичных цифр числа $A_n$:

A[1]:=a mod 10^l:
for j from 1 to n-1 do A[j+1]:=a&^A[j] mod 10^l; od:
print(A[n]);

(используется язык Maple; значок $\&$ нужен для того, чтобы не было переполнения).

Комментарий. а) При $l=1$ этот алгоритм может врать. б) В алгоритме можно заменить модуль $10^l$ на произвольный модуль $m$ и, тем самым, пытаться вычислить $r(n,m)=A_n \bmod{m}$. Помимо серии $m=10^l$, есть и другие серии подобного вида, для которых вычисление $r(n,m)$ будет корректным, однако при случайном выборе модуля $m$ ответ будет, скорее всего, неверным.

[StaticZero]

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

используется язык Maple

Лучше, ИМХО, писать псевдокод, не все знают синтаксис Maple.

[iifat]

Не углядел в слепоте своей сакральной мудрости. Чтобы вычислить последние $l$ цифр, мы честно, насколько я могу судить, проводим все вычисления по модулю $10^l$.
Также не понял, зачем заводить целый массив и с чего бы вдруг этот алгоритм не давал $A_n\pmod n$ для любого $n$. И да, языка Maple я также не знаю.

[svv]

iifat
Тут фишка в том, что, согласно алгоритму, показатель степени тоже можно брать по модулю $10^\ell$, что неочевидно.
Очевидно, что если ищется сумма по модулю $m$, можно взять по модулю $m$ слагаемые. Если произведение — множители. Если степень — основание степени. Но не показатель.

$2^4 \operatorname{mod} 3=1$, но $2^{4 \operatorname{mod} 3}=2$

[ИСН]

Ну это потому, что при $l>1$ у нас $10^l$ делится на функцию Кармайкла от себя.

[iifat]

svv в сообщении #1472258 писал(а):

показатель степени тоже можно брать по модулю $10^\ell$

Виноват. Действительно, про модуль степени и не заметил.

[nnosipov]

ИСН в сообщении #1472266 писал(а):

Ну это потому, что при $l>1$ у нас $10^l$ делится на функцию Кармайкла от себя.

А хватит ли одной делимости $m$ на $\lambda(m)$? Мне потребовалась также делимость $m$ на $\lambda(\lambda(m))$ и т.д. Подозреваю, что все эти делимости уже идут бесплатно (вытекают из делимости $m$ на $\lambda(m)$), но как-то не вижу доказательства.

[kotenok gav]

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

Подозреваю, что все эти делимости уже идут бесплатно (вытекают из делимости $m$ на $\lambda(m)$), но как-то не вижу доказательства.

https://ru.wikipedia.org/wiki/%D0%A4%D1 ... 1%82%D1%8C

[nnosipov]

А, так это очевидно. Ну, тогда вопрос снят.

[nnosipov]

Еще один забавный нюанс. Как известно, степенная башня $\{A_j\}$ стабилизируется по любому модулю $m$. Пусть $A$ --- это "стабильное значение" (предел, так сказать, при $n \to \infty$). Тогда сравнение

$$a^A \equiv A \pmod{m}$$

кажется естественным (хотя бы по аналогии с непрерывным случаем), но на самом деле оно верно только в исключительных случаях --- таких, как $m=10^l$, например. Вот конкретный пример:

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

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