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
8858
Действительно, чего это я ... ОК, берем актуальную версию.

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


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

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


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

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

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


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

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


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

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


05/09/16
11461
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
259

(Оффтоп)

nnosipov в сообщении #1429546 писал(а):
A la Ktina

Ktina жил, Ktina жив, Ktina будет жить! :mrgreen:

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


20/12/10
8858
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
8858
alesha_popovich в сообщении #1429701 писал(а):

(Оффтоп)

nnosipov в сообщении #1429546 писал(а):
A la Ktina

Ktina жил, Ktina жив, Ktina будет жить! :mrgreen:

(Оффтоп)

Когда-то очень давно Ktina обращал внимание общественности на действительно интересные сюжеты. Например, вот здесь topic37895.html A la Ktina --- это всего лишь ностальгия по тем приятным временам.

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


05/09/16
11461
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 цифр, может раздуть окно далеко вправо, кликать с осторожностью :))

956969919283142561389148317301116633477904635350742925688194179814805103614602607228813572116286194894050365951633375325449912213382811761190934895654781689172919712816979355794199970611432242931591485280662020337820252247608372854171807762201929657849049669441888831989810729335046133320730086428765660557102457824431745503734131655200194515401733383341114415769265542322314402055128564234291477103255218577452383221375732840901048884013520583646772623461644018429723240034177600036440607598925134177589165626270884118181903126467944023341230547106527444426607292334389195039004345436394333994394133459295243441307308441431647456278879444645148816803695498132259629275232896999739310683905603611213835559800439226943490656760909388753154187279675031669683511036750660021437272877703278829486340256540299706494483534626253018700708684306400788343861107188069119569550392884393153273555342682070322801289150656485288234582815369873216406761595563185347955807292517774138242259489049474537125381194009102104056962990704247718644111462684396630776619786554120549522966282617416474799016528351939867287132626710504685745575361262071888104857100208685878458240120940203527689311244673143774676645727211682290112048965082365751873207073023232034810850262735473401926463721518005562604520306702793005791242501572625655729469851060733189362419248791281723613765697061526899894734189527191913327912976594171881322596469016230435938067806170866832860723649282102389280852420796484963289159320709047780627168804708980596408922354804536866286585911043204588245553939170418856059185348809537428122923711775900024886733279869752939542793627468671519472783330821159864634166659808356033479264613099587071270946202536791423464640878256184154283408602892977557445507081098029656640984496771123196378086187922435228554444856871983810904903346882263490626423238122384253856304761791524607291232144769415526711698323306138321752780383112453384370827006562458108034676288920245375927610384790246039311880116897780933241212136005505158810819

time = 17min, 33,024 ms.
?

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

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


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

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


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

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

(Вот:)

74631697793884832635217483732887730757926087668761318944111581266608420652880714778391896396745165
99925469667439005520345446331724070539002718847172096131480332197857613231500171210243532998596670888859465
41674667495564102098015280010691292125267288633841412333315370812854463944365285232465104778319896698976420
46016112778331784016417184337144696564815629986274398923779099470742645036481573378601778424740617602762251
80997324126913393115984504018696763755558398688344525004006282206309278099736842505469803723781903505423999
79490343806993352725699049960439592253572998564678647228715584738358937347599877892857685780114503069268072
91757430106776324918680045536976536897778223801294763448637649474250847853635064835662841958769888726006723
88554861346016802397840322270489718713610132192857465613444440456780626264630499698624189150317847791210846
53092991927250935546390787806586157289511523227890810207603224366204955752414773823553586263304589330424887
78390861309358849993411314098220897846895082447370589655654868752127029850000641843215703155220610568270607
28213481114242646827956023668134891117889107295508649131326136348080247851533299622826459177557817823516853
47012848348820196557210981362590607854837538918354162253980219980339763643164479581661583246470688199431943
89950571908363460808013510502085590568920310341519539830941658330484364427559829057798121949441198165090129
13032324878071667510474211559965723082696754710231851784317345909652895714823736830666490177629303490368838
20532409564259099537075394063014244781956168204361688969309414297625495289014128710354153922571822171558002
76858626412254160855345452051595648550427136105272463735658330504620784899952472193572327868385509775865055
31555778716404039674640195495582151479670258749988989889117162355579850820799300060217982081867548675502214
66154465903563191232313034543984478927025929898037599892145586880070421627635816042571203365107475386461633
17495245743921834363031697227194832699477875603081104530151954389828164504863370712361416038848297179

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


20/12/10
8858
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
11461
nnosipov
Что именно надо вычислить, я понял верно.
Само собой, "прямо" это сделать нельзя.
Поскольку спрашивается только о младших цифрах, то только их и вычисляем, на каждом шаге оставляя 2019 младших цифр и отбрасывая старшие. У меня были сомнения сколько младших цифр оставлять. Сперва я подумал, что надо оставлять на одну больше (2020), но потом решил что и 2019 хватит.

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

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



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

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


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

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