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

[Yadryara]

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

Если Вам так трудно набрать лишние 3 символа - то да, будем спорить.

Вот именно что лишние. И зачем, главное, набирать эти 3 символа.

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

И между прочим "1" (номер позиции в паттерне) ещё короче чем "27".

Да, когда речь шла о 15-ке, было удобно так говорить: 1-е место, 15-е место. А для более коротких цепочек неудобно. Потому что первое место плавает.

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

А вот набрать коэффициенты паттерна вместо гораздо более короткого его номера у Хуго Вам почему-то не трудно.

Что значит набрать? Моя прога выдала мне паттерн в таком виде. Специально с шагом, для облегчения его идентификации. Так что я не набирал, а скопипастил.

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

Никакого уважения к другим ...

Это с чьей же стороны никакого уважения к другим?

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

В третьих, вся эта бодяга с ограничением $qr$ и $p^2$ затеяна исключительно ради доказательств минимальности,

Вы же сами сказали, чтобы я смирился, что доказать не удастся. Так что не о доказательстве пока речь, а хотя бы об однократной полной проверке всех возможных паттернов.

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

В четвёртых, результаты работы моих программ Хуго так и не принимаются, так что никакого смысла их писать и нет.

А причём тут принимаются результаты Хьюго или нет? Как это никакого смысла?? Что за пессимизм.

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

В итоге речи про мою программу вообще не идёт.

Идёт.

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

Речь идёт про ускорение работы pcoul! Не знаю почему Вы упорно это игнорируете.

Я не игнорю. Но если Асм+Пари намного быстрее, то почему же речь о более быстрых прогах не идёт?

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

13-ку и так докажем с pcoul

Именно докажем? А за какое время?

[EUgeneUS]

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

искать меньшие 14 и 15 перспектив мало (а те что были уже более-менее проверены),

Вот с этим не соглашусь.
а) Я почти уверен, что известные и 14-ка, и 15-ка не являются минимальными.
б) Оптимизма улучшить 14-ку на 2-3 порядка у меня поубавилось. Но улучшить её где-то на порядок считаю вполне вероятным.
в) Улучшение 15-ки на порядок или больше, выглядит уже не столь вероятным.

Это основывается на некоторых, вообще-то умозрительных соображениях.
а) Скорее цепочек с простыми в квадрате большими, чем проверялись, должно быть таки довольно много.
б) Но все таки сильно большие простые в квадрате, видимо, маловероятны.
в) Известная 13-ка скорее всего минимальная, более того, видимо, это какой-то сильный "выброс вниз". Далее анализ тренда показывает, что
- либо известная 15-ка тоже выброс вниз. Тогда можно предположить, что 14-ка лежит на тренде и может быть минимальной.
- либо известная 15-ка близка к тренду, тогда 14-ка или не минимальная, либо сильный выброс вверх. Но выбросы вверх гораздо менее вероятны, чем выбросы вниз.

С другой стороны, ограничения на простые в квадрате сверху, слабо помогут для поиска меньшей 14-ки. ИМХО.

[Yadryara]

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

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

Вот есть паттерн 554954400-4-4:

Не знаю такого, номер по списку Хуго скажите.

b1165

[Dmitriy40]

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

Вот именно что лишние. И зачем, главное, набирать эти 3 символа.

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

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

Вы же сами сказали, чтобы я смирился, что доказать не удастся. Так что не о доказательстве пока речь, а хотя бы об однократной полной проверке всех возможных паттернов.

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

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

Именно докажем? А за какое время?

Докажем в смысле проверки всех вариантов.
За несколько месяцев, смотря кто и как займётся уменьшением -p для pcoul. Ну и проверкой паттернов потом с этим -p.
К примеру сама pcoul с ключом -W умеет уменьшать порог -p со скоростью где-то 10-15e6/c, значит уменьшение порога с 2.2e12 займёт не менее 50 часов, это на каждый паттерн. На оставшиеся к проверке 3000 паттернов это 6000 дней или месяца 4 во все доступные нам всем ~50 потоков. Плюс проверка потом паттернов.
С какой скоростью у Хуго работает sq12 я так не помню, но до 1e9 должна бы за несколько недель уменьшить порог. Зато сразу для всех паттернов, а дальше уже каждый сам себе по -W ещё сильнее.
В общем оценка в месяцы (скажем до года) выглядит разумной.

