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

[EUgeneUS]

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

$2^8$ в 8-й позиции, $5^2$ в 10-й, $7^2$ в первой, $3^2$ в 6-й, остальные тоже произвольно.

Нашел аналогичный расклад. Отличается тем, что $7^2$ стоит в 11-й позиции, а не в первой.

-- 27.04.2022, 21:04 --

Но с учетом того, что вот этот вариант:

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

$2^8$ в 8-й позиции, $5^2$ в 10-й, $7^2$ в первой, $3^2$ в 1-й и 10-й, остальные достаточно произвольно (только чтобы не было 11 и 13 без квадрата);

а) даёт шаг/модуль более чем на три порядка меньше
б) перестановки дадут огромное количество паттернов.

ИМХО, правильный вариант будет такой:
а) определить "разумное количество паттернов". (40 с лишним тысяч было ещё разумным )
б) в рамках "разумного количества паттернов" выбрать более перспективные перестановки (они будут чуть более перспективными).
в) и попробовать поискать 14-36 в этой системе паттернов.

Что скажете?

-- 27.04.2022, 21:24 --

и всё таки.
Наиболее оптимальная "система" паттернов (из найденных) для 14-ки относительно оптимальной системы для 15-ки снижает:
1. Количество искомых простых с 10 до 9
2. Количество квадратов "средних" простых: с 21 до 20

Всего лишь.

Переход на систему паттернов с одним квадратом для 14-ки относительно известной оптимальной системы для 14-ки без квадрата снижает:
1. Количество искомых простых с 9 до 7
2. Количество квадратов "средних" простых: с 20 до 16

При этом снижение количества квадратов "средних" простых (для 14-ки без квадрата большого простого) снизило шаг на три с лишним порядка. Так что, система с одним квадратом всё ещё представляется перспективной.

[Dmitriy40]

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

Поэтому последовательность проверки видится такой:
1. Проверяем квадрат.
2. Проверяем все большие $p$
3. Проверяем, что квадрат - простого (если, конечно, его проверка на простоту не будет в два раза быстрее больших простых, но это вряд ли)
4. Проверяем $pq$

В общем это уже не столь существенно, проверка на простоту конечно зависит от величины чисел, но довольно странным образом (растёт, но неизвестно как в точности). И в любом случае не сравнима с факторизацией.
А проверять на простоту под квадратом выгоднее потому что она будет заметно реже чем простота других, т.е. фильтрация выгоднее сначала именно по нему. Ну сравните сколько из миллиарда 80-значных чисел из любой арифметической прогрессии (а $n=n_0+km$ именно таковой и является) простые и из скольких извлечётся квадрат и даст простое, мы ведь не можем в паттерне учесть что под квадратом именно простое и даже что именно квадрат.

К тому же я остаюсь в уверенности что выгоднее вообще перебирать по этому $p^2$, если получится наложить на него достаточно сильные условия чтобы это имело смысл. С 30-ю делителями это получилось, а там было лишь 3-4 других числа, тут же их 7, т.е. условия будут ещё жестче (и шаг перебора простого соответственно больше). Помнится числа там в общем-то сравнимые, кажется примерно 70-значные.

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

две раскладки, которые у меня получились с квадратом.

Простите, только пришла в голову мысль проверить — во второй раскладке квадрат произведения двух простых должен иметь остаток 248 по модулю 256 или остаток 31 по модулю 32, чего быть никак не может, квадрат любого нечётного числа (а произведение двух простых кроме двойки нечётно) даёт остатки лишь 1 по модулю 8 или 1,9,17,25 по модулю 32. Так что вторая раскладка неразрешима.
По первой, остаток по модулю 32 должен быть 1 и вроде бы такое проходит, но среди простых до $10^8$ нет ни одного, которое дало бы простое на месте $2^8$, что как бы намекает на неразрешимость, выше я уже натыкался на такое.
Да, а первая не проходит по модулю 49, никакое число 0..48 после возведения в квадрат и домножения на 8 и вычитания 5 не даёт кратного 49.

-- 27.04.2022, 22:33 --

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

Наиболее оптимальная "система" паттернов (из найденных) для 14-ки

Э, я что-то пропустил и она уже была опубликована/выбрана?

[EUgeneUS]

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

В общем это уже не столь существенно, проверка на простоту конечно зависит от величины чисел, но довольно странным образом (растёт, но неизвестно как в точности).

Хм... Тут идея такая:
1. Проверки нужно проводить по критерию "цена-качество". То есть проверки дающие лучшую фильтрацию за меньшее время - нужно проводить раньше.
2. Проверка, что число является квадратом простого - это две проверки: что число является квадратом, и что $\sqrt{N}$ таки простое. Идея в том, что никто не мешает эти проверки разделить во времени.
3. Если проверяем простоту числа $N$ и простоту числа $\sqrt{N}$ (при этом корень точно целый, это проверили раньше),
а) при этом считаем, что скорость проверки различается меньше, чем в два раза.
б) то выгоднее сначала проверять простоту чисел $N$, а уже потом простоту числа $\sqrt{N}$. Так как вероятность, что число $N$ будет простым в два раза меньше, чем вероятность, что будет простым число $\sqrt{N}$.

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

