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

[Dmitriy40]

Про вероятности от количества простых я согласен, мои вычисления чуть выше примерно то же показывают.

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

Кроме того, использовав в паттерне искомое простое в квадрате мы очень сильно ограничим возможные варианты подстановок дополнительных простых в квадратах, т.е. очень существенным образом количество вариантов паттернов, уже не 15!-20! (как у меня постоянно выходит что для М24, что для М36), а сколько там, может быть их станет достаточно мало для полного перебора.
Потому что выбирать одну-две группы паттернов и один из 10! вариантов в них ради сокращения программ хотя бы до сотни тысяч — это проверка по вершинам, которая результата не принесла.
А всего возможных групп паттернов для М36 (и для М24) выходит десятки тысяч, и в каждую подставлять до 15-20 простых. Т.е. перебор всех низин абсолютно нереален. И вопрос как их разумно ограничить.

Вот например для М24 выбрал 22 группы с 17 прямо проверяемыми числами, а подстановка 6-ти простых (т.е. всего 720 вариантов в каждой группе) в квадратах увеличивает количество проверяемых чисел до 23 из всего 31. 8 мест остаются непроверяемыми, шаг 1e118. К сожалению 4 непроверяемых места в середине паттерна потому найти сразу длинные непрерывные цепочки маловероятно. И не получается 14 требуемых простых (т.е. 14! паттернов) сильно сократить отрезав края, там проверяемые числа без дополнительных простых.
Попытка учитывать лишь середину паттерна приводит к 22-м группам с 13-ю прямо проверяемых числам и при подстановке 4-х простых в квадратах увеличивается до 17 проверяемых (по 24 паттернов на группу). И всего надо 16 дополнительных простых. Зато шаг всего 1e84 и числа только в квадратах (т.е. паттерны КМК).
Какой набор даже из этих двух выбрать и как ограничить хотя бы непроверяемые числа (даже 14! вариантов нереально) мне непонятно. Расставив же произвольно 8-12 простых по непроверяемым местам и начав проверять вероятность нахождения решения ничтожна.

[Dmitriy40]

VAL
Вопросы по инструкции с точки зрения пользователя:
1. Как распараллелить на несколько потоков?
2. Как задать лишь кусок работы, не пересекающийся с другими участниками? Сейчас все запустят выложенный код и будут считать одно и то же.
3. Сколько оценочно времени требует один цикл работы? Т.е. как часто надо перезапускать счёт?
4. Как его уменьшить/увеличить?
5. Про поправить путь к логу не написано. И лучше бы путь указывать относительным (или вообще не указывать, только имя файла).
6. Смысл изменяемых параметров лучше (дополнительно кратко) описывать прямо в комментариях PARI кода.
7. Статистика прогресса при работе выводится слишком редко, запустил и непонятно считает или нет. И крайне неравномерно, например 22%, потом только конец счёта (во всяком для минутных интервалов счёта, на недельных разумеется не проверял).
8. По окончании счёта из внешнего .gp файла PARI не закрылся и имя программы не вывелось.
9. Время работы "на круг" вообще не выводится что не позволяет планировать вычисления, тем более в несколько потоков с разной скоростью в каждом.
10. Считать количество единичек в векторе приходится глазами, неужели сложно было допечатать vecsum()?
Понятно что лично я легко со всем этим разберусь, но все ли смогут поменять код под себя ... Впрочем может я неправильно думаю обо всех и им все эти тонкости и не нужны ...

-- 16.04.2022, 14:47 --

Странно что цикл по u2/U2 идёт лишь до 11, хотя оба вектора длиной 12.

-- 16.04.2022, 14:58 --

Меня выше критиковали что числа слишком большие и не поддаются факторизации, сами же молча сделали ограниченную факторизацию 11-ти больших чисел и ничего, типа здесь можно. Некрасиво (в плане критики).

[VAL]

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

Они получены прямым способом или обратным?

Поскольку я не знаю, что такое обратный способ, полагаю, что прямым
Вот пример для одной позиции одного из паттернов для поиска цепочек из 20 чисел по 48 делителей.

F19 := [0, 0, 0, 0, 0, 0, 0]; for j from 10000001 to 10010000 do d := nops(ifactors((a*(j*mm+p1)+11)/m19)[2]); if d > 7 then d := 7 end if; F19[d] := F19[d]+1 end do; F19; evalf((1/10000)*F19, 5)

Здесь важно, что результаты примерно одинаковы при изменении размера чисел (на несколько порядков), номера позиции, выбора паттерна.
И даже относительно замены 48 делителей на 24 или 12.
Например, вот результат для приведенного фрагмента:

[0.069600, 0.22380, 0.29640, 0.24000, 0.11360, 0.041800, 0.014800]