EUgeneUS
Я скорее имел в виду что для поиска меньшей 14 и 15 вовсе не нужно писать универсальную программу с квадратичными переборами и автоматическим переключением между режимами проверки (которую Антон так ждёт), вполне достаточно руками указать количество квадратичных переборов (они же короткие) для каждого шага паттернов и всего лишь добавить в уже работающий код перебора на PARI расстановку этих простых в квадратах в паттерн и компиляцию на лету. И то и другое вполне отлажено и работает и вообще требует чуть ли не всего десятка строк кода (особенно если не сильно заморачиваться тонкими оптимизациями). Ну и конечно настроенного окружения чтобы асм код компилился. В общем с этим проблем нет.

-- 18.01.2023, 22:24 --

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

а) Скорее цепочек с простыми в квадрате большими, чем проверялись, должно быть таки довольно много.

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

[Yadryara]

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

Чтобы было понятнее, не только Вам, но и другим.

А что тут непонятного-то? 32 в обсуждаемых паттернах всегда стоит на 32-м месте. Не надо быть семи пядей во лбу, чтобы понять какое место 27-е.

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

при том что слово "позиция" в том же контексте встречается и в иных значениях, именно как позиция в векторе паттерна, запутывает.

Ну вот совершенно не запутывает. От слова совсем. Ибо все обсуждаемые паттерны гораздо короче.

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

Вот набирать столько текста ради непонятно спора Вам не лень, а набрать три символа лень ...

А зачем их набирать?

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

И снова поднимать тему математичности "доказательства" всем надоело.

Не знаю, кто Вас уполномочил говорить за всех.

EUgeneUS, вот кстати, снова недостаток pcoul бросается в глаза. Вы с Демисом ищете непрерывную 14-ку. А обычные 14-ки за это время вы нашли? А 13-ки? А 12-ки хотя бы? Или pcoul как не показывала раньше более короткие цепочки, так и не показывает?

Вот если например во время поиска нашлись бы 100 непрерывных 12-к, 20 непрерывных 13-к, 8 обычных 14-к. Тогда да, можно было бы сказать, что непрерывной 14-ке уже пора появиться.

А сейчас что? В потёмках рыщете?

Когда мы раньше искали цепочки, в том числе 14-ки, другие находки здорово подсказывали нам вероятности.

[EUgeneUS]

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

Dmitriy40 в сообщении #1577846

писал(а):
И снова поднимать тему математичности "доказательства" всем надоело.
Не знаю, кто Вас уполномочил говорить за всех.

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

-- 19.01.2023, 09:37 --

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

Вот это соображение выглядит сомнительным

Это соображение основывается на следующих:
1. Пусть у нас есть $k$ мест, куда нужно расставить простые в квадрате. И мы выбираем простые для расстановки из $n$ штук.
Тогда вариантов расстановки простых будет $C^n_k$, что будет расти очень быстро с ростом $n$.
Если будем считать (см. ниже), что каждый вариант расстановки даёт цепочку с одинаковой вероятностью, то окажется, что вероятность, что в случайно выбранной цепочке (например, первой) будет какой-нибудь фиксированный, заданный набор из $k$ простых чисел в квадрате - крайне мала. Просто потому что наборов очень много.

2. С другой стороны, у нас ограничен размер чисел сверху. А это для каждого варианта расстановки приводит к разным вероятностям. Просто потому что чем бОльшие числа в квадратах мы расставляем, тем больше шаг, и тем меньше шагов до ограничения сверху, и тем меньше вероятность успеха.

То есть
а) Вероятность обнаружить в цепочке какое-то заданное простое в квадрате - падает с ростом этого числа (пункт 2 выше).
б) Однако, обнаружить в цепочке ровно $k$ первых (наименьших) простых чисел в квадратах, так же очень мала. (Хотя и наибольшая из среди всех возможных расстановок простых в квадрате).

