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
9549
nnosipov в сообщении #1429829 писал(а):
Понятна ли теперь идея вычисления?

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

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


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

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


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

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

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


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

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


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

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


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

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


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

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

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


20/12/10
8387
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

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



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

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


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

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