А вот усредненный по всем позициям:

[0.062000, 0.19800, 0.31200, 0.25800, 0.11000, 0.038000, 0.022000]

[VAL]

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

Мне другое не совсем понятно:[..]

Это вопросы "философские". На них отвечу, чуть позже, после ответов на конкретные вопросы по программкам.

[Yadryara]

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

Поскольку я не знаю, что такое обратный способ, полагаю, что прямым

Здесь прямой, да. Про обратный способ я выше объяснял многократно.

Между тем, посчитал вероятность нахождения непрерывной 14-ки для КМК37-11 и существующих программ. Оказывается первая непрерывная 14-ка тоже припозднилась, причём ещё сильнее чем первая 15-шка.

Первая 15-шка нашлась после 60 миллиардов попыток при расчётных 44 ярдах.

Первая непрерывная 14-ка нашлась после 4.5 миллиардов попыток при расчётных 3.0 ярдах.

Насколько я помню, в любом из 46080 паттернов, если первое место проверяемое, то 15-е нет. И наоборот, если 15-е место проверяемое, то 1-е нет. Всегда-всегда.

И формула вероятности для непрерывной 14-ки получается совсем простая

$$Y_1^{10}Y_2^4(1-Y_1) + Y_1^{11}Y_2^3(1-Y_2)$$

Для 0-4е36 взял $Y_1=0.192; Y_2=0.243$.

Это я к тому, что вполне можно найти и меньшую 14-ку и меньшую 15-ку. Так что передайте Jon E. Schoenfield-у, пусть тоже подключается к обсчёту. Это ведь его последовательность.

[VAL]

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

VAL
Вопросы по инструкции с точки зрения пользователя:
1. Как распараллелить на несколько потоков?

Запускается несколько экземпляров PARI. Каждый автоматически занимает один поток.
В PARI есть возможность изменить это. Но не вижу необходимости.

Цитата:

2. Как задать лишь кусок работы, не пересекающийся с другими участниками? Сейчас все запустят выложенный код и будут считать одно и то же.

Я именно потому и не выкладываю код. То, что я прислал - иллюстрация к инструкции.
А программки я высылаю в личку, тем, кто отзовется. Пока это только EUgeniUS, не пожалевший 4 потока.
IMHO, там проще всего координировать действия. Один (главный путаник ) ведет учет и контроль, а остальные запускают одни и те же программки, меняя всего один параметр (i1).

Цитата:

3. Сколько оценочно времени требует один цикл работы? Т.е. как часто надо перезапускать счёт?

Это зависит от компа.
Каждый может подобрать удобный для него шаг. После пробных запусков.
Все это написано в примечаниях к инструкции.
Кстати, они видны?

Цитата:

4. Как его уменьшить/увеличить?

Для этого надо изменить число, прибавляемое к i1 в строке "i2 = i1 +.."
Похоже, примечания таки не видны.

Цитата:

5. Про поправить путь к логу не написано. И лучше бы путь указывать относительным (или вообще не указывать, только имя файла).

Точно не видны Другая версия Word?

Цитата:

6. Смысл изменяемых параметров лучше (дополнительно кратко) описывать прямо в комментариях PARI кода.

Все описано в невидимых комментах А теперь и здесь.

Цитата:

7. Статистика прогресса при работе выводится слишком редко, запустил и непонятно считает или нет. И крайне неравномерно, например 22%, потом только конец счёта (во всяком для минутных интервалов счёта, на недельных разумеется не проверял).

Возможно. Я подстраивал под себя. Я запускаю большие интервалы на быстром компе. При более частой выдаче прогресса замусоривается экран.

Цитата:

8. По окончании счёта из внешнего .gp файла PARI не закрылся и имя программы не вывелось.

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

Цитата:

9. Время работы "на круг" вообще не выводится что не позволяет планировать вычисления, тем более в несколько потоков с разной скоростью в каждом.

Время выводит сам PARI. Правда только часы-минуты-секунды. Сутки считаю сам.

Цитата:

10. Считать количество единичек в векторе приходится глазами, неужели сложно было допечатать vecsum()?

Самое странное замечание! Это количество, увеличенное на 3 (количество простых), выводится сразу после вектора.

Цитата:

Странно что цикл по u2/U2 идёт лишь до 11, хотя оба вектора длиной 12.

Это мой глюк. Он не приводит к ошибкам. Просто снижает качество фильтра. Обиднее другое. Я эту штуку (доставшуюся по наследству от цепочек длины 19) уже обнаружил. И полагал, что исправил. Однако, "Жив, Курилка!"

Цитата:

Меня выше критиковали что числа слишком большие и не поддаются факторизации, сами же молча сделали ограниченную факторизацию 11-ти больших чисел и ничего, типа здесь можно. Некрасиво (в плане критики).