Что касается экспериментов. Я посчитал первые 20+ цепочек длиной 9. А Хуго нашел какие максимальные простые в квадратах встречаются в этих цепочках. Так вот, насколько помню, для 20 с лишним цепочек максимальное простое в квадрате практически не повторяется. То есть в этих цепочках разные наборы простых чисел в квадратах.

-- 19.01.2023, 09:48 --

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

Я скорее имел в виду что для поиска меньшей 14 и 15 вовсе не нужно писать универсальную программу с квадратичными переборами и автоматическим переключением между режимами проверки (которую Антон так ждёт), вполне достаточно руками указать количество квадратичных переборов (они же короткие) для каждого шага паттернов и всего лишь добавить в уже работающий код перебора на PARI расстановку этих простых в квадратах в паттерн и компиляцию на лету. И то и другое вполне отлажено и работает и вообще требует чуть ли не всего десятка строк кода (особенно если не сильно заморачиваться тонкими оптимизациями). Ну и конечно настроенного окружения чтобы асм код компилился. В общем с этим проблем нет.

1. Можно ли таким способом посчитать, скажем 400 (или хотя бы 150) b-паттернов для 14-к, с ограничением на подставляемые простые в квадратах - до 500?
2. Будет ли это быстрее, чем аналогичные расчеты в pcoul?
3. Можно ли оценить время расчета одного паттерна (в один поток) со следующими параметрами:

а) $LCM = 554954400$ (до расстановки квадратов простых)
б) количество проверяемых мест, после расстановки квадратов простых - 11
в) количество подставляемых квадратов простых - 7.
г) простые в квадратах - все возможные меньше 500
д) расчет до 2e32.

[EUgeneUS]

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

Тогда вариантов расстановки простых будет $C^n_k$, что будет расти очень быстро с ростом $n$.

$C^n_k$ - это количество подмножеств, наборов простых, выбранных для расстановки.
А количество собственно расстановок будет $k! \cdot C^n_k$.

Но на дальнейшие рассуждения это уточнение не влияет.

-- 19.01.2023, 11:23 --

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

EUgeneUS, вот кстати, снова недостаток pcoul бросается в глаза. Вы с Демисом ищете непрерывную 14-ку. А обычные 14-ки за это время вы нашли? А 13-ки? А 12-ки хотя бы? Или pcoul как не показывала раньше более короткие цепочки, так и не показывает?

Это, конечно, доставляет некоторые недобства. Но не критично.
Софт для поиска цепочек выбирается по двум простым критериям:
1. Он должен сущетсвовать.
2. Из существующих, тот который считает быстрее, тот и лучше.

Остальное - вторично.

[Yadryara]

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

1. Пусть у нас есть $k$ мест, куда нужно расставить простые в квадрате. И мы выбираем простые для расстановки из $n$ штук.
Тогда вариантов расстановки простых будет $C^n_k$,

Во-первых, наоборот, большее число($n$) принято ставить вниз, а в биномиальных кэфах вверх:

$$C^k_n = \binom{n}{k}$$

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

А количество собственно расстановок будет $k! \cdot C^n_k$.

Во-вторых, мы это совсем недавно обсуждали:

$$k! \cdot C^k_n \approx n^k$$

[Dmitriy40]

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

Или pcoul как не показывала раньше более короткие цепочки, так и не показывает?

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

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

Когда мы раньше искали цепочки, в том числе 14-ки, другие находки здорово подсказывали нам вероятности.

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

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

абсурд, так как доказать с математической строгостью, что софт работает верно, невозможно.

Извините, но уточню: в принципе возможно, но очень-очень сложно и никто заниматься не собирается. Это уже обсуждали.

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

а) Вероятность обнаружить в цепочке какое-то заданное простое в квадрате - падает с ростом этого числа (пункт 2 выше).

Согласен.

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

