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

[Yadryara]

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

Это не слишком корректно, у меня что 1e45, что 1e46, перебираются одинаковое время, 1e47 всего вдвое дольше, и только дальше время растёт линейно

Я выше как раз об этом писал. Осторожнее надо с оценками времени.

Я нашёл ещё одну дырявую 18-ку и 2 дырявые 17-ки. 19-ка пока прячется от меня.

А мы что опять одно и то же считаем? Возьмите хотя бы те расстановки, которые я ещё не пробовал — те, что начинаются на 7, 8 или 9. Или аккуратно отзеркальте M[]. Или может всё-таки получше разобраться с построением паттернов. Их ведь тьма-тьмущая, а мы зачем-то за один и тот же комплект взялись.

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

DemISdx, VAL, а вы будете участвовать в длительном, но перспективном расчете рекорда $D(48,21)$?

Присоединяюсь к вопросу. Вместе весело шагать по просторам

[EUgeneUS]

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

Без этого мутить на пару лет счёт считаю рано.

плюс 100500

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

Проверить паттерн с 4-мя простыми, его реальную скорость и требуемое время по Вашей оценке.

Калькулятор шансов считает количество попыток\итераций. А про время он не знает.
Вроде бы выкладывал для него грубые оценки (на малой статистике)...
Кстати, за сутки посчиталась статистка для паттерна с 3 простыми на 100000 итераций (40000 "кандидатов"). Уточнилось в лучшую сторону, но не намного.
Запустил сбор статистики на 100000 итераций для паттерна на четыре простых. Это на стуки примерно.
Как посчитается - всё расскажу про этот паттерн

[EUgeneUS]

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

А мы что опять одно и то же считаем? Возьмите хотя бы те расстановки, которые я ещё не пробовал — те, что начинаются на 7, 8 или 9

1. Это всё оценочные/пристрелочные запуски.
2. Если делить "фронт работ", то, имхо, удобнее по диапазону с расчетом всех 9! перестановок.

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

Или аккуратно отзеркальте M[]. Или может всё-таки получше разобраться с построением паттернов. Их ведь тьма-тьмущая, а мы зачем-то за один и тот же комплект взялись.

Эффект от "размножения" паттернов посчитан и известен. Выкладывал же табличку.
Тренды там такие:
Увеличение количества паттернов на порядок ведет к
а) уменьшению числа, до которого счтаем, на 1.114 - 1.116 порядка.
б) уменьшению количества проверок (суммарно по всем паттернам) на 0.114 - 0.116 порядка.

-- 15.10.2025, 19:50 --

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

Я нашёл ещё одну дырявую 18-ку и 2 дырявые 17-ки. 19-ка пока прячется от меня.

Вероятность, что дырявая 18 улучшится до дырявой 19: 0.34 - 0.56.
То есть в среднем на 2-3 дырявых 18 будет 1 дырявыя 19.

[Dmitriy40]

Кстати, если не знали, перебор в forperm можно запустить не с начала, а с любой точки (и всегда до конца) - надо ему просто указать вместо #mdkv (или 9) эту самую начальную точку, например forperm([7,1,2,3,4,5,6,8,9],rass, ...).
Если надо оборвать раньше конца, то добавляем if(rass[1..3]==[8,2,7], break).
Правда с этими векторами надо аккуратнее.
Это к вопросу о делении работы, на будущее.
Хотя делить по диапазону удобнее. И не по i, а по n.

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

А мы что опять одно и то же считаем?

А мне было интересно посмотреть именно все расстановки, в том числе сравнить с Вашими, что выгоднее. Да и комп ночью иначе отдыхал бы, так что это "бесплатно" вышло.

[Yadryara]

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

19-ка пока прячется от меня.

Эта красотка легка на помине Ну и не только она нашлась:

Start                                                 Location               Valids
26775093546337571754412744723988589091340703171346    1111111 1111111111 11      19
72909466110460584674297272553362643585315288960146    1111111 1111 11 11111      18
154631495973083613535277148109710834053326309716946   111  11111111111111 1      18
585605360962144936768057576267008749038198122219346   1111111 111 1111111 1      18
606402818949710702556903161178143151197645296548946   11111 1 1111111111 11      18
7463656036994854901626760003614676193212978675835346  111111111  1111 11111      18
21766102877738194392931437163144706992418461424146    11 1111 11111 1 11111      17
88459004668425618097049432547681760440087272643346    111 111 11 11 1111111      17
114784130292194694936375096369864402429171784851346   1111 111  111 1111111      17
178380987012396308863900153677813852686655763044946   1 1111111111111 11  1      17
373798579271459461965814865637583613001311662572946   111111111   111111 11      17
839190911935283032541757641339028804086245959176146   1   11111111111 11111      17
964850637842488519125342139865857065214365420387346   111 1 11 111 11111111      17
970218500041309616393034077124132007375891684899346   111 11111 11111  1111      17
7381053290475287446784877192019650965812213151883346  111 111 1 1 111111111      17

Dmitriy40, спасибо за справку по forperm, припоминаю.

[Dmitriy40]

Хм, забавно, но при заданном диапазоне по n диапазон по i уже не зависит от перебираемого места и от размещённого там квадрата простого, так как n и i связаны коэффициентом a*m (с точностью до сложения/вычитания p1 и ip), который всегда равен lcm(M)*6 и от размещения и перебираемого места не зависит. Это лишь p, перебираемое простое, зависит, потому что только от m, а не от всего a*m, но не i. В общем логично, но сразу фиг поймёшь. И можно вычисление sta и sto (или i1,i2 в программе VAL) вынести из цикла foreach и даже из forperm (если задать lcm(M)).

[DemISdx]

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

DemISdx, VAL, а вы будете участвовать в длительном, но перспективном расчете рекорда $D(48,21)$?

О как!
Прямо сразу с места в карьер!
Думаю поучаствовать можно.

(Оффтоп)

Правда пока, насколько вижу, все очень туманно:

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

2. Будет ли версия для AVX2 или только на SSE? (у всех ведь разношерстное железо)

3. Какое число юнитов планируется (примерно).

4. Сколько времени будет считаться один юнит (примерно).

5. Координация и учет заданий?

6. Именование юнитов.

7. Генерация юнитов.

8. Что-то еще наверняка будет нужно учесть.

Подписываться на три года как-то страшновато, пока, во всяком случае...
Хотя, с другой стороны, а почему нет?

9. Отладка софта, отдельная песня.

Для 19-252 Дмитрий 2,5 года пилил и оттачивал код, прежде чем можно было взяться за расчет.

Это не к тому, что 2,5 долго, а к тому, что момент отладки есть техническая и технологическая необходимость.
Не важно сколько он займет времени.

Поэтому и пишу, что пока все туманно...

[EUgeneUS]

DemISdx

Срок сейчас примерно такой: 60-90 потоко-лет для нахождения цепочки с вероятностью 0.95.
Для вероятности 0.99 - в 1.53 раза больше.

В принципе, выглядит подъемно, если бы потоков больше сотни.... Раз в два ... или в пять
Это для текущий реализации, без ускорителей.

-- 15.10.2025, 21:34 --

Но это, конечно, предварительный вопрос был, чтобы понимать на какое количество потоков можно расчитавать.

[Dmitriy40]

О, а ведь для 3-х проверяемых мест ускорителей не будет 9!, их будет лишь 9*8=72шт, именно столько вариантов расстановки простых в квадратах по проверяемым местам (на одно не ставятся вообще). А непроверяемые ускоритель не колышут (UPD. Это если ему передать готовый p1 и доделать инициализацию, он как раз зависит от всей расстановки).
Для 4-х проверяемых мест ускорителей надо тоже 9*8=72шт так как на двух местах квадраты не расставляются.

-- 15.10.2025, 22:13 --