Конечно, ничего! Это же предварительный фильтр. Его предназначение - забраковать заведомо непригодные варианты. А для отфильтрованных идет полное разложение.

Сейчас выложу новую инструкцию (pdf). А то вместо инструкции получился пример программы
Запускать эту программку не надо. Запускаемые высылаю в ЛИЧКУ.

[Yadryara]

\begin{tabular}{|l|c|c|c|c|c|c|} \hline Хороших чисел & 11+ & 11 & 12 & 13 & 14 & 15 \\ \hline \text{<4e35 11-23} & 255 & 201 & 42 & 12 & & \\ \text{<4e35 КМК37-11} & 325 & 258 & 59 & 5 & 3 & \\\hline \end{tabular}

Олловских нашёл 8 против 5.

[Dmitriy40]

VAL
Спасибо за разбор, думаю он пригодится людям. Прокомментирую только существенное.

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

Запускается несколько экземпляров PARI. Каждый автоматически занимает один поток.

И везде считается одно и то же ... Подсказка: я думал ответ будет например "заменить for(i=i1,i2, на forstep(i=i1+N0,i2,NN," (N0=0..NN-1) — этого уже достаточно для распараллеливания работы по NN потокам.
Кстати в этом цикле, for(i=i1,i2,, значение i=i2 будет проверено дважды (в конце одного цикла и начале следующего), что в принципе может привести к дублированию цепочки в логах. Маловероятно, но у меня реально было. К счастью на скорость влияние ничтожно.

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

Все это написано в примечаниях к инструкции.
Кстати, они видны?

После сравнения с pdf оказалось что видно только второе, V2, первое лишь подсвечено жёлтым, но без текста примечания.
И в них (V1 и V2) так и нет про замер скорости и какое число влияет на время работы.

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

При более частой выдаче прогресса замусоривается экран.

Для этого есть известные решения (например писать в лог и на экран разными командами и в разном формате, write и printf, причём на экран удобно без перевода строки, в ту же строку, будет идти счётчик без замусоривания экрана (но не лога если включен, что считаю вредным)). Конечно это дело вкуса.

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

А вот почему имя не вывелось..? У меня выводится.

Возможно Вы по иному запускаете счёт (например из уже запущенного PARI командой \r file.gp, я же запускаю из консоли командой gp64 -q file.gp). Потому я стараюсь для вывода везде использовать команды print и не надеяться на соглашения о печати переменных в самом PARI.

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

Время выводит сам PARI.

Если включен соответствующий параметр. У меня включен, но при запуске из консоли не выводит (как и значения переменных m,p1,a,uu,MM,i1,i2), видимо считается что это уже не диалоговый режим и всё что хотели вывели сами командами print ...

В общем ИМХО все эти ответы и пояснения должны быть сразу в инструкции ... Или прикладываться к запускаемым программам в личке. Впрочем, если всё всех и так устраивает ... то себе я сам поправлю как надо.

[EUgeneUS]

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

И везде считается одно и то же ...

Так уважаемый VAL под каждый заявленный поток высылает в ЛС отдельный текст для PARI/GP. Не должно бы в каждом потоке считаться одно и то же.
В остальном Ваши комментарии и ответы на них были весьма полезны.
Добавлю. Ещё не хватает механизма для возобновления счета после останова. Чтобы считалось не сначала, а с места останова (или около него)

[Dmitriy40]

Я подозревал об этом, что в разных потоках будут разные программы.
Про возобновить счёт, это как раз вопрос более частого вывода статистики, чтобы в ней было чётко видно до какого i проверили. Вот почему кстати и не люблю все эти индексы, предпочитаю в реальные числа пересчитывать, уж несколько умножений/делений на скорость не повлияют, а удобства добавят сильно.

И ведь совершенно несложно было дать мне эти 10-30-50 паттернов и попросить наделать ускорителей под них, и SSE и AVX2, но видимо тысячекратное ускорение никому не интересно (или отсутствующих вирусов боятся, уж не знаю) ... Я ведь давным давно озвучил предложение нагенерить сколько надо (в разумных пределах) любых паттернов и до сих пор его не отзывал. Ну пусть даже не тысячекратное из-за лишь трёх проверяемых чисел, пусть даже стократное (вот даже восстанавливать паттерн из программы и замерять реальное не хочется) ...

Прикину сколько бы так искали пятнашку М12: после проверки $10^{38}/4.4\cdot10^{26}\times46080\approx1.05\cdot10^{16}$ кандидатов нашлось три пятнашки, т.е. в среднем надо было 3.5 квадриллиона попыток (шагов) или просчитать до 1.54e42, при этом 1e38 по одному паттерну проверялся у меня 4 минуты, т.е. хватило бы 43 дня (в один поток). Да, немного не хватило, я успел лишь половину этого просчитать по одному из паттернов ... Даже интересно найдётся ли за неделю в 4 потока пятнашка именно по тому паттерну ... Хотя, выше говорили это вероятность лишь 63%, для 95% надо втрое дальше или почти месяц счёта в 4 потока, печально. Без ускорителей на голом PARI 43000 дней или 115 лет на поток.
Для искомой двадцатки я так понимаю никто оценки вероятностей не проводил и ничего озвучивать не собирается ...

[Yadryara]

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

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

Вот именно! Хотя в стократном очень сильно сомневаюсь.

Я же ведь как раз про эти 3 одиночных простых спрашивал:

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

Dmitriy40, я правильно понимаю, что с Асмом было бы ещё в разы быстрее?

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

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

Надо бы всё-таки проверить, сможет ли Асм и здесь помочь.

И коммент специально для Саратова.

$66387422053662391209161093722597723545$ имеет 4 простых множителя в разложении, но 12 делителей.

$5110145662825543332475140141244972679378639054064347$ имеет 6 простых множителей в разложении, но 48 делителей.

Здесь нет противоречия.

[kotenok gav]

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

Похоже, меня не только Лев игнорирует

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

[Yadryara]

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

Вот пример для одной позиции одного из паттернов для поиска цепочек из 20 чисел по 48 делителей.
Код:

F19 := [0, 0, 0, 0, 0, 0, 0]; for j from 10000001 to 10010000 do d := nops(ifactors((a*(j*mm+p1)+11)/m19)[2]); if d > 7 then d := 7 end if; F19[d] := F19[d]+1 end do; F19; evalf((1/10000)*F19, 5)

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

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

Похоже, меня не только Лев игнорирует

Так меня не только Лев, меня даже Прав не слышит. А ещё бывает ты прав, а тебя не слышат.

[VAL]

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

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

Называйте, как хотите. Но эта именно та вероятность, которая нас интересует.
Какая нам разница, сколько делителей имеют в среднем числа, которые нам заведомо не подходят и которые мы не проверяем.

-- 17 апр 2022, 12:56 --

kotenok gav в сообщении #1552785 писал(а):

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

Я Вам и без запуска скажу. Одна программа нагрузит процессор на $\frac{100}n\%$, где $n$ - количество логических ядер.

[EUgeneUS]

kotenok gav в сообщении #1552785 писал(а):

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

Это в первую очередь зависит от модели Вашего процессора. А во вторую от того, насколько компьютер загружен другими задачами.
Например, у меня
а) в процессоре четыре ядра, каждое по одному потоку. Всего четыре потока.
б) компьютер ничем не загружен (он монопольно выделен для счета).
в) итого - могу отдать четыре потока.
Их и запускаю. Четвертый, кстати требует подтверждения административных прав. Видимо, из-за того, что счет уже с системой начинает конкурировать за процессор.
В диспетчере задач четко видно, что каждый процесс с gp.exe использует 25% процессорного времени.