б) Однако, обнаружить в цепочке ровно $k$ первых (наименьших) простых чисел в квадратах, так же очень мала. (Хотя и наибольшая из среди всех возможных расстановок простых в квадрате).

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

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

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

Ну, 20+ штук слишком мало для серьёзных выводов. Логи поднимать не стал, сделал по другому: взял 223 известных мне цепочки длиной 13+ (вероятно это не все, просто лежали удобно в одном файлике) и проверил какие из них имеют в своём составе простые больше 50, дающие 12 делителей, нашлись только эти:
1131687019435887932785738910041: 39761^2
3571541827470111796155912172441: 59^2
8465690351577098126087841014041: 61^2
80215613469168729088982885848674841: 101^2
566219997030344639985349043045409945: 53^2
1079136912629672106849725820967421145: 61^2
4400767817056948144578127394427047641: 53^2
4927799318825620554165604225906247641: 59^2
5400788496821420197301806862543165145: 53^2
Почему такой большой разрыв в середине не знаю, цепочки там есть, но все простые в квадратах на местах с 12 делителями меньше 50.
Заметьте, из 223шт только две имеют простые больше 61, и одна из них очевидно статистический выброс, а во вторую 101 расставлялось насильно. И только первые 3 цепочки из этих были найдены без подстановки данных простых в квадратах, т.е. реально нашлись сами, в остальных данные простые расставлялись насильно и их учитывать нельзя. Т.е. сами собой нашлись лишь 3 цепочки из 223, одна из которых очевидно случайный выброс, а две другие имеют практически наименьшие простые. И других простых нет.
Программа проверки:

xx=[1131687019435887932785738910041,80215613469168729088982885848674841];\\Сами добавите интересующие
default(factor_add_primes,1);
foreach(xx,x, removeprimes(addprimes()); print1(x,":"); for(d=1,15, nd=numdiv(x+d-1); if(nd!=12, next); f=factor(x+d-1); k=Vec(select(x->x==2,f[,2],1)); k=select(x->f[x,1]>50,k); foreach(k,g, print1("  ",f[g,1],"^2"););); print;);

-- 19.01.2023, 12:20 --

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

Почему такой большой разрыв в середине не знаю, цепочки там есть, но все простые в квадратах на местах с 12 делителями меньше 50.

А, знаю: все те цепочки искались с расстановкой простых меньше 50 во все возможные места и потому простые больше 50 в квадратах там найтись и не могут. Как не могут найтись и в апрельских логах поиска 15-ки. Всё же надо брать логи именно где простые расставлялись не во все возможные места ...

[Dmitriy40]

Надыбал тут каких-то логов с расстановками не всех простых, очень неравномерно по диапазону, зато много, 83892 цепочки до 2e34, надеюсь простые больше 50 в них не расставлялись, среди них нашлось 197 цепочек с простыми больше 50 в квадратах, дающие 12 делителей:

(Оффтоп)

