Периодические последовательности Мынки 2.0

Вы, вероятно, ждёте контент, а я, видимо, пинаю хуи. Кому интересно, чем я занимаюсь всё это время, вот полный список: пишу (пытаюсь писать) плагины к Морровинду, играю в Обливион, конкретно — в Дрожащие острова: становлюсь Шигаратом, если вам это о чём-нибудь говорит; откидываю снег от дома, смотрю Аватара Корру, пишу (писал в пятницу и субботу) пробники, решаю что-нибудь, но только если скинут. Проверяю почту, ибо ждать результаты олимпиад это пиздец.

По-хорошему, пока все карантинятся и каникулятся, надо бы писать разборы. Но мне лень. Я тут подумал, что мы с вами давно не обсуждали моё исследование и, несмотря на то что я им настолько же давно не занимался, там вроде бы были какие-то продвижения в последний раз.

Прежде всего расскажу вообще о сути сего, потому что в группе есть те, кто не читал, а те, кто читал, — не помнят, а те, кто помнит, — не поняли.

Я как-то записал небольшую табличку. Она выглядела примерно так:

2 4 8 6 2
3 9 7 1 3
4 6 4 6 4
5 5 5 5 5
6 6 6 6 6
7 9 3 1 7
8 4 2 6 8
9 1 9 1 9

В первом столбце — однозначные числа от 1 до 9. А дальше — последние цифры чисел, получающихся возведением во 2-ю, 3-ю, 4-ю и 5-ю степень чисел из первого столбца. Другими словами — остаток от деления на десять.

Как вы видите, последний столбец целиком копирует первый. А степени разные. Кроме того, последняя цифра произведения зависит только от последних цифр множителей. Я думаю, вы замечали это, например, когда перемножали столбиком. Так вот, это значит, что дальше в первой строке снова будет 48624862, во второй 97139713, в третьей 64646464 и так далее.

Проще говоря, эти последовательности цикличны. Я их в своё время и назвал циклами. Сейчас бы я сказал, что это периодичные последовательности.

Так вот. Если подумать дальше, то можно прийти к выводу, что для двух последних цифр тоже должны существовать циклы. Существует всего 100 вариантов для последних двух цифр — от 00 до 99. Поэтому сто первый элемент последовательности так или иначе совпадёт с каким-нибудь из предыдущих, и начиная с него цикл повторится опять.

Но всё оказалось проще. Первые совпадения, как правило, начинаются не на 101-м элементе, а намного раньше, по-моему, не позже 21-го.

Ну и, в общем-то, уже не вызывает сомнений, что любая последовательность вида
a[n] = k^n mod 10^m, где k и m — постоянные целые величины
является периодической. Длина периода зависит от k и m.

Причём правильнее начинать эту последовательность с n = 0.

Если эта запись непонятна, пишите в комменты. Ну и вот пара примеров:

Можно наслаждаться этим вечно.

Но будем двигаться дальше. Почему-то мне проще всего двигаться дальше на примере 13. Смотрите:

Я выделил маленький участок, но, на самом деле, он есть везде. Третья с конца цифра в первом столбце находится в неизменной последовательности
0 8 6 4 2 0 8 6 4 2

Во втором столбце:
0 4 8 2 6 0 4 8 2 6

В третьем:
1 3 5 7 9 1 3 5 7 9

В четвёртом:
1 7 3 9 5 1 7 3 9 5

В общем-то, для остатков деление на 10 характерно такое свойство:
«+2» = «-8»
«+3» = «-7»
«+a» = «+a-10»

Поэтому первую последовательность мы можем назвать своеобразной прогрессией с разностью d = «+8». Я пишу это в кавычках, потому что

0 + 8 = 8, а
8 + 8 ≠ 6, но

0 «+8» = 8 и
8 «+8» = 16.

Будем считать, мы придумали новую операцию.

Итак. Теперь будем заменять последовательность её разностью, и заметим:

1 столбец: «+8»
2 столбец: «+4»
3 столбец: «+2»
4 столбец: «+6»
5 столбец: «+8»
6 столбец: «+4»

и дальше они повторяются. Удивительно, да? Это уже не так легко объяснить, как то что было в начале, но зато удобно использовать. Чтобы знать, какими тремя цифрами заканчивается, скажем, 13 в 25495 степени, мне достаточно знать, какими тремя цифрами заканчивается 13 в 15-й степени и 13 в 35-й. Но это мне было известно ещё с «Чёрной тетради», там об этом, кстати, довольно много написано.

А вот что я увидел уже после того, как написал программу:

Видите, да?

00 88 76 64 52 40 28 16 04 92 80 68 56 44 32 20 08 96 84 72

Эта последовательность тоже является прогрессией с разностью d = «+88» или, удобнее, «-12».

2 столбец: «+44»/«-56»
3 столбец: «+72»/«-28»
4 столбец: «+36»/«-64»
5 столбец: «+68»/«-32»
…
20 столбец: «+76»/«-24»

Это значит, что мне достаточно знать последние четыре цифры 13 в 1 и в 21, чтобы предсказать последние четыре цифры в 15446589568956589541. Круто, но ещё не то.

1 столбец: «+88»/«-12»
2 столбец: «+44»/«-56»
3 столбец: «+72»/«-28»
4 столбец: «+36»/«-64»
5 столбец: «+68»/«-32»
…
20 столбец: «+76»/«-24»