-- 17.04.2022, 13:09 --

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

И ведь совершенно несложно было дать мне эти 10-30-50 паттернов и попросить наделать ускорителей под них, и SSE и AVX2, но видимо тысячекратное ускорение никому не интересно (или отсутствующих вирусов боятся, уж не знаю) ... Я ведь давным давно озвучил предложение нагенерить сколько надо (в разумных пределах) любых паттернов и до сих пор его не отзывал. Ну пусть даже не тысячекратное из-за лишь трёх проверяемых чисел, пусть даже стократное (вот даже восстанавливать паттерн из программы и замерять реальное не хочется) ...

В моем представлении, был более перспективен Ваш анализ на тему какие паттерны более удачно ложатся на ускорение.
Однако, если нагеренирить ускорителей ("в разумных пределах") и сделать скрипты для запуска счёта с помощью их (для цепочки 20-48), не потребует настолько много Вашего времени, чтобы это повлияло на анализ - это было бы просто здОрово. Хорошо бы, если будет такая договоренность между Вами и уважаемым VAL.

По поводу запуска счета без ускорителей по скриптам уважаемого VAL.
1. Сохранил текст скриптов в *.gp.
2. Запустилось без особых проблем. Но в одном скрипте была опечатка - пропущена запятая. Была быстро найдена путем сравнения с другими тремя
3. "Урожайность" не высока. Часа за три счета в логах было цепочки "16" и одна "17". На четыре потока.
4. Остро не хватает возможности перенастроить счет с места останова. Уже был сбой питания, пришлось начать сначала.
5. Так же не хватает какого-то прогресс бара. Например, совершенно не понятно, сколько будет считать каждый скрипт "до конца".