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

[wrest]

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

Ещё хочу напомнить, что VAL просил не использовать $k$, а использовать $i$, потому что $k$ уже занято. И вроде бы именно так и договорились. По крайней мере я этому следую.

Я надеюсь, вы не предлагаете мне погрузиться в пучину 300 страниц этой темы?

[Yadryara]

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

Я надеюсь, вы не предлагаете мне погрузиться в пучину 300 страниц этой темы?

Предлагаю. Причём на полном серьёзе. Я неоднократно перечитывал некоторые места.

Необязательно конечно именно 300 страниц изучать. Очень много содержательного сказано в самом начале, буквально на первых же страницах.

[wrest]

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

Предлагаю. Причём на полном серьёзе.

Ясно. Ну вы меня сюда зазвали, я ответил, что мне непонятно. Если вам понятно (на основе прочитанного в теме) - поделитесь пож-ста. Ну а нет, так и нет.

[Dmitriy40]

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

Теперь "внедряем" паттерн в m считаем вероятность - как?

Но ведь паттернов для D(24,6) больше одного - для какого будете считать? Или каких? А ведь они встречаются очень и очень сильно по разному. Например кортежей с $2^{11}$ в первом числе всего 5шт до 500млрд (и нашлись они за минуту):
58592131072
150062516224
326334900224
369759053824
494514817024
Т.е. в этом интервале их средняя плотность $10^{-11}$.
А с $3^{11}$ так же на первом месте - ещё сильно меньше, первые: 33907939155423, 113144673394971, 216758290274271, 350112100868379, аж сотни триллионов и полчаса счёта!

[Yadryara]

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

Если вам понятно (на основе прочитанного в теме) - поделитесь пож-ста.

Я именно это и делаю. Точнее, мы сейчас вдвоём вам помогаем. Подробнее напишу уже не сегодня.

[wrest]

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

Но ведь паттернов для D(24,6) больше одного - для какого будете считать? Или каких?

Сверхзадача - выбирать паттерн с максимальным коэффициентом вероятность/сложность. Под сложностью тут видится замедление обработки при росте m, ну скажем 40-значные считать быстрее (наверное) чем 70-значные. Но пока сосредоточиться на вероятности. Задача такая: дан паттерн, посчитать вероятность. Лучше брать небольшие длины (5-7) чтобы можно было проверить правильность расчёта прямо просеяв цепочки. Но в общем-то, можно и по более длинным цепочкам проверять прямым подсчётом - вероятности по каждому месту проверить нетрудно, потом все их перемножить.

[Dmitriy40]

wrest
По моему примерно этим занимался EUgeneUS некоторое время назад, даже целый калькулятор в Экселе запилил для расчётов вероятностей. В теме есть и его результаты, и программа для получения исходных данных для них (на что с какой вероятностью раскладываются числа).

[EUgeneUS]

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

По моему примерно этим занимался EUgeneUS некоторое время назад, даже целый калькулятор в Экселе запилил для расчётов вероятностей.

Есть такое.

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

Сверхзадача - выбирать паттерн с максимальным коэффициентом вероятность/сложность. Под сложностью тут видится замедление обработки при росте m, ну скажем 40-значные считать быстрее (наверное) чем 70-значные. Но пока сосредоточиться на вероятности.

А какая задача сейчас решается?
ИМХО, для всех $k \le 100$ цепочки, доступные имеющимися мощностями за разумное время, найдены.
Для следующих улучшений нужно увеличивать мощность на 1-2 порядка хотя бы.

[Yadryara]

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

Ну вы меня сюда зазвали,

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

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

Но ведь паттернов для D(24,6) больше одного

Не просто паттернов больше одного — серии паттернов разные. Я же про это уже написал:

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

Сказать о сериях здесь можно так: сборная солянка.

Возможно, уважаемый wrest не понял этих слов и потому проигнорил.

wrest, вы писали что Дмитрия понимаете лучше чем меня. И причина, видимо, проста: вы Дмитрия почему-то читаете более внимательно чем меня.

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

Сверхзадача - выбирать паттерн с максимальным коэффициентом вероятность/сложность.

Всё-таки давайте пока не паттерн, а серию выбирать.

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

Под сложностью тут видится замедление обработки при росте m, ну скажем 40-значные считать быстрее (наверное) чем 70-значные.

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

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

