Пентадекатлон мечты

[Huz]

mathematician123 в сообщении #1558051 писал(а):

Доказано, что $M(84) \le 21$:

Huz в сообщении #1557713 писал(а):

For $M(84) \ge 22$, we are constrained to have:
- no value 24 (mod 32) or 16 (mod 32)
- no value 30 (mod 36)
- no value 40 (mod 48)
- no value 42 (mod 72) or 66 (mod 72)

I believe that covers all possibilities, so $M(84) \le 21$.

Если всё верно, то те же рассуждения доказывают, что $M(k) \le 21$, если $k \equiv 4 \pmod{8}$ и $k$ не делится на 5.В частности, $M(108) \le 21$.

Here's a breakdown to help with verification, using $n$ to represent the smallest number in the chain.

No value 24 (mod 32) or 16 (mod 32) means we need $n \in \{25, 26\} \pmod{32}$
$= \{25,26,57,58,89,90\} \pmod{96}$.
No value 40 (mod 48) disallows 25,26, so $n \in \{57,58,89,90\} \pmod{96}$
$= \{57,58,89,90,153,154,185,186,249,250,281,282\} \pmod{288}$
$= \{9,10,17,18,33,34,41,42,57,58,65,66\} \pmod{72}$.
No value 30 (mod 36) disallows 9..30, 45..66 leaving $n \in \{33,34,41,42\} \pmod{72}$.
No value 42 (mod 72) disallows the rest (and we don't need 66 (mod 72), it's just a special case of 30 (mod 36)).

I haven't analysed the reasoning yet, but my code thinks it may also be possible to prove $M(84) < 21$, using $n \equiv -5 \pmod{192}, n + 13 = 8y^2$.

(Later) I messed that up, $M(84)=21$ still looks possible.

[VAL]

Пока всякие online TeX'и капризничают, комп считает.
$M1326)=5$

(Оффтоп)

14345008345180812212073431974782879009233075152309784811976850982908981855614679757416360449361259635269243734493638458645948702572223287747018442122256825246897613337416591882558556520826224387337635415955824140306091674718654898068998222332408706961521722627520307163301475161036341184433584304962158203121

Два вопроса по таблице.
1. Может, вместо ссылок привести сами стартовые числа цепочек?
2. Как обозвать (в заголовке столбца) тех, кто нашел цепочку? Авторы? Вряд ли. Первооткрыватели? ...?

[Dmitriy40]

VAL в сообщении #1558109 писал(а):

1. Может, вместо ссылок привести сами стартовые числа цепочек?

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

VAL в сообщении #1558109 писал(а):

2. Как обозвать (в заголовке столбца) тех, кто нашел цепочку? Авторы? Вряд ли. Первооткрыватели? ...?

Found by: / Найдена:

[EUgeneUS]

Dmitriy40 в сообщении #1558103 писал(а):

Счёт по 48 делителям у себя остановил, ускорители и PARI программу и насчитанный лог (для примера) выложил в то же облако
, папка M48n21, .gp файл и лог положил и отдельно если кому хочется посмотреть только их.
Кто будет считать: .gp файл надо настроить на нужный диапазон и нужное количество потоков.

Запустил у себя до 500e51, это будет считаться несколько суток.
Не могли бы Вы объяснить нотацию чисел после "maxlen=". Про первые три - догадался. Но вопрос связан вот с чем: вероятно будут находиться кандидаты в 21-ку, в которых полностью не разложатся все числа. Как их искать в логах?

[Dmitriy40]

EUgeneUS в сообщении #1558115 писал(а):

Не могли бы Вы объяснить нотацию чисел после "maxlen=". Про первые три - догадался. Но вопрос связан вот с чем: вероятно будут находиться кандидаты в 21-ку, в которых полностью не разложатся все числа. Как их искать в логах?

