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
8858
wrest в сообщении #1429810 писал(а):
Поскольку спрашивается только о младших цифрах, то только их и вычисляем, на каждом шаге оставляя 2019 младших цифр и отбрасывая старшие.
Мне кажется, что это принципиально неверно. Лучше бы все это формулами записать, чтобы алгоритм вычисления был ясен. А то вдруг я чего-то недопонял.

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

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


05/09/16
11461
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
7126
Богородский
wrest, у вас ошибка. Именно такая, как описана в статье Тетрация. Проверьте на примере степенной башни из двоек. Ваш способ даёт $4, 16, 256, 65536, ...$, а должно быть $2, 4, 16, 65536, ...$. Степенная башня должна расти гораздо быстрее чем у вас.

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

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


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

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

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


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

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


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

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

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


20/12/10
8858
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
11461
Yadryara в сообщении #1429816 писал(а):
что нельзя вот так просто отбросить огромное количество старших цифр, как это сделали вы!

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

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


20/12/10
8858
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
11461
nnosipov в сообщении #1429823 писал(а):
Начните с вычисления одной (последней) цифры, чтобы понять общий принцип.

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

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


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

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

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


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

По модулю 10.

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


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

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

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



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

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

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