85510907479449945: 53^2
300912826995067545: 113^2
5269780472979935641: 71^2
15810392809846574041: 167^2
24911498106742992345: 401^2
30685734329682681945: 59^2
31326793814138337945: 131^2
33946738690731835545: 367^2
57143202264015057945: 211^2
62262100050888105945: 67^2
67514473535630606041: 167^2
68544671835440789145: 107^2
76950132416453798041: 103^2
77364970726717017945: 73^2 67^2
77653457664954614041: 1487^2
80397428003971362841: 131^2
89394018701452699545: 331^2
102147123256519396441: 193^2
111710548405911797145: 547^2
113332681647709195545: 101^2
115678591122514367641: 349^2
127209044987013249945: 223^2
127751360532524189145: 167^2
133644379940052282841: 97^2
142085161134093264345: 53^2
143397803606244749145: 223^2
411898994016563313945: 109^2
83421565717100108605051545: 71^2
133363161358630473415344345: 89^2
187166081238497379232780441: 97^2
201894530673067235549505945: 191^2
340102435562189223437726041: 61^2
1606104911571962665170005145: 401^2
8461109457443602869616651545: 71^2
32026065347714054110591085145: 101^2
33313404182322895649534457945: 461^2
39146328504365619361829174041: 89^2
44208257180999518093415159641: 71^2
47462918325178013568537354841: 239^2
109484303717519034873883656345: 461^2
144773817552320064737616810841: 103^2
168120539963088839523789965145: 53^2
206531860242824925604355328345: 139^2
219457410786614544923685071641: 241^2
228230449121636407684769246041: 67^2
233258062403722655707523558041: 9679^2
256116753581935628187702873945: 97^2
273336263972348117430652080345: 151^2
300515880870243047835317544345: 79^2
306726395489188314048941390041: 103^2
310413555230809095822070314841: 61^2
346323512340065098822283217945: 107^2
353652290170350638627196364441: 89^2
359458254213464642665682308441: 163^2
361460718953467117080026188441: 83^2
373253654049385606264101321945: 439^2
390558877475643365067537115545: 53^2
391494138582256998041341199641: 101^2
407342438227636818973005624345: 139^2
428761203470217945100135127641: 233^2
471169543719537587491637836441: 107^2
484592541776331664999869888345: 167^2
485362163353157872373842362841: 67^2
488526248568160698601619011545: 109^2
491758280770710341629884100441: 59^2
538263397715272727689748366041: 53^2
545571663310449357770929027545: 79^2
549598620512568094545805478041: 97^2
599656351733711104003439409945: 61^2
605059414584747616202572602841: 71^2
622271580877608621598153142041: 139^2
658528531544608934367281683545: 73^2
675878426818708183779557947545: 59^2
690901004646812387119986926041: 53^2
696723569389947521476592880345: 181^2
749308448907943447774346001945: 1061^2
780145782493627752531336522841: 137^2
811093176845280613615828108441: 127^2
863664968431674914477420222041: 149^2
865411205511937170239558370841: 89^2
889448568995300646370740887641: 59^2
910947370017531443969214787545: 71^2
917129587918885531951606146841: 109^2
954852953801191478756525150041: 89^2
989370550872934239551441476441: 101^2
994568366896863390419137535641: 109^2
1012125533209604210280936609945: 127^2
1013074797762547660288399828441: 59^2
1051476891597555999145813277145: 433^2
1131687019435887932785738910041: 39761^2
1178778878116208248475522083545: 67^2
1193096235690194768727265271641: 631^2
1193642679204311583010096493145: 67^2
1236132520734766982667226910041: 307^2
1236510882875867306070672369945: 53^2
1263350396341216478213041157145: 59^2
1270465860049890618215295652441: 67^2
1295861537365976793988641379545: 59^2
1372919774552018689588601107545: 151^2
1412850126349033107631163126041: 191^2
1442816347750128796251006119641: 181^2
1497661028388143936492357832345: 67^2
1524183328387315307299008336345: 127^2
1547874121023884282439131068441: 53^2
1562232173452792308559624871641: 439^2
1584642510651649179285023634841: 179^2
1623988139060203671686128967641: 59^2
1651065560911633009493755718041: 71^2
1687414513664182480271645165145: 1181^2
1706594999275341212465281877145: 103^2
1844434475708538582847747017945: 83^2
2733376865673389265928274015641: 733^2
3571541827470111796155912172441: 59^2
3645620175798307988052750090841: 83^2
6266979717912496403865089111641: 73^2
7068420382950996998965377383641: 61^2
7857490650143959203662666898841: 257^2
8465690351577098126087841014041: 61^2
10321331002786362718809436473945: 61^2
10341457405462868154390599093145: 137^2
10580750735373130667686900757145: 67^2
11543334574276541517458392070041: 71^2
12197334647000916497233443192345: 53^2
13390421222540979412089213753945: 113^2
13833906539742534381376845647641: 59^2
14486628337981265172629467660441: 197^2
14809142144730380468083840386841: 151^2
16293438995922813666369240873945: 61^2
16603722584434914395621870798041: 53^2
16903270242911009123151941515545: 113^2
20926737899743344412050298631641: 101^2
21385550602302594426480618341145: 83^2
22395501742461125709444540633945: 67^2
22785008922883685684884570425945: 73^2
23359036875212398665020556734041: 61^2
23397765324824917183421780831641: 67^2
23575401059848425837529986518041: 59^2
23722479864965078543706658123545: 53^2
24637068258016929499949988978841: 127^2
24752271150024578608845872942041: 71^2
26298683138004850554567350309145: 61^2
29889421166890772528918447112345: 61^2
32115340719759976679097517819545: 73^2
33453088155214832377904141371545: 191^2
33510724952522115584135847028441: 53^2
34706151271780804234471755955545: 149^2
35193055719898871519400677961945: 107^2
35727475586623009491256252780441: 97^2
36339256141419825959964373881945: 107^2
37015145057675227688618451398041: 103^2
37082260796049126544514925906841: 79^2
37954366828008316123369322040345: 97^2
38468278464718824645711022444441: 89^2
38892116924480807272492448957145: 101^2
39697768319527528639462621248345: 53^2
39698862719648746569292129891545: 61^2
43355358589717352836523136523545: 71^2
43377584880517955515318209916441: 59^2
43860610709185384787114235753945: 449^2
44577208469691178877893625577945: 73^2
44923537547468574187024967562841: 59^2
46177813019447622200410990065945: 233^2
47630279549689833836257733875545: 97^2
49942784347407798737484828811545: 163^2
50878290752438790936683297222041: 53^2
51332668065933429053024020444441: 53^2
52790839508797264522834381968345: 83^2
53434235116738675352265870215641: 2753^2
53462884872756572727497716698841: 181^2
54232563242162743391098229634841: 67^2
54291914328276425370256869748441: 239^2
54700486368479053666596751603545: 109^2
56620347263296375096538122122841: 239^2
58136827761388960450957999718041: 127^2
58255677490218463234740118099545: 61^2
58372841721761793741200850738841: 479^2
58594972618068706291192305700441: 163^2
58654933509533657810182785931545: 89^2
116695227295458633199714858593945: 89^2
145978264788352403084630733941145: 59^2
167530002338988347437038363201945: 179^2
203515353659923963171504706798041: 53^2
205507092681515684947433429092441: 53^2
223188857574723879620052931109145: 137^2
253341334327131823078731402954841: 107^2
287623428571575330238304709066841: 311^2
896463673766509718510485837650841: 71^2
2245868644912562753650063611954841: 83^2
2712298792848384550647793601610841: 59^2
6012330123251543262990205134460441: 53^2
7309708716530839979294715519724441: 89^2
10173617416495583527128345835823641: 167^2
14738035232155739799682895836583641: 53^2
15302235742827948259636316053814041: 53^2
19652357804405709644803620462158041: 157^2
19866200146399280342126318372592345: 79^2
19881972652581681069486933164783641: 59^2