Простите, только пришла в голову мысль проверить — во второй раскладке квадрат произведения двух простых должен иметь остаток 248 по модулю 256 или остаток 31 по модулю 32, чего быть никак не может, квадрат любого нечётного числа (а произведение двух простых кроме двойки нечётно) даёт остатки лишь 1 по модулю 8 или 1,9,17,25 по модулю 32. Так что вторая раскладка неразрешима.

Вот это важное замечание. КТО может запретить некие системы паттернов и-или перестановки внутри системы паттернов... Но в КТО и модульной арифметики вообще не копенгаген, и нужна отдельная проверка\экспертиза со стороны других участников.
Впрочем, вторая раскладка была хуже. Первая не бракуется?

[Dmitriy40]

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

Первая не бракуется?

Бракуется, по модулю 49 ($7^8$ брать даже не стал), я туда выше дополнил.
Только лучше бы меня перепроверить ...

[EUgeneUS]

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

Э, я что-то пропустил и она уже была опубликована/выбрана?

Из найденных же.
Имелась в виду эта:

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

$2^8$ в 8-й позиции, $5^2$ в 10-й, $7^2$ в первой, $3^2$ в 1-й и 10-й, остальные достаточно произвольно (только чтобы не было 11 и 13 без квадрата);

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

Бракуется, по модулю 49 ($7^8$ брать даже не стал), я туда выше дополнил.

Жаль. Пока других вариантов с квадратом нет - идея с квадратом забракована. Впрочем, весьма интересно, что скажет уважаемый VAL по этому поводу. Может и упираться в этот вариант нет смысла в принципе...

[Yadryara]

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

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

Ну а я жду ответы на вопросы про КМК.

Я посчитал их риторическими и неактуальными. Например в M36n13 уже присутствует $3^8$ вместо квадрата и получается уже они были не КМК. Фактически КМК (если ещё не обращать внимание на исключение с двойкой) остались в силе лишь для M12n15/14, а ими похоже занимаетесь только Вы.

На данный момент, вроде бы только я, но Хьюго Баскервиль/Босс совсем недавно обновил рекорд для 12-10. Возможно, продолжает заниматься.

Просто у меня возникло и далее укрепилось подозрение, что мы говорим о разном. У меня в КМК "M" — минимальные, а у Вас "M" — малые.

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

M12n15/14

А здесь-то что означает "M" ? Количество делителей?

У VAL "M" — максимальное количество чисел с данным количеством делителей подряд:

$M(6)=5$
$M(8)=7$
$M(12)=15$
$M(24)=31 ?$

Стоит ли одной и той же букве "М" приписывать столько разных смыслов?

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

Также интересно Ваше мнение, как переделать проги с подквадратного 41 на 43.

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

Заменить 7 на 8 в r=Set([]), плюс оставить bb=[5,37]. Сам не пробовал, но новых подводных камней не вижу.

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

[EUgeneUS]

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

$2^8$ в 8-й позиции, $5^2$ в 10-й, $7^2$ в первой, $3^2$ в 1-й и 10-й, остальные достаточно произвольно (только чтобы не было 11 и 13 без квадрата);

Если в первой позиции заменить $3^2$ на $3^8$, то эта раскладка будет оптимальной для 14-ки (без квадрата большого простого). Она обеспечивает:
1. Количество больших (искомых) простых - 9 штук. Не улучшается.
2. Общее количество квадратов "средних" простых - 19 штук. Не улучшается.
3. Количество пар квадратов "средних" простых - 8 штук. Можно уменьшить на 1, но ценой увеличения количества больших простых до 10.

Эта расстановка имеет 3 варианта расстановки для 7-к.

[VAL]

Завтра отбываю в на 10 дней.
Зарядил 4 компа на поиск 18 чисел по 24 делителя и 20 чисел по 48 делителей.
Надеюсь, что к моему возвращению соответствующие цепочки найдутся.

В перспективу найти в ближайшее время 15 (или хотя бы 14) чисел по 36 делителей не верю (возможно, зря).
Заглянул в таблицу HUGO и заметил, что он активно занимается поиском T(30, x) (в его обозначениях).
В текущем месяце добрался до цепочки из 7 чисел по 60 делителей.
Полагаю, мы легко продвинемся существенно дальше.
До отъезда попробую составить паттерны и оценить перспективы.

Кстати, Hugo исходит из оценки $M(60)\le 23$ (это уже в моих обозначениях). Есть подозрение, что ее можно улучшить до $M(60)\le 15$