Лучше брать небольшие длины (5-7) чтобы можно было проверить правильность расчёта прямо просеяв цепочки.

Совершенно верно. Об этом и была моя большая просьба. Найдите самостоятельно хотя бы цепочки длиной 5.

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

Но в общем-то, можно и по более длинным цепочкам проверять прямым подсчётом - вероятности по каждому месту проверить нетрудно, потом все их перемножить.

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

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

Сверхзадача - выбирать паттерн с максимальным коэффициентом вероятность/сложность.

У меня сверхзадача в несколько другой формулировке: выбрать серию паттернов с максимальной скоростью нахождения кортежей.

Потому и в быстрых программах об этом писал, а не здесь.

Пока лидирует серия с одним простым.

[wrest]

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

А какая задача сейчас решается?

По паттерну ("внедрённым" простым в каждое число цепочки) вычислить вероятность того, что все числа в цепочке имеют нужное количество делителей, из чего оценить матожидание количества цепочек которые нужно перебрать до нахождения победной.

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

доступные имеющимися мощностями за разумное время, найдены.
Для следующих улучшений нужно увеличивать мощность на 1-2 порядка хотя бы.

Тоска-печаль.

А почему мы не можем сконструировать стартовое число цепочки такое что последующие числа имеют нужное количество делителей?
Ну например, мы элементарно можем сконструировать число, за которым следует нужное нам количество составных и среди них ни одного простого.

[EUgeneUS]

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

По паттерну ("внедрённым" простым в каждое число цепочки) вычислить вероятность того, что все числа в цепочке имеют нужное количество делителей, из чего оценить матожидание количества цепочек которые нужно перебрать до нахождения победной.

Если Вы рассматриваете это, как самостоятельную задачу, то - да. Мой "калькулятор шансов" её решает.
Если интересно - могу выслать пример таблички и комментарии к ней. Но в электронной почте, ибо файл нужно пересылать.

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

А почему мы не можем сконструировать стартовое число цепочки такое что последующие числа имеют нужное количество делителей?

Сконструируйте начальное число хотя бы для простых-близнецов

Если получится,

Цитата:

То вам седло большое, ковёр и телевизор,
В подарок сразу вручат, а может быть, вручат

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

Тоска-печаль.

Вообще говоря, можно присмотреться к цепочкам $k=12(2n+1)$
Все текущие цепочки для них ($k<100$) найдены с помощью ускорителей Дмитрия. А это значит:
а) из-за особенностей ускорителей (на каждый паттерн нужно компилировать свой ускоритель, а значит их не может быть очень много)
б) а это ограничивает стратегию поиска "неоптимальными" стратегиями. "Неоптимальными стратегиями" тут означает, что проверяются цепочки не с максимальной вероятностью, но они проверяются очень быстро.

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

то можно было бы попытаться улучшить, такие цепочки. В частности, поискать $D(36,14)$ и даже второй "финальный" пентадекатлон - $D(36,15)$.

-- 13.04.2026, 12:09 --

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

В частности, поискать $D(36,14)$

Тесты скрипта на PARI\GP и pcoul для этой цели показывают, что не хватает то ли 2, то ли 3 порядка (не помню точно) по быстродействию.

[Yadryara]

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

Тоска-печаль.

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

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

"Неоптимальными стратегиями" тут означает, что проверяются цепочки не с максимальной вероятностью, но они проверяются очень быстро.

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

не хватает то ли 2, то ли 3 порядка (не помню точно) по быстродействию.

Подчёркивание моё. wrest, ну вот видите. Думаете я от балды говорил, что быстрота программ занимает центральное место в поиске цепочек?

Только освойте, пожалуйста, поиск цепочек по паттерну от начала до конца. На первой же странице есть программа Владимира поиска по конкретному паттерну. Она для 12 делителей, но может это и хорошо, вам легче разобраться будет.

Там серия на 11 простых: 11-4-6!

[wrest]

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

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

Неее, предполагается, как мне видится, что для паттерна, где паттерн это числа $n0;m$ и вектор длиной равной длине цепочки который содержит "внедрённые" множители (то есть числа в цепочке на них делятся гарантированно), проверяется довольно много (порядка, скажем, 10^9 может больше) цепочек с начальными числами вида
$n_i=n0+i\cdot m$ (где i меняется в пределах от $0$ до $10^9$)
Так что подготовка паттерна занимает пренебрежимо малое время.
Текущие достижения в pari/gp -- фильтрация по готовому паттерну со скоростью примерно $10^5$ цепочек в секунду (или больше в зависимости от мощности железа) на размерах прогрессии порядка $2..3\cdot10^5$ членов (т.е. несколько сот тысяч цепочек по одному паттерну) - это для $n0,m \approx 10^{40}$