("Статистика по простым до 200)

53: 20
59: 16
61: 12
67: 12
71: 11
73: 6
79: 4
83: 6
89: 9
97: 7
101: 6
103: 5
107: 6
109: 5
113: 3
127: 5
131: 2
137: 3
139: 3
149: 2
151: 3
157: 1
163: 3
167: 5
179: 2
181: 3
191: 3
193: 1
197: 1

Что видно, что простые встречаются и относительно большие, вплоть до тысяч; видно что повторы таки есть, и немало; что встретились практически все (кроме 173 и 199) простые до 200; однако все исключительно редко.

[EUgeneUS]

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

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

Можно довольно просто сделать грубые оценки отношения вероятностей.
Если $P(p_1)$ - вероятность найти в цепочке квадрат простого числа $p_1 > 13$,
и $P(p_2)$ - вероятность найти в цепочке квадрат простого числа $p_2 > p_1 > 13$,
то $\frac{P(p_1)}{P(p_2)} \approx (\frac{p_1}{p_2})^2$. Эта оценка несколько занижает вероятность встретить бОльшее число.

[Dmitriy40]

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

3. Можно ли оценить время расчета одного паттерна (в один поток) со следующими параметрами:

Можно.
Сделаем предположения: в квадратичных переборах расставляются 90 простых (17...500), время компиляции одного ускорителя 0.2с, время компиляции всех 90 ускорителей 20с, за это время ускоритель может линейно перебрать 20e9 итераций (почему не меньше чуть ниже).
Т.е. если на некотором шаге осталось перебрать менее 20e9 итераций, то следующий квадратичный перебор не запускаем и перебираем линейно.
Если расставить два простых 491 и 499, то останется 6e12 итераций, вероятно можно запустить ещё один квадратичный перебор, значит проверяемых мест будет точно не меньше 9, а при этом ускоритель выдаёт примерно 1e9/с итераций (на AVX). Примем что скорость больше уже не увеличивается (это близко к истине).
Напишем программу оценки времени, не запускающую реальный счёт, а лишь прикидывающую потребное время.

stop=2e32;\\Докуда будем считать
speed=1e9;\\Скорость ускорителей, примем фиксированной, для CP=9+
L0=554594400;\\Начальный LCM
pmax=500;\\Какие простые перебрать
tmin=0.2*(primepi(pmax)-primepi(13));\\Сколько займёт компиляция всех ускорителей в одном квадратичном переборе
{EstimateTime(L)=my(t=0,tl,p);
   tl=0.2+stop/L/speed;\\Время линейного перебора
   if(tl<tmin, return(tl););\\Если квадратичные переборы точно дольше, то и не запускаем
   forprime(p=17,pmax, t+=EstimateTime(L*p^2););\\Оценим время от запуска квадратичного перебора
   return(min(tl,t));\\Вернём минимальное время из квадратичного и линейного переборов
}
print(EstimateTime(L0));

Для указанных параметров (и предположений) она выдаёт время 13.3e6 секунд (считает около минуты). Долго однако.
Уменьшение pmax до 200 уменьшает время до 3.65e6 секунд, тоже немало.
В общем играйтесь.

Погрешность я так думаю должна составлять где-то несколько процентов: не пропускаются одинаковые простые в квадратичных переборах; скорость принята постоянной, хотя для эффективных паттернов с 8-ю и менее проверяемыми местами она будет меньше; не учтено что некоторые паттерны могут провериться почти вдвое быстрее (если компилятор ускорителя обнаружит единственный допустимый остаток по модулю 3 для индекса). Да и вообще неплохо бы конечно еЁ сверить с реальными запусками ... Считайте это грубым приближением.

-- 19.01.2023, 15:02 --

Если в tl=0.2+... константу заменить на 0, то общее время уменьшается вдвое, до 6.5e6 секунд, т.е. это время только счёта ускорителями, без их компиляции. И значит компиляция занимала 13.3e6-6.5e6=6.8e6 секунд или было скомпилено 34млн ускорителей (каждый по полсотни килобайт или суммарно порядка 1.5ТБ). Вот так вот.
Если же в двух местах заменить 0.2 на 0.3 (что ближе к практике), то общее время растёт до 16.6e6 секунд, или 50млн ускорителей - запускается больше квадратичных переборов.
Учёт (пропуск) совпадающих простых уменьшает время с 13.3e6 до 11.2e6.

[EUgeneUS]

Спасибо!

Грустно это. Грубая экстраполяция времения работы pcoul для такого же запуска в те же 13.5 млн. секунд упирается.

[Yadryara]

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

Грустно это.

Всё-таки я спешу поделиться хорошими новостями.

По-прежнему вожусь с конкретным мультипустым паттерном.

Идея в том, чтобы расставлять на пустые места не квадраты простых, а куары. Так вот они очень плохо расставляются. На три места ещё удаётся расставить, а вот на все 4 места пока нет. Это хороший знак.

Хотя счёт продолжается. Может ещё найдётся много вариантов.

-- 20.01.2023, 11:51 --

Один вариант нашёлся.

[EUgeneUS]

Yadryara
Не очень понимаю эту идею.
Вы пытаетесь на все пустые места расставить одинаковые $qr$?

В противном случае, каких-то проблем с расстановкой быть не должно - на каждое место будет свой набор допустимых $qr$.