Да, извиняюсь, забыл про это рассказать.
Первое число после maxlen= это именно длина максимальной непрерывной цепочки.
Второе и последующие - это сколько чисел слева прошли тест номер 1,2,3,4, точнее на каком числе соответствующий тест остановился (или закончился если дошёл до правого конца цепочки). Разумеется в каждом тесте допроверяется лишь числа с 0 делителей (т.е. всё ещё потенциально могущие дать нужное количество делителей), проверка идёт слева направо по цепочке. Тесты ограничены так: первый простые до $2^{18}$, второй простые до $2^{26}$, третий 3с на каждое место, четвёртый 60с на каждое место. 60с по идее должно хватать для полного разложения, но если даже вдруг не хватит, то можно будет допроверить руками. Для полностью разложенной цепочки будет maxlen=21/21/21/21/21 и FOUND и запишется в отдельный файл M48.FOUND21.txt и счёт во всех потоках остановится на границе круга.
Цепочки не давшие /21 на первом тесте (т.е. точно не подходящие под искомые) в лог не выводятся, это отрезается командой if(rr1<nn, next); в 47-й строке .gp файла.
Каждый следующий тест запускается только если предыдущий дал кандидата ровно 21 длиной, это условие if(rr2==nn, и аналогичные в некоторых строках.
Все эти условия (по крайней мере первые три теста) весьма заметно влияют на скорость счёта так что менять не стоит, к тому же цепочки длиной менее 21 уже не интересны, именно поэтому выбрана такая схема проверки.

Если вдруг кто захочет поэкспериментировать с другими настройками тестов: шаг step уменьшать не стоит, лучше ограничить диапазон паттернов, заменив в 12-й строке маску "M%dn%d-???-???.exe" на менее общую, например "M%dn%d-?01-11?.exe" (всего 20 паттернов вместо 5760, причём включая и зеркальность).

Как искать в логе: в консоли есть команда findstr "\/21\/20" M48n21-?.txt - для поиска цепочек давших 20 на втором тесте, обратный слеш нужен так как обычный является спецсимволом и должен "экранироваться". Для 21 на первом, 21 на втором и 19,20,21 на третьем: findstr "\/21\/21\/21 \/21\/21\/20 \/21\/21\/19" M48n21-?.txt
Найти недоразложенные цепочки для ручной допроверки можно командой findstr "\/21\/21\/21\/21" | findstr /V "FOUND" - т.е. все тесты прошли, но FOUND нет, т.е. что-то где-то недоразложилось. Чтобы не искать их в логах добавьте после 79-й строки с записью найденного в FOUND ещё строку if(rr4==nn && maxlen<nn, write(strprintf("M%d.TOCHECK.txt",nd), ff[g],":",w)); и все недоразложенные кандидаты соберутся в одном общем для всех потоков файле. Я заменил .gp файл в облаке (не в архиве, там старый, только отдельно лежащий) на с этой доработкой, можете посмотреть куда что как вставить.

-- 21.06.2022, 19:23 --

Тем временем сделал ускорители для 14 чисел по 72 делителя, там же в облаке, папка M72n14. Тоже только x32 SSE версия, под x64 работает (и лучше чем под x32).
Архив с ускорителями, .gp файлом перебора и файлом лога с примером запуска. Лог и .gp файл так же положил и отдельно.
Доработка с недоразложенными цепочками отдельно внедрена. Тестов выполняется 5, так как числа сильно больше и 60с может не хватить для разложения, добавлен тест с ограничением в 900с на каждое место, это сильно долго, но срабатывать он будет хорошо если раз в день, потому на общую скорость вряд ли повлияет.
Круг (кстати почти ровно 3млн шагов) сделал не 2ч, а 12 минут, всё же 2ч как-то многовато, тем более если у других счёт медленнее, то 2ч превратятся в 4-5-7, что ну совсем много. Кто хочет по другому - меняйте step. Как быстро проверить изменения описал выше (временно изменить маску на менее общую вплоть до одного-двух паттернов и тестировать).

Ускорение от 4-х проверяемых чисел ещё снизилось, коэффициент фильтрации стал не 720, а всего 220, и скорость где-то 4.5млн/с вместо 18млн/с. И доля времени в ускорителях снизилась с трети до 1/6. Маловато. 83% времени тратится в PARI, что не есть хорошо.

[EUgeneUS]

Dmitriy40
Спасибо!
Как искать кандидатов теперь понятно.
Кстати, первый круг у меня ещё не закончился. Похоже, будет несколько часов (по сравнению с часом с небольшим у Вас)
Так что, вероятно сильно оптимистично хапнул до 500e51. Завтра посмотрим на скорость.

Dmitriy40 в сообщении #1558122 писал(а):

Ускорение от 4-х проверяемых чисел ещё снизилось, коэффициент фильтрации стал не 720, а всего 220, и скорость где-то 4.5млн/с вместо 18млн/с. И доля времени в ускорителях снизилась с трети до 1/6. Маловато. 83% времени тратится в PARI, что не есть хорошо.

Я выше, в рамках мозгового штурма, предлагал, как можно бы прикрутить ускорители к $pq$. Эта идея не проходная?

-- 21.06.2022, 19:58 --

Чем больше степень двойки в количестве делителей, тем больше "избыток" простых. Вероятно, в паттернах для ближайших цепочек на 96 делителей $p$ может просто не оказаться. Везде будут $pq$ и длиннее.

[Dmitriy40]

EUgeneUS в сообщении #1558128 писал(а):

Я выше, в рамках мозгового штурма, предлагал, как можно бы прикрутить ускорители к $pq$. Эта идея не проходная?

Если Вы об этом:

EUgeneUS в сообщении #1558009 писал(а):

2. Числа в позициях $pq$ тоже "пропустить через ускорители" по следующей схеме:
а) если число разделилось ровно на одно среднее простое - отправить остаток в isprime
б) если число разделилось более чем на одно среднее простое - отправить всю цепочку в треш.
в) если число не разделилось ни на какое среднее простое, то тут вопрос, что с этим делать. Может просто в лог сложить (если цепочка не выкинулась по другим причинам).