И кстати, были сделаны 5760 SSE ускорителей (половина зеркальные) по паттернам с 5-ю проверяемыми числами.
Базовый паттерн (без простых 23-59):
[2850, 289, 4, 3, 242, 845, 504, 1, 2, 3, 20, 1, 6, 49, 32, 13365, 2, 1, 2652, 361, 70]
lcm(v)=798553590651032485486124582002569763540418400 (после расстановки всех квадратов простых)
Насколько вижу, было две независимые перестановки простых в квадратах: 23-37 и 41-59. Паттерн при этом один (плюс зеркальный).

Этими ускорителями было проверено до 13e52.
Скорость составила 70 минут на 1e52, из которых 50 минут допроверка в PARI из 5-ти этапов: isprime, factor(,2^18), factor(,2^26), factor() на 3с, factor() на 60с.
Каждый круг (1e52 по всем 5760 ускорителям) генерил 99.9млн кандидатов в PARI. Первые два теста проходили с десяток цепочек. Третий тест прошли 2 цепочки из 93 прошедших первые два (и из примерно 1.3млрд кандидатов от ускорителей).
Лучший найденный valids=10 одна штука, третий тест не прошла.

EUgeneUS
Можете по этим данным оценить докуда надо перебрать n для нахождения M48n21? Оценим время с такими паттернами и ускорителями.

[EUgeneUS]

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

Базовый паттерн (без простых 23-59):
[2850, 289, 4, 3, 242, 845, 504, 1, 2, 3, 20, 1, 6, 49, 32, 13365, 2, 1, 2652, 361, 70]

Если не сложно, просьба: для этого паттерна указать, какое неизвестное число ожидается на каждом месте (p, pq, pqr, pqrs...), и в каких позициях размещаются квадраты простых.
Я могу это все сам посчитать, но вручную
Как посчтиается статистика для паттерна 4 простыми, запущу для этого

[Dmitriy40]

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

Если не сложно, просьба: для этого паттерна указать, какое неизвестное число ожидается на каждом месте (p, pq, pqr, pqrs...), и в каких позициях размещаются квадраты простых.
Я могу это все сам посчитать, но вручную

Не надо вручную:

? v=[2850, 289, 4, 3, 242, 845, 504, 1, 2, 3, 20, 1, 6, 49, 32, 13365, 2, 1, 2652, 361, 70];
? d=[numdiv(t) | t<-v]
%2 = [24, 3, 3, 2, 6, 6, 24, 1, 2, 2, 6, 1, 4, 3, 6, 24, 2, 1, 24, 3, 8]
? p2=[issquarefree(t) | t<-v]\\квадраты простых
%3 = [0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1]
? p2=[t==8||t==4||t==2||t==1 | t<-d]\\или так квадраты
%3 = [0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1]
? p=[t==24||t==8 | t<-d]
%5 = [1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1]
? pq=[t==12||t==4 | t<-d]
%6 = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0]
? pqr=[t==6||t==2 | t<-d]
%7 = [0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0]
? pqrs=[t==3||t==1 | t<-d]
%8 = [0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0]

Если надо в виде индексов, то:

? p2=Vec(select(t->(t==8||t==4||t==2||t==1),d,1))
%9 = [4, 8, 9, 10, 12, 13, 17, 18, 21]

Остальные аналогично, меняется только условие.

[Dmitriy40]

Нашёл у себя исходник M48n21p4 и M48n21p5 (с паттернами, с 4 и 5 проверяемыми местами соответственно), из него по быстрому сварганил M48n21p3 и заценил скорость перебора. Паттерн:
v=[ 3698, 3971, 12, 49, 50, 5043, 362024, 529, 18, 4805, 28, 4107, 242, 841, 480, 289, 4418, 63, 4, 845, 320226 ]
1e8 штук i перебираются за 10с, из которых 8с в PARI. И никак 8с уменьшаться не хотят, уже даже всю проверку взял из последней проги, всё равно, фильтрация улучшается, а скорость практически нет, ispseudoprime слишком тормозят на таких числах, а без них резко ухудшается фильтрация и резко тормозят уже factor/numdiv.
В пространстве n=i*lcm(v)=i*2.9576e43 скорость соответственно 3e50/c.
Сколько проверок не спрашивайте, ускоритель тихарится, в PARI возвращается примерно 0.435млн i из 100млн.
Для сравнения скорость прошлой ночью на PARI составила 5e48/10.5ч*9!=4.8e49/c, практически в 6 раз меньше.
Вот примерно такое ускорение дают ускорители для трех проверяемых мест. Слишком мало мест, фильтрация плоха, много кандидатов остаётся, 80% работы остаётся PARI.
Тут даже бесполезно ускоритель под AVX делать (проверенные SSE), выигрыш не превысит считанных процентов общей скорости.

