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

[nnosipov]

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

Поскольку спрашивается только о младших цифрах, то только их и вычисляем, на каждом шаге оставляя 2019 младших цифр и отбрасывая старшие.

Мне кажется, что это принципиально неверно. Лучше бы все это формулами записать, чтобы алгоритм вычисления был ясен. А то вдруг я чего-то недопонял.

Самое интересное в этой задаче --- это доказательство корректности предъявляемого алгоритма вычисления (иначе как проверить ответ-то?).

[wrest]

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

Мне кажется, что это принципиально неверно. Лучше бы все это формулами записать, чтобы алгоритм вычисления был ясен. А то вдруг я чего-то недопонял.

А ну там же вроде ясно:
? a=(2019^(2019))%(10^2019);b=10^(2019);for(i=1,2018,a=(a^2019)%b);print(a)
Означает:
$a_1=2019^{2019} \pmod{10^{2019}}$
$a_{n+1}=a_n^{2019} \pmod{10^{2019}}$
Печатаем $a_{2019}$

[Yadryara]

wrest, у вас ошибка. Именно такая, как описана в статье Тетрация. Проверьте на примере степенной башни из двоек. Ваш способ даёт $4, 16, 256, 65536, ...$, а должно быть $2, 4, 16, 65536, ...$. Степенная башня должна расти гораздо быстрее чем у вас.

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

[wrest]

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

Да, двоечникам я задаю совсем простой вопрос: какая там первая цифра?

А её вообще можно вычислить на современном компьютере за разумное время?

[nnosipov]

wrest
Это шутка была. Разумеется, нет.

[wrest]

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

у вас ошибка. Именно такая, как описана в статье Тетрация
. Проверьте на примере степенной башни из двоек. Ваш способ даёт $4, 16, 256, 65536, ...$, а должно быть $2, 4, 16, 65536, ...$. Степенная башня должна расти гораздо быстрее чем у вас.

А... Ясно.
Тогда я пас, я поднимаюсь снизу вверх а надо спускаться сверху вниз. Помойму это невозможно без черной магии.

[nnosipov]

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

А ну там же вроде ясно:
? a=(2019^(2019))%(10^2019);b=10^(2019);for(i=1,2018,a=(a^2019)%b);print(a)
Означает:
$a_1=2019^{2019} \pmod{10^{2019}}$
$a_{n+1}=a_n^{2019} \pmod{10^{2019}}$
Печатаем $a_{2019}$

Ну, я на всякий случай переспросил. Увы, тут все несколько интересней. Я не зря выше намекал на Эйлеров с Кармайклами.

[wrest]

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

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

Почему же, если числа умножать последовательно то отбрасывать старшие цифры как раз можно и нужно. Но вы указали на мою неправильную тетрацию, и я что-то вообще не понимаю как можно вычислить даже две младшие цифры а не то что 2019.

[nnosipov]

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

Помойму это невозможно без черной магии.

Да не, применяется исключительно белая магия Можно потренироваться на более простом примере: найти последние три цифры $2017^{2017^{2017}}$ (здесь ответ симпатичный).

-- Чт дек 12, 2019 13:32:00 --

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

и я что-то вообще не понимаю как можно вычислить даже две младшие цифры а не то что 2019.

Начните с вычисления одной (последней) цифры, чтобы понять общий принцип.

[wrest]

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

Начните с вычисления одной (последней) цифры, чтобы понять общий принцип.

Поскольку на конце числа 2019 цифра 9, то последняя цифра степени может быть 9 или 1. Выбор небогатый и вроде бы выходит так, что 9 в итоге возводится в нечётную степень, так что последней цифрой будет девятка. Ну и всё, для второй цифры рассуждение не подходит.

[nnosipov]

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

Выбор небогатый и вроде бы выходит так, что 9 в итоге возводится в нечётную степень, так что последней цифрой будет девятка.

А теперь мы это развернуто сформулируем: чтобы вычислить башню из 2019 этажей по модулю $10$, необходимо вычислить такую же башню, но уже из 2018 этажей, по модулю $2$.

А если бы мы хотели знать нашу 2019-этажную башню по модулю $100$, то по какому модулю нам было бы достаточно знать укороченную на один этаж (т.е. 2018-этажную) такую же башню?

[wrest]

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

А если бы мы хотели знать нашу 2019-этажную башню по модулю $100$, то по какому модулю нам было бы достаточно знать укороченную на один этаж (т.е. 2018-этажную) такую же башню?

По модулю 10.

[nnosipov]

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

По модулю 10.

Почему? Нам нужно вычислить $A^B \bmod{100}$. Если я знаю только $r=B \bmod{10}$, могу я по $r$ однозначно определить $A^B \bmod{100}$?

[wrest]

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

Почему?

Потому что период повторения двух последних цифр степеней числа (оканчивающегося на) 19 равен 10.
$19^1 =19 \pmod{100}$
$19^2 =61 \pmod {100}$
$19^3 =59 \pmod{100}$
$19^4=21 \pmod {100}$
$19^5=99 \pmod {100}$
$19^6=81 \pmod {100}$
$19^7=39 \pmod {100}$
$19^8=41 \pmod {100}$
$19^9=79 \pmod {100}$
$19^{10}=01 \pmod {100}$
$19^{11}=19 \pmod {100}$
$19^{10n+k}=19^k \pmod {100}$

[nnosipov]

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

Потому что период повторения двух последних цифр степеней числа (оканчивающегося на) 19 равен 10.

Верно. Здесь немножко повезло. Понятна ли теперь идея вычисления?