fixfix
2014 dxdy logo

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

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




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


20/12/10
9179
Действительно, чего это я ... ОК, берем актуальную версию.

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


11/12/05
10252
А можно следующий год? За 3 секунды.
А то в мою лично голову уже ни Элер, ни Кармайкл не помещаются, даже если поделить один на другого.

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


20/12/10
9179
Dan B-Yallay в сообщении #1429590 писал(а):
А можно следующий год? За 3 секунды.
Только если в уме :-)

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

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


05/09/16
12259
nnosipov в сообщении #1429585 писал(а):
Следующий номер в нашей программе: найти последние $2017$ цифр степенной башни из $2017$ этажей, каждый этаж равен числу $2017$. Время решения: 3 минуты (мой компьютер быстрее не умеет).
Быстрый у вас компьютер... у меня планшет за три минуты всходит на 111 этажей только.

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


20/12/10
9179
wrest в сообщении #1429595 писал(а):
Быстрый у вас компьютер... у меня планшет за три минуты всходит на 111 этажей только.
Боюсь, дело в алгоритме, ибо компьютер у меня слабенький. Впрочем, я слегка приврал насчет времени: на самом деле 5 минут (Maple, i3).

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


05/09/16
12259
nnosipov в сообщении #1429621 писал(а):
Боюсь, дело в алгоритме,

Наверное, но тут, кажется, особо не ускоришься.
nnosipov в сообщении #1429621 писал(а):
Впрочем, я слегка приврал насчет времени: на самом деле 5 минут (Maple, i3).
А, ну это совсем другое дело. У меня компьютер в среднем в 10 раз быстрее планшета, тогда норм.

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


24/03/19
147
nnosipov в сообщении #1429561 писал(а):
$1997^{1997}$

Решение через Эйлера (не у всех в голове Кармайкл): $\varphi(1000)=\varphi(2^3)\cdot \varphi(5^3)=(8-4)\cdot (125-25)=400,$ так что $1997^{400}\equiv 1 \pmod{1000}.$ Значит, дальше: $1997^{1997} \equiv (-3)^{-3} \equiv (-27)^{-1} \equiv (973)^{-1} \pmod{1000}.$ Последнюю величину можно найти с помощью алгоритма Евклида: $973^{-1} \equiv 37 \pmod{1000}.$

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


08/12/17
384

(Оффтоп)


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


20/12/10
9179
SiberianSemion в сообщении #1429672 писал(а):
Последнюю величину можно найти с помощью алгоритма Евклида: $973^{-1} \equiv 37 \pmod{1000}.$
А как это проделать в уме?

Я имел в виду следующую выкладку: $$1997^{1997}=(-3)^{5\cdot 400 -3}=(-3)^{-3}=333^3=(333 \cdot 3)^2 \cdot 37=37 \bmod{1000}.$$

-- Чт дек 12, 2019 00:53:23 --

wrest в сообщении #1429622 писал(а):
У меня компьютер в среднем в 10 раз быстрее планшета, тогда норм.
Если нетрудно, напишите, за сколько Ваш компьютер (видимо >=i7) справился с задачей. Наверное, Вы использовали Pari, здесь должно быть пошустрее, чем в Maple. Просто любопытно.

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


20/12/10
9179
alesha_popovich в сообщении #1429701 писал(а):

(Оффтоп)

(Оффтоп)


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


05/09/16
12259
nnosipov в сообщении #1429752 писал(а):
Если нетрудно, напишите, за сколько Ваш компьютер (видимо >=i7) справился с задачей.

Запускал на mac mini 2011 года (ноутбучный процессор Intel Core i7-2635QM 2.0GHz quad core)
Считал последние 2019 цифр башни в 2019 этажей.
Прямо в лоб, без выкрутас:

nnosipov в сообщении #1429752 писал(а):
Если нетрудно, напишите, за сколько Ваш компьютер (видимо >=i7) справился с задачей.

Запускал на mac mini 2011 года (ноутбучный процессор Intel Core i7-2635QM 2.0GHz quad core)
Считал последние 2019 цифр башни в 2019 этажей.
Прямо в лоб, без выкрутас:
? a=(2019^(2019))%(10^2019);b=10^(2019);for(i=1,2017,a=(a^2019)%b);print(a)

(Далее 2019 цифр, может раздуть окно далеко вправо, кликать с осторожностью :))


time = 17min, 33,024 ms.
?

К рабочему компу, который поновее и побыстрее, доступа больше нет :( :)

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


20/12/10
9179
wrest
Что-то у меня другой ответ.

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


05/09/16
12259
nnosipov в сообщении #1429786 писал(а):
Что-то у меня другой ответ.

А, ну да. Цикл надо до 2018.

(Вот:)


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


20/12/10
9179
wrest в сообщении #1429797 писал(а):
А, ну да. Цикл надо до 2018.
Нет, не в этом дело. У Вас вычисляется принципиально не то, что нужно. Поэтому и ответы не совпадают.

Степенная башня $x_n$ определяется так: $x_1=a$, $x_n=a^{x_{n-1}}$ ($n=2,3,\dots$). Таким образом, $x_n$ --- это степенная башня из $n$ этажей, каждый из которых (включая и само основание башни) равен числу $a$. Например, при $a=3$ и $n=3$ получим $3^{3^3}$ --- башня из трех этажей. Нас интересует случай, когда $a=2019$ и $n=2019$. Нужно найти $x_n \bmod{10^{2019}}$.

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


05/09/16
12259
nnosipov
Что именно надо вычислить, я понял верно.
Само собой, "прямо" это сделать нельзя.
Поскольку спрашивается только о младших цифрах, то только их и вычисляем, на каждом шаге оставляя 2019 младших цифр и отбрасывая старшие. У меня были сомнения сколько младших цифр оставлять. Сперва я подумал, что надо оставлять на одну больше (2020), но потом решил что и 2019 хватит.

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

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



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

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


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

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