Как вы можете видеть, 44*2 = 88, 72*2 = 144. Всё усложняется тем, что 44 при «делении» на 2 может дать 22, а может дать 72. Эта проблема решается тем, что все числа, которые я записал выше, делятся на 4. А 22 на 4 не делится. И в любой паре потенциальных делителей будет одно число, кратное 4, и одно не кратное. Если мы встретимся с чем-то подобным для трёх цифр, там должны будут быть только кратные 8, чисто по логике.

Ну и не дай бог выйдет, что это справедливо только для 13. Давайте проверим.

Да, тут я должен уточнить. Для чётных чисел из циклов постоянно выбиваются первые члены. Чаще всего, выбивается ровно столько первых членов, сколько последних цифр вы рассматриваете, но это не всегда так. 0001 ненормальное явление для 14^n, сами посудите, 1 даже не чётное. Вместо 0001 будет 9376, вместо 0014 будет 1264, вместо 0196 будет 7696, вместо 2774 будет 7774, ну а дальше всё совпадает. Можете проверить, 2774«*14» = 7774«*14». Это умножение в кавычках, надеюсь, по понятной причине.

Ну и ещё столбцов только десять, потому что исходное число заканчивается на 4, это всегда уменьшает количество столбцов в 2 раза. Если число заканчивается на 6, то в 4.

Так вот. А теперь выписываем в первом столбце последовательность. вместо 00 пишем 76.

76 49 05 61 17 73 29 85…

Числа корявые, но можно заметить, что все они отличаются на «+56» или «-44». И это здорово. Мне лень писать дальше ковычки, представьте, что они есть:

1 столбец: +56/-44
2 столбец: +84/-16
3 столбец: +76/-24
4 столбец: +64/-36
5 столбец: +96/-4
6 столбец: +44/-56
7 столбец: +16/-84
8 столбец: +24/-76
9 столбец: +36/-64
10 столбец: +4/-96

Чего-то не видно, чтобы 4*2 = 36, странно, да? Тут вроде бы надо умножать на 9. Не очень приятно. Зато видно совершенно другую закономерность. Заметьте, все числа, заканчивающиеся на 6 изменяются на +20, а все числа, заканчивающиеся на 4 изменяются на -20. Прикольно. А, главное, нихуя не видно связи с умножением на 9.

Ну да ладно. По такому случаю предлагаю вернуться к таким же хуйням у 13.

+88/-12
+44/-56
+72/-28
+36/-64
+68/-32
+84/-16
+92/-8
+96/-4
+48/-52
+24/-76
+12/-88
+56/-44
+28/-72
+64/-36
+32/-68
+16/-84
+8/-92
+4/-96
+52/-48
+76/-24

Я устал это писать.

Ну делаем выводы. Для всех чисел, заканчивающихся на 8 — +80. На 4 — +40. На 2 — +20. На 6 — +60. Возможно, это свойство приятнее, чем деление на 2.

Если вы думаете, что я знаю, что пишу, то вы очень ошибаетесь, я тут сижу охуеваю.

Так или иначе, это позволяет нам предсказывать намного больше, чем мы могли раньше.

Теперь к более абстрактным вещам.

Поработаем с этой табличкой. С последней цифрой всё ясно. Предпоследняя образует прогрессию с разностями «+6» «+8» «+4» и «+2» для соответствующих столбцов.

Выписываем первые две цифры в первом столбце

00 56 72 48 84 80 36 52 28 64

Абсолютно бессвязный набор чисел, вроде. А теперь выпишем разности между элементами.

56-00 = 56
72-56 = 16
48-72 = 76 [76+72 = 148]
84-48 = 36
80-84 = 96
36-80 = 56
52-36 = 16
…

Сверхзамечательно.
56 16 76 36 96 это уже красивая неплохая последовательность. С разностью «+60»

Во втором столбике тем же образом можно получить
28 08 88 68 48 с разностью «+80»

В третьем
64 04 44 84 24 с разностью «+40»

В четвёртом
32 52 72 92 12 с разностью «+20»

56 16 76 36 96
28 08 88 68 48
64 04 44 84 24
32 52 72 92 12

Снова 32*2 = 64 и так далее. Красиво. Я что думаю, эта хуйня ломает мне мозг.

Но что мы имеем.

Числа, образованные последней цифрой в столбцах равны.
Числа, образованные последними двумя цифрами в столбцах образуют «прогрессию»
Числа, образованные последними тремя цифрами в столбцах образуют «прогрессию» второго порядка

По-моему, логично проверить числа, образованные четырьмя цифрами на «прогрессию» третьего порядка. Но проверять в статье мне неохота, можете просто поверить на слово, эта «прогрессия» действительно есть. Дальше я не проверял, но должно быть тоже. И там дохуилиард всяких жутких страшных совпадений, которые мне лень описывать, потому что от них взрывается голова.

Пожалуй, последнее, что я хочу рассказать, это вот что.

Мы с вами только что смотрели таблицу, в которой в строках совпадает только одна цифра. Давайте посмотрим таблицу, в которой совпадают две цифры. Или не посмотрим. Мне лень, но надо.

Мы, вроде бы, уже разобрались, что последние четыре цифры образуют «прогрессию» первого порядка. Вау. Да тут ведь всё, что было в таблице выше, умножается на два. Давайте проверим.

Элементы начальной последовательности: 0000 4388 3176 6364 3952
Их разности: 4388 8788 3188 7588 [это не код карточки, если что]
Разности разностей: 4400 4400 4400

Ура. Ну всё. Сеанс окончен, всем спасибо.

Вы, наверное, будете ругаться и отписываться, но я почти ничего из этого не могу объяснить, доказать или хотя бы понять. Предположительно, мне надо идти к сенсеям теории чисел, занимающихся изучением остатков. Но я клал на них хуй :)