[Dmitriy40]

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

Просто у меня возникло и далее укрепилось подозрение, что мы говорим о разном. У меня в КМК "M" — минимальные, а у Вас "M" — малые.

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

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

А здесь-то что означает "M" ? Количество делителей?

Да.

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

Стоит ли одной и той же букве "М" приписывать столько разных смыслов?

Я лишних смыслов не приписывал, лишь не указываю скобки (символы скобок далеко не везде допустимы, а удобно везде называть одинаково).

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

В перспективу найти в ближайшее время 15 (или хотя бы 14) чисел по 36 делителей не верю (возможно, зря).

Чего-то я тоже не верю. 9 простых это слишком много, если принять вероятность даже $1/20$, то получится одна цепочка ALL на $20^9=512\cdot10^9$ шагов, и даже если вероятность остальных 5-ти мест вдвое выше, то общая вероятность 1:51200трлн шагов, моя программа проверяет порядка 83млн шагов в секунду, т.е. в среднем надо 20 лет в один поток. И это по довольно оптимистичным оценкам вероятностей. Если их взять более правдивыми $1/24$ и $1/15$ для проверяемых и непроверяемых мест, то оценка станет 1:2e18 шагов или 700 лет.

Посмотреть M60n15 это интересно, только ведь снова вылезут 10 простых, без них никуда. А числа будут ещё больше (там же простое в 4-й степени), значит вероятность простых ещё меньше. Вот поискать M60n13 намного более реально (немногим менее реальнее найденной M36n13). Может стоит с этого и начать. Тоже подумаю, вроде тут паттерны несложные.

[EUgeneUS]

VAL
Как-нибудь прокомментируете идею поискать 14 на 36 делителей с паттернами с одним квадратом большого простого?
Есть шанс, что может быть лучше? Или это в принципе не проходной вариант?

[VAL]

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

До отъезда попробую составить паттерны и оценить перспективы.

Сляпал на скорую руку на цепочку из 11 чисел по 60 делителей.
Перспективы хорошие. Цепочки из 8, 9 и 10 должны найтись по ходу.
Одновременная простота пяти требуемых чисел наступает по оценкам примерно раз на 6 миллионов проверок.

В таблице можно переставлять ярко желтые между собой, желтоватые между собой. Аналогично с зелеными.
Итого получается 2304 паттерна.

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

Как-нибудь прокомментируете идею поискать 14 на 36 делителей с паттернами с одним квадратом большого простого?
Есть шанс, что может быть лучше? Или это в принципе не проходной вариант?

Так я же уже ответил, что не считаю это перспективным. Впрочем, в детали не вдавался.

В нахождение 15 чисел по 60 делителей не верю, тем более. Полагаю, что после нахождения 11 реально замахнуться на 12 и 13.

[Yadryara]

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

Да мне собственно без разницы.

Вот это-то и грустно. Ибо такой подход нередко мешает понимать друг друга.

Я уже на 2-й странице писал:

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

Если придерживаться схемы, которую я назвал концепцией минимальных квадратов, то один из вариантов можно изобразить так:

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

Если строго в смысле минимальных, то вообще говоря непонятно почему двойка исключается (оговорка что мол больше длины как-то искусственна).

Что-то, простите?? Кем исключается, откуда, чья оговорка?

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

Ну и все Ваши модификации тогда уже не КМК

Насчёт всех говорить пока не буду, но в последних вариантах как раз именно по этой причине и нет аббревиатуры КМК.

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

Я лишних смыслов не приписывал,

По сравнению с VAL у Вас совсем другой смысл "М". Сравните:

У VAL "M" — Mаксимально возможное количество чисел с данным количеством делителей подряд.

У Вас "M" — количество делителей.

[Dmitriy40]

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

По сравнению с VAL у Вас совсем другой смысл "М". Сравните:

У VAL "M" — Mаксимально возможное количество чисел с данным количеством делителей подряд.

У Вас "M" — количество делителей.

У него $M(60)=11$, у меня M60n11. Не вижу путаницы. Убрал скобки и заменил "=" на "n". Не приписывая буквам никакого специального смысла.

[VAL]

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

У него $M(60)=11$,

Нет.
Если мы найдем цепочку из 11 чисел, то будет строго доказано, что $M(60) \ge 11$. Причем на самом деле наверняка больше.
$M(k)$ - это длина максимальной цепочки, а не максимальной известной.

Кроме того, это обозначение ввел не я. Его ввели Дюнш и Эгглтон в первой работе, посвященной этой тематике.

[Dmitriy40]

Ну значит в моём понимании "M60n11" это цепочки из 11 чисел по 60 делителей. И "M60" всё так же означает 60 делителей. ОК, без значка равенства.
И я так и не понял где выше была с этим путаница, с буквой M.