2014 dxdy logo

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

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




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


05/09/16
8289
nnosipov в сообщении #1429829 писал(а):
Понятна ли теперь идея вычисления?

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

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


20/12/10
7309
wrest в сообщении #1429833 писал(а):
Надо идти и у Виноградова спрашивать.
Про теорему Эйлера там прочитайте. С ее помощью можно получить простейшую версию алгоритма. Потом, как сам алгоритм станет ясен, обсудим как его оптимизировать.

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


29/04/13
3878
Богородский
nnosipov в сообщении #1429829 писал(а):
Здесь немножко повезло.

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

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


20/12/10
7309
Yadryara в сообщении #1432180 писал(а):
Штука в том, что так будет везти и дальше.
Выигрыш есть, но он очень скромный.
Yadryara в сообщении #1432180 писал(а):
Совпадает с Вашим ответом?
Совпадает. А таки все 2019 цифр поместить здесь? В память, так сказать, уходящего года. :-)

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


29/04/13
3878
Богородский
До конца года лично я пас. $19$ цифр: $3935880226871001179$

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


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

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


29/04/13
3878
Богородский
nnosipov в сообщении #1432368 писал(а):
У меня 19-я цифра равна $1$.

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

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


20/12/10
7309
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).

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

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



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

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


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

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