-- 13.04.2026, 15:22 --

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

а) эффективно отсеивает цепочки с большим количеством ожидаемых простых чисел.

Ну тут у нас есть такие успехи. Предвычисляем остатки от деления на простые числа в диапазоне до $2^{20}..2^{24}$ (от $10^5 $до $10^6$ "табличных" простых) и модулярными операциями выясняем есть ли в цепочке число, которое делится на очередное простое из таблицы. То есть массово факторизуем цепочки целиком по таблице простых. Ну это всё считаем, цепочки где есть числа с перебором множителей выкидываем, прошедшие проверяем на недобор множителей и в конце полностью факторизуем прошедшие через все фильтры. Вот это в в совокупности даёт скорость в 10^5 цепочек в секунду. Алгоритмически считаем, что там всё эффективно для высокоуровневого языка без учёта архитектуры CPU.

-- 13.04.2026, 15:25 --

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

в) не требовал бы компиляции под каждый паттерн.

паттерн (в смысле упоминаемом мной выше: первый член арифметической прогрессии n0; шаг прогрессии m и вектор со встроенными множителями) может передаваться в функцию как параметр.

[EUgeneUS]

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

Неее, предполагается, как мне видится, что для паттерна, где паттерн это числа $n0;m$ и вектор длиной равной длине цепочки который содержит "внедрённые" множители (то есть числа в цепочке на них делятся гарантированно), проверяется довольно много (порядка, скажем, 10^9 может больше) цепочек с начальными числами вида

Не на не.

Асимптотика вероятности найти цепочку устроена так, что с ростом чисел $N$ в цепочке (то есть с ростом $i$) вероятность падает как $\frac{1}{(\ln N)^l}$, где $l$ - количество чисел в цепочке.
Эмпирическое правило: увеличиваем величину чисел в цепочке на два порядка - вероятность падает в два раза.
Для $D(36,14)$ и $D(36,15)$ огромное количество паттернов (больше с огромным запасом, чем нужно) обеспечивается только за счет перестановок квадратов простых чисел.
Вот и получается, что "оптимальная стратегия" - это проверять в каждом паттерне единицы, может быть десятки цепочек.
А чтобы "оптимальная стратегия" всё таки была оптимальной, время "подготовки паттерна" должно быть сравнимым с временем проверки одной цепочки.

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

Текущие достижения в pari/gp -- фильтрация по готовому паттерну со скоростью примерно $10^5$ цепочек в секунду (или больше в зависимости от мощности железа) на размерах $2..3\cdot10^5$ - это для $n0,m \approx 10^{40}$

Для нахождения трех цепочек $D(12,15)$ было выполнено примерно $10^{17}$ проверок. По оценкам Дмитрия, насколько помню.
Для нахождения $D(36,14)$ нужно столько же (по порядку величины), но если использовать стратегию, как описано выше.
А это десятки тысяч лет в один поток, при скорости проверок $10^5$ в секунду.
И числа там будут где-то в районе 70-значных.
Правда там почти все ожидаемые числа - простые. А оставшиеся полупростые.

[wrest]

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

Асимптотика вероятности найти цепочку устроена так, что с ростом чисел $N$ в цепочке (то есть с ростом $i$) вероятность падает как $\frac{1}{(\ln N)^l}$, где $l$ - количество чисел в цепочке.
Эмпирическое правило: увеличиваем величину чисел в цепочке на два порядка - вероятность падает в два раза.

Тут не очень понятно. Если мы перебираем числа вида $n=n0+i\cdot m$ где n0 и m порядка скажем 40 цифр, а i порядка 9 цифр, то n будет порядка 40..49 цифр. Не такой уж большой рост, для миллиарда цепочек по одному паттерну. А если n0 и m будут 70-ти значные, то относительный рост 70->79 знаков ещё меньше.

-- 13.04.2026, 16:15 --

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

Там серия на 11 простых: 11-4-6!

Я не понимаю что это значит, игнорирую.