2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4  След.
 
 Re: A la Ktina (классический арифмост)
Сообщение12.12.2019, 08:01 
Заслуженный участник


20/12/10
8394
wrest в сообщении #1429810 писал(а):
Поскольку спрашивается только о младших цифрах, то только их и вычисляем, на каждом шаге оставляя 2019 младших цифр и отбрасывая старшие.
Мне кажется, что это принципиально неверно. Лучше бы все это формулами записать, чтобы алгоритм вычисления был ясен. А то вдруг я чего-то недопонял.

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

 Профиль  
                  
 
 Re: A la Ktina (классический арифмост)
Сообщение12.12.2019, 09:01 


05/09/16
9552
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}$

 Профиль  
                  
 
 Re: A la Ktina (классический арифмост)
Сообщение12.12.2019, 09:02 
Аватара пользователя


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

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

 Профиль  
                  
 
 Re: A la Ktina (классический арифмост)
Сообщение12.12.2019, 09:13 


05/09/16
9552
nnosipov в сообщении #1429591 писал(а):
Да, двоечникам я задаю совсем простой вопрос: какая там первая цифра?

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

 Профиль  
                  
 
 Re: A la Ktina (классический арифмост)
Сообщение12.12.2019, 09:15 
Заслуженный участник


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

 Профиль  
                  
 
 Re: A la Ktina (классический арифмост)
Сообщение12.12.2019, 09:17 


05/09/16
9552
Yadryara в сообщении #1429816 писал(а):
у вас ошибка. Именно такая, как описана в статье Тетрация
. Проверьте на примере степенной башни из двоек. Ваш способ даёт $4, 16, 256, 65536, ...$, а должно быть $2, 4, 16, 65536, ...$. Степенная башня должна расти гораздо быстрее чем у вас.

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

 Профиль  
                  
 
 Re: A la Ktina (классический арифмост)
Сообщение12.12.2019, 09:20 
Заслуженный участник


20/12/10
8394
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}$
Ну, я на всякий случай переспросил. Увы, тут все несколько интересней. Я не зря выше намекал на Эйлеров с Кармайклами.

 Профиль  
                  
 
 Re: A la Ktina (классический арифмост)
Сообщение12.12.2019, 09:26 


05/09/16
9552
Yadryara в сообщении #1429816 писал(а):
что нельзя вот так просто отбросить огромное количество старших цифр, как это сделали вы!

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

 Профиль  
                  
 
 Re: A la Ktina (классический арифмост)
Сообщение12.12.2019, 09:27 
Заслуженный участник


20/12/10
8394
wrest в сообщении #1429819 писал(а):
Помойму это невозможно без черной магии.
Да не, применяется исключительно белая магия :-) Можно потренироваться на более простом примере: найти последние три цифры $2017^{2017^{2017}}$ (здесь ответ симпатичный).

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

wrest в сообщении #1429821 писал(а):
и я что-то вообще не понимаю как можно вычислить даже две младшие цифры а не то что 2019.
Начните с вычисления одной (последней) цифры, чтобы понять общий принцип.

 Профиль  
                  
 
 Re: A la Ktina (классический арифмост)
Сообщение12.12.2019, 09:44 


05/09/16
9552
nnosipov в сообщении #1429823 писал(а):
Начните с вычисления одной (последней) цифры, чтобы понять общий принцип.

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

 Профиль  
                  
 
 Re: A la Ktina (классический арифмост)
Сообщение12.12.2019, 09:52 
Заслуженный участник


20/12/10
8394
wrest в сообщении #1429824 писал(а):
Выбор небогатый и вроде бы выходит так, что 9 в итоге возводится в нечётную степень, так что последней цифрой будет девятка.
А теперь мы это развернуто сформулируем: чтобы вычислить башню из 2019 этажей по модулю $10$, необходимо вычислить такую же башню, но уже из 2018 этажей, по модулю $2$.

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

 Профиль  
                  
 
 Re: A la Ktina (классический арифмост)
Сообщение12.12.2019, 10:08 


05/09/16
9552
nnosipov в сообщении #1429825 писал(а):
А если бы мы хотели знать нашу 2019-этажную башню по модулю $100$, то по какому модулю нам было бы достаточно знать укороченную на один этаж (т.е. 2018-этажную) такую же башню?

По модулю 10.

 Профиль  
                  
 
 Re: A la Ktina (классический арифмост)
Сообщение12.12.2019, 10:16 
Заслуженный участник


20/12/10
8394
wrest в сообщении #1429826 писал(а):
По модулю 10.
Почему? Нам нужно вычислить $A^B \bmod{100}$. Если я знаю только $r=B \bmod{10}$, могу я по $r$ однозначно определить $A^B \bmod{100}$?

 Профиль  
                  
 
 Re: A la Ktina (классический арифмост)
Сообщение12.12.2019, 10:26 


05/09/16
9552
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}$

 Профиль  
                  
 
 Re: A la Ktina (классический арифмост)
Сообщение12.12.2019, 10:44 
Заслуженный участник


20/12/10
8394
wrest в сообщении #1429828 писал(а):
Потому что период повторения двух последних цифр степеней числа (оканчивающегося на) 19 равен 10.
Верно. Здесь немножко повезло. Понятна ли теперь идея вычисления?

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 53 ]  На страницу Пред.  1, 2, 3, 4  След.

Модератор: Модераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: Osmiy


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group