В тех же условиях вариант M48n21p4 (4 проверяемых места) работает вдвое быстрее, 4.7с (3.5с в PARI) на 1e8 штук i. Вываливается около 0.174млн i из 100млн. lcm(v) тот же. Соответственно скорость 6.3e50/c. Паттерн:
v=[ 54910, 529, 12, 1573, 2738, 75, 194936, 841, 18, 961, 20, 5043, 3698, 15463, 1056, 14045, 338, 153, 4, 361, 1470 ]

В тех же условиях вариант M48n21p5 (5 проверяемых мест) работает ещё быстрее, 4.6с (2.9с в PARI) на 1e8 штук i. Вываливается около 0.138млн i из 100млн. Но lcm(v) больше, 7.9855359e44. Соответственно скорость 1.7e52/c. Паттерн:
v=[ 2850, 289, 4, 5043, 242, 845, 504, 529, 3698, 6627, 20, 841, 5766, 49, 32, 13365, 5618, 1369, 2652, 361, 243670 ]

[EUgeneUS]

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

Не надо вручную:

Спасибо!

-- 16.10.2025, 05:17 --



На картинке график $b_1$ от места для паттерна с 3p. По статистике на 100000 итераций (около 40000 "кандидатов")
$b_1$ - коэффициент во сколько раз больше вероятность найти простое с паттерном, чем без паттерна.
В теории:
а) не должен зависеть от места.
б) рассчитывается аналитически.

Желтая линия - теоретическое значение.
Красная - усредненное по номеру места.
Синяя - данные по каждому месту.

Невооруженным глазом видно, что несколько съехало вниз, из-за выбросов на некоторых чётных местах (2, 4, 6, 12, 18, 20).

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

-- 16.10.2025, 05:37 --

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

В тех же условиях вариант M48n21p4 (4 проверяемых места) работает вдвое быстрее, 4.7с (3.5с в PARI) на 1e8 штук i. Вываливается около 0.174млн i из 100млн. lcm(v) тот же. Соответственно скорость 6.3e50/c. Паттерн:
v=[ 54910, 529, 12, 1573, 2738, 75, 194936, 841, 18, 961, 20, 5043, 3698, 15463, 1056, 14045, 338, 153, 4, 361, 1470 ]

Пока на малой статистике: количество проверок $i_m$ и число, до куда надо считать ($N$) - больше в 5.3 - 5.4 раза, чем для 3p.

[Yadryara]

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

Для сравнения скорость прошлой ночью на PARI составила 5e48/10.5ч*9!=4.8e49/c, практически в 6 раз меньше.
Вот примерно такое ускорение дают ускорители для трех проверяемых мест.

Вот именно об этом я и писал недавно:

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

Эффективны. И Дмитрий об этом прямо писал в теме. Для 3-х одиночных простых — в 6 раз быстрее.

То есть Вы это сравнение уже делали и я с тех пор запомнил.

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

Могу выслать 9-й комплект Вам и 8-й — Владимиру. Посчитаете, заодно потестите. Это для одного потока на PARI. Дырявая 19-ка нашлась у меня в 5-м комплекте. Моё время счёта — 38 часов. Находки пишутся в файл "9-1e50.txt". Их примерно 120-140 штук, то есть строчек.

Если 21-ка найдётся, счёт будет остановлен с YES-ом.

[VAL]

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

DemISdx, VAL, а вы будете участвовать в длительном, но перспективном расчете рекорда $D(48,21)$?

Дважды пытался ответить.
Оба раза ответ загадочным образом исчез

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