то идея рабочая, только это существенно переписывать внутренность ускорителей. И под разные типы паттернов (сколько может быть простых в первой степени) снова переписывать. Но фильтрацию это улучшит не очень существенно, в десятки раз всего лишь. Например для цепочек с 48 делителями, где много $pqrs$, до 5% цепочек ALL имеют меньше 48 делителей в непроверяемых местах и ускоритель их отбросить не может. Хотя, более чем 20-ти кратное снижение времени в PARI ... Это интересно. У меня бродила эта мысль ещё для M12, но там цепочек с небольшими простыми в разложениях было откровенно мало и погоды они не делали.
Предполагаю что под "средним простым" Вы понимаете простые до (порядка) 32768, которые сейчас в ускорителях и используются.

[VAL]

$M(1254)=5$

(Оффтоп)

23779383891192230506671033863155531750192020864534166025754851133088052431878612667470734403666167361133852951256451666922848504139788927180837984322004557213346455201736980308077989808904636379682633181947867104894840849969730489183871618820919975654052913046696336761504010788311214710235595703121

$M(966)=5$

(Оффтоп)

848929286187683489471827395537460473762509405239754338963801680258305184877373362673787429293214048718806432927867316823254462463638140821135691129255267838015578589577628488221688206818210463147842590303395348076001633197932142877799367528240529563833929585645172595977783203121

$M(1482)=5$

(Оффтоп)

44632381182946951583131225888824770812559718151006957216456663009265265495451313678006196258114445412829052734264387738888637357734096106046569287230136070592819822268911218286678300772229278293003593655227675759457105444846865384342097430064636799302643886788319517097147915021357029757930086859583222146311328887939453121

[VAL]

Поправил таблицу и комментарии к ней с учетом замечаний (если чего не учел, сигнализируйте).
Добавил ссылки на сообщения со стартовыми числами всех цепочек, упомянутых в таблице.
За исключением 96. Похоже, стартовое число этой цепочки здесь не пробегало. Ну или я его не нашел
Привожу его здесь. Чтобы было куда сослаться
$T(48,12) \le 3657247947154092365348734114264045665667638581245$

[VAL]

Сделал базовый паттерн для поиска десятки по 108 множителей.
Эмпирический прогноз 1 искомая цепочка на примерно 2 триллиона проверяемых.
Проблема в том, что числа, которые должны быть произведениями двух простых могут факторизоваться долго.
Однако после семи проверок на isprime и предварительных фильтров полных факторизаций будет совсем мало.
Можно переставлять квадраты:
в красноватых ячейках (6 вариантов);
желтоватых ячейках (90 вариантов);
сиреневых ячейках (90 вариантов).

[Dmitriy40]

$M(272)=7$:

(Оффтоп)

129999265554516530363443527657185338399600340543801806120772746992120256447825701220245361328125

[Yadryara]

Таблица улучшилась. Если будет желание сократить последний столбец, то напомню, что стандартное обозначение WR применяется не только в спорте.

VAL в сообщении #1558179 писал(а):

Сделал базовый паттерн для поиска десятки по 108 множителей.

Правильно, чё. Делители надоели, пришёл черёд множителей. Тем более, что и Дзюбанов обещал помочь. Пора, говорит, множители дзюбанить

[VAL]

Dmitriy40 в сообщении #1558202 писал(а):

$M(272)=7$:

(Оффтоп)

129999265554516530363443527657185338399600340543801806120772746992120256447825701220245361328125

А как искали?
Там ведь всего одна проверка на простоту, а составные довольно большие и множителей много (отсекать неудобно).

-- 22 июн 2022, 20:11 --

Yadryara в сообщении #1558205 писал(а):

Делители надоели, пришёл черёд множителей.

Вы не поверите! Каждый делитель - он на самом деле множитель, а каждый множитель - делитель.
Но самое удивительное при этом, что они еще и не синонимы.

[Dmitriy40]

VAL в сообщении #1558216 писал(а):

А как искали?
Там ведь всего одна проверка на простоту, а составные довольно большие и множителей много (отсекать неудобно).

А так и искал, сделал ускорители (48шт) с одним проверяемым числом, потом 4-х стадийная допроверка в PARI (максимум по 9с на число), остатки доразлагал руками, кажется 4-я цепочка подошла.
Интересно было как будут работать ускорители если аж 4 простых в первой надо, получится ли хоть одно проверяемое число, получилось (с трудом конечно), но скорость была просто никакая, фильтрация раз в 12 всего лишь, т.е. от PARI ускорение раз в 5-7. Больше так не хочу, тут хоть числа не слишком большие.
Цепочка нашлась кстати всего через 6100 шагов, счёт занял минут 15, но вот наладка/настройка его пару часов (без создания паттернов и компиляции, на это хватило полчаса).

[Dmitriy40]

$M(184)=7$:

(Оффтоп)

1631181288692726201588541373453362702859716990031391523347571165569745384002026410080172929831511370380897830042176768779754638671869