A la Ktina (классический арифмост)

[nnosipov]

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

[Dan B-Yallay]

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

[nnosipov]

Dan B-Yallay в сообщении #1429590 писал(а):

А можно следующий год? За 3 секунды.

Только если в уме

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

[wrest]

nnosipov в сообщении #1429585 писал(а):

Следующий номер в нашей программе: найти последние $2017$ цифр степенной башни из $2017$ этажей, каждый этаж равен числу $2017$. Время решения: 3 минуты (мой компьютер быстрее не умеет).

Быстрый у вас компьютер... у меня планшет за три минуты всходит на 111 этажей только.

[nnosipov]

wrest в сообщении #1429595 писал(а):

Быстрый у вас компьютер... у меня планшет за три минуты всходит на 111 этажей только.

Боюсь, дело в алгоритме, ибо компьютер у меня слабенький. Впрочем, я слегка приврал насчет времени: на самом деле 5 минут (Maple, i3).

[wrest]

nnosipov в сообщении #1429621 писал(а):

Боюсь, дело в алгоритме,

Наверное, но тут, кажется, особо не ускоришься.

nnosipov в сообщении #1429621 писал(а):

Впрочем, я слегка приврал насчет времени: на самом деле 5 минут (Maple, i3).

А, ну это совсем другое дело. У меня компьютер в среднем в 10 раз быстрее планшета, тогда норм.

[SiberianSemion]

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}.$

[alesha_popovich]

(Оффтоп)

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

A la Ktina

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

[nnosipov]

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. Просто любопытно.

[nnosipov]

alesha_popovich в сообщении #1429701 писал(а):

(Оффтоп)

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

A la Ktina

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

(Оффтоп)

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

[wrest]

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.
?
К рабочему компу, который поновее и побыстрее, доступа больше нет :( :)

[nnosipov]

wrest
Что-то у меня другой ответ.

[wrest]

nnosipov в сообщении #1429786 писал(а):

Что-то у меня другой ответ.

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

(Вот:)

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

[nnosipov]

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}}$.

[wrest]

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