Симметричные кортежи из последовательных простых чисел

[Yadryara]

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

Я прохожу не по простым, а лишь по допустимым начальным числам цепочки, их 552960/23# (/223e6), потому и быстрее.

Так я тоже. Причём у меня 29#. Как его назвать, шаг? У меня для 7-к отдельная прога. Вот она:

(Оффтоп)

allocatemem(2^27);
{print();v=[0,6,30,36,42,66,72];
kp=0;k3=0;k5=0;k7=0;k9=0;
start=358705*10^11;fin=start+100*10^9;
w=2*3*5*7*11*13*17*19*23*29;

ko=1;m=vector(29,i,[]);
forprime(p=2,#m, m[p]=setminus(vector(p,i,i-1),Set(-v%p));
printf("%d: x %d: %d\n",p,#m[p],m[p]);
ko=ko*#m[p]);o=vector(ko);print();

print(w);print();
print(ko);

x0=Mod(1,2);
foreach(m[29],m29,
foreach(m[23],m23,
foreach(m[19],m19,
foreach(m[17],m17,
foreach(m[13],m13,
foreach(m[11],m11,
foreach(m[7],m7,
foreach(m[5],m5,
foreach(m[3],m3,
x=lift(chinese([x0,Mod(m29,29),Mod(m23,23),Mod(m19,19),Mod(m17,17),Mod(m13,13),Mod(m11,11),Mod(m7,7),Mod(m5,5),Mod(m3,3)]));
no++;o[no]=x)))))))));

print(no);print();

for(y=floor(start/w), floor(fin/w)+1,
for(i=1,ko,
kan=y*w+o[i];kkan++;

if(ispseudoprime(kan)
&& nextprime(kan+1)-kan==v[2]
&& nextprime(kan+v[2]+1)-kan==v[3]
&& nextprime(kan+v[3]+1)-kan==v[4]
&& nextprime(kan+v[4]+1)-kan==v[5]
&& nextprime(kan+v[5]+1)-kan==v[6]
&& nextprime(kan+v[6]+1)-kan==v[7], 

di=nextprime(kan+v[6]+1)-kan;

if(kan>=start && kan<=fin,
k7++;
print1(k7,"   ");
forprime(p=kan,kan+v[1],print1(p,"   "));
print(di));

)));
print();print(kkan);print();
print(k7);
\\print();
}quit;

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

вон на тройки и пятёрки посмотрите.

По тройкам согласие просто отличное, а с 5-ками что-то не то:

У меня-то 222шт/1e9 против Ваших 233шт/1e9.

[Dmitriy40]

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

Да те же минут 40. Сейчас запущу.

Насчитала 1339шт. Одна где-то потерялась. Да и плевать.

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

У меня-то 222шт/1e9 против Ваших 233шт/1e9.

Запустил с меньшим пропуском, через 20м получил величину 219.43шт/1e9. Говорю ж, флуктуации.

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

Так я тоже. Причём у меня 29#.

У меня 29# работает лишь чуть быстрее 23#: с пропуском 10:1 первая 190с (плюс 39с подготовки таблицы), вторая 220с (плюс 1.6с подготовки таблицы). Обычно мне лень ждать 40с подготовки.
Но gp32 вместо 220с работает 325с.
Плюс я перед первой ispseudoprime проверяю ещё несколько десятков простых модулей начального числа x командой for(j=npr+1,#pr, if(!setsearch(m[j],x%pr[j]), next(2)); );, это ускоряет с 30с до 21с.
В сумме это даёт выигрыш 1.82 раза, от 8ч составит расчётные 4.4ч, почему не 0.7ч я не знаю, может у Вас ноут в режиме энергосбережения и скинул частоту до 0.5ГГц? Настолько сильных причин торможения в программе не вижу.

[Yadryara]

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

В сумме это даёт выигрыш 1.82 раза, от 8ч составит расчётные 4.4ч, почему не 0.7ч я не знаю, может у Вас ноут в режиме энергосбережения и скинул частоту до 0.5ГГц?

Ноут мне сын давно сломал.
Вроде бы я знаю почему так медленно. У меня же до сих пор 32 разряда. И я сравнительно недавно заметил что в задачах с простыми числами при переходе через 4,3 млрд(как раз $2^{32}$) комп замедляется в разы. Хотя тема не об этом.

Касаемо главной задачи. Всё-таки то, что кэфы такие большие даже внизу, это плохие новости для тех кто ищет 19-252. Вы-то продолжаете искать?

[Dmitriy40]

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

Вроде бы я знаю почему так медленно. У меня же до сих пор 32 разряда.

Это я выше проверил, замедление примерно 1.5 раза.

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

в задачах с простыми числами при переходе через 4,3 млрд(как раз $2^{32}$) комп замедляется в разы.

Да, а для x64 граница резкого замедления $2^{64}$, это связано с тестом простоты по малой теореме Ферма (точнее его развития BPSW, где малая теорема Ферма отрабатывает первой в составе одной итерации теста Миллера-Рабина), реализуемым как вычисление возведения в степень по модулю проверяемого числа. Пока проверяемое число влезает в регистр есть аппаратная команда взятия остатка (деления с остатком), как только перестаёт влезать - надо деление выполнять программно, что заметно медленнее.

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

Вы-то продолжаете искать?

Да, считается где-то около 83e22. Ничего особо интересного не было, вот и не стал рассказывать про каждый 1e23 (чаще раза в месяц), думаю по итогам года отчитаюсь, видимо по границе 85e22.

[Yadryara]

Посчитал пока самые короткие цепочки. Первые три строчки обсчитаны полностью.

Условие позеленения пришлось ужесточить ещё на порядок — до 10 тысяч. Иначе флуктуации, как можно видеть из таблицы, мешают разглядеть закономерности.

$\tikz[scale=.08]{ \fill[green!90!blue!50] (80,280) rectangle (100,190); \fill[green!90!blue!50] (100,270) rectangle (120,250); \fill[green!90!blue!50] (100,240) rectangle (120,230); \draw[step=20cm] (0,190) grid +(120,100); \draw (0,290) -- (120,290); \draw (0,270) -- (120,270); \draw (0,250) -- (120,250); \draw (0,230) -- (120,230); \draw (0,210) -- (120,210); \draw (0,190) -- (120,190); \node at (10,275){$10^9$}; \node at (10,265){$10^{10}$}; \node at (10,255){$10^{11}$}; \node at (10,245){$\approx 10^{12}$}; \node at (10,235){$\approx 10^{13}$}; \node at (10,225){$\approx 10^{14}$}; \node at (10,215){$\approx 10^{15}$}; \node at (10,205){$\approx 10^{16}$}; \node at (10,195){$\approx 10^{17}$}; \node at (30,285){\text{1}}; \node at (30,275){\text{50847534}}; \node at (30,265){\text{45505251}}; \node at (30,255){\text{41180548}}; \node at (30,245){\text{37607933}}; \node at (30,235){\text{34606538}}; \node at (30,225){\text{32050233}}; \node at (30,215){\text{29844965}}; \node at (30,205){\text{27921439}}; \node at (30,195){\text{26235078}}; \node at (50,285){\text{3}}; \node at (50,275){\text{595279}}; \node at (50,265){\text{438310}}; \node at (50,255){\text{331661}}; \node at (50,245){\text{255863}}; \node at (50,235){\text{202190}}; \node at (50,225){\text{162539}}; \node at (50,215){\text{132488}}; \node at (50,205){\text{109620}}; \node at (50,195){\text{91699}}; \node at (70,285){\text{5}}; \node at (70,275){\text{1501}}; \node at (70,265){\text{1154}}; \node at (70,255){\text{865.4}}; \node at (70,245){\text{641.5}}; \node at (70,235){\text{492.5}}; \node at (70,225){\text{376.4}}; \node at (70,215){\text{296.1}}; \node at (70,205){\text{221.7}}; \node at (70,195){\text{171.5}}; \node at (90,285){\text{C3}}; \node at (90,275){\text{85.4}}; \node at (90,265){\text{104}}; \node at (90,255){\text{124}}; \node at (90,245){\text{147}}; \node at (90,235){\text{171}}; \node at (90,225){\text{197}}; \node at (90,215){\text{225}}; \node at (90,205){\text{255}}; \node at (90,195){\text{286}}; \node at (110,285){\text{C5}}; \node at (110,275){\text{397}}; \node at (110,265){\text{380}}; \node at (110,255){\text{383}}; \node at (110,245){\text{399}}; \node at (110,235){\text{411}}; \node at (110,225){\text{432}}; \node at (110,215){\text{447}}; \node at (110,205){\text{494}}; \node at (110,195){\text{535}};}$

[Dmitriy40]

Так какова же оценка для КПППЧ19d252?

[Yadryara]

До этой оценки ещё весьма далеко. Но вроде никто не торопит. Постепенно буду пытаться к ней подходить. Если кто желает помочь со счётом — милости прошу.

[Dmitriy40]

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

Кстати оценка 8e23 хорошо согласуется с оценкой по известным 13-15-17-кам, там формула получается $x(n)=0.0016\cdot 25.2443^n, x(19)=7\cdot10^{23}$. Может к концу года и найдётся ...

Не нашлась. Не нашлось даже ни одной цепочки с valids=19 (не только решения, но и даже с лишними простыми в интервале 0-252).

Покажу итоги года, счёт был с апреля 2023. Досчиталось до 85e22, плюс отдельные мелкие кусочки. Только самое интересное, часть была показана выше (в момент находок), часть будет дублирована так как подпадает под несколько критериев отбора.
С всего одной ошибкой (одно из нужных простых оказалось составным, помечено плюсом):
20502399070486534394861: [ 0, 6, 12, 30, 42, 72, 90, 96, 120, 126, 132, 156, 162, 180, 210, 222,+240, 246, 252], len=18, valids=18
154787380396512840656501: [ +0, 6, 12, 30, 42, 72, 90, 96, 120, 126, 132, 156, 162, 180, 210, 222, 240, 246, 252], len=18, valids=18
152280801556172495686561: [ 0, 6, 12, 30, +42, 72, 90, 96, 120, 126, 132, 156, 162, 180, 210, 222, 240, 246, 252], len=18, valids=18
163238587802201963204821: [ 0, +6, 12, 30, 42, 72, 90, 96, 120, 126, 132, 156, 162, 180, 210, 222, 240, 246, 252], len=18, valids=18
327480747328610662288037: [ 0, 6, 12, 30, +42, 72, 90, 96, 120, 126, 132, 156, 162, 180, 210, 222, 240, 246, 252], len=18, valids=18
434510678411396023322707: [ 0, 6, 12, 30, 42, +72, 90, 96, 120, 126, 132, 156, 162, 180, 210, 222, 240, 246, 252], len=18, valids=18
901985248981556228168761: [ 0, 6, 12, 30, 42, 72, 90, 96, 120, 126, 132, 156, 162, 180, 210, 222, 240, 246,+252], len=18, valids=18
Всего с одной дыркой (простым не соответствующим паттерну, выделю жирным):
154787380396512840656501:[-28, 6, 12, 30, 42, 72, 90, 96, 120, 126, 132, 156, 162, 180, 210, 222, 240, 246, 252], valids=18
548934853673670454695071:[0, 6, 12, 30, 42, 72, 92, 96, 120, 126, 132, 156, 162, 180, 210, 222, 240, 246, 252], valids=18
901985248981556228168761:[0, 6, 12, 30, 42, 72, 90, 96, 120, 126, 132, 156, 162, 180, 210, 222, 240, 246, 418], valids=18
С центральной 17-кой:
154787380396512840656501: [ +0, 6, 12, 30, 42, 72, 90, 96, 120, 126, 132, 156, 162, 180, 210, 222, 240, 246, 252], len=18, valids=18
901985248981556228168761: [ 0, 6, 12, 30, 42, 72, 90, 96, 120, 126, 132, 156, 162, 180, 210, 222, 240, 246,+252], len=18, valids=18
Самая плотная (больше всего простых влезло в интервал 0-252):
131801863072799186567381: [ 0, 6, 12, -20, -26, 30, -32, 42, -56, +72, 90, 96, -98,-102, 120,+126, 132, 156,-158, 162,-176, 180,-200, 210,-212, 222,-230, 240, 246, 252], len=28, valids=17

Не рекорды, но статистика.
Всего в интервале 0-85e22 проверено более 150e15шт кандидатов, из них для почти 2.4млн.шт в интервале 0-252 влезло не менее 17 простых и попали в логи (размер которых превысил 436МБ). Из них в более 73тыс.шт влезло больше 19 простых и почти 189тыс.шт ровно 19 простых.
С valids=18 (столько простых в интервале 0-252 совпадают с паттерном) найдено 56шт (включая и показанные выше). С valids=17 найдено чуть более тысячи штук.
Центральных 15-ек найдено 2шт, центральных 13-ек 26шт, центральных 11-ок 81шт, центральных 9-ок 2005шт.

[Yadryara]

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

Не нашлась.

Найдётся.

Зато у Вас темп счёта сильно вырос:

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

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

Тогда 19-ки должны быть одна на 8e23 ... Печально.

Сколько месяцев счёта до туда?

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

Месяцев 8-10.

А дошли за 5 с лишним месяцев.

Что касается найденных Вами цепочек и прогнозов. Не хочется отделываться прикидками по верхам. Продолжаю пока смотреть самые короткие цепочки.

И пока удалось аппроксимировать только тройки. Показатель степени соотв. полинома 1.92. Думаю, что на самом деле конечно квадрат, то есть кэфы при тройках (С3) аппроксимируются параболой. $C3(0-1\cdot10^{25}) \approx 610$
Другими словами, на каждые 610 простых чисел приходится лишь одна центральная 3-ка. А на каждые 700-800 центральных 3-к — лишь одна центральная 5-ка.

Я написал 700-800 по той простой причине, что уже с С5 всё-таки происходит расколбас и непонятно, что там за формула. Надо ещё больше статистики собрать. Десять тысяч 5-к всё равно мало.

А что у нас gris молчит... Есть ли соображения по 19-252 ?

[Dmitriy40]

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

Зато у Вас темп счёта сильно вырос:

Так я как раз спустя неделю от той оценки ускорил программу почти в полтора раза (ценой памяти, больше в 1.7 раза) переносом части проверок из дельфи в асм. Но только для паттернов длиной 19, общий случай делать поленился (до сих пор).

[ice00]

hi,

just to mention that another k-tuple competition is being done:

https://primesmagicgames.altervista.org/wp/primes-k-tuple-2/

Maybe some of you could be interested in participating (if you have question you can wrote in comments of that page)

Thanks

[Yadryara]

ice00

I’m still used to discussing things here. Why move somewhere?

The method you started counting with is very ineffective.

For example, to search for 19-252, the period 19# is taken. But why??

It has been discussed here many times that you need to take at least 37#. And this alone can give a 40-fold acceleration. See table.

$\frac{23}6 \frac{29}{12} \frac{31}{12} \frac{37}{20} \approx 44$

And the corresponding programs in PARI were carried out here.
​
------------------------------------------------------------------

Мне всё-таки привычно здесь обсуждать. Зачем куда-то переезжать.

Тот алгоритм, по которому Вы начали считать, весьма малоэффективен.

Например, для поиска 19-252 берётся период 19#. Но зачем??

Здесь многократно обсуждалось, что надо брать минимум 37#. И уже одно это может дать 40-кратное ускорение. См. таблицу.

$\frac{23}6 \frac{29}{12} \frac{31}{12} \frac{37}{20} \approx 44$

И соответствующие программы на PARI здесь приводились.

[ice00]

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

ice00

I’m still used to discussing things here. Why move somewhere?

No problems, the suggestion was that maybe the question/answer can help other people that read the competition page.

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

ice00
The method you started counting with is very ineffective.

For example, to search for 19-252, the period 19# is taken. But why??

It has been discussed here many times that you need to take at least 37#. And this alone can give a 40-fold acceleration. See table.

$\frac{23}6 \frac{29}{12} \frac{31}{12} \frac{37}{20} \approx 44$

And the corresponding programs in PARI were carried out here.

Sorry for that but I'm not aware of all the (past) discussions in details.

However each contestant uses the algorithms and software he sees fit.

[Yadryara]

ice00 в сообщении #1625567 писал(а):

Sorry for that but I'm not aware of all the (past) discussions in details.

And don't want to go into details?

We are simply talking about the fact that if we count in such a slow way, then it is not clear what will happen first - the decay of a proton or 19-252 will be found.

And no one keeps secret the way to count millions of balances on the fly. Just recently I brought a program where this was done. It works even without the usual sorting of balances in ascending order.
​
-----------------------------------------------------------------------------------------

И не желаете вникать в детали?

Просто речь идёт о том, что если считать столь медленным способом, то непонятно что случится раньше — распад протона или 19-252 найдётся.

И ведь никто не держит в секрете способ подсчёта миллионов остатков на лету. Совсем недавно приводил прогу, где это делалось. Работает даже без обычной сортировки остатков по возрастанию.

[Dmitriy40]

А я показывал как добавлением одной строчки можно ускорить программу почти впятеро только за счёт замены части проверок ispseudoprime на setsearch от частного, что оказывается намного быстрее. Так можно (более-менее) ускорить фактически любую программу проверки по паттернам на PARI.

Кстати, просто для информации: некоторые задачи в конкурсе требуют доказательства минимальности найденных решений и в худшем случае (если меньше ничего не найдётся) придётся повторить все вычисления, которые заняли более двух (скорее ближе к трём) миллионов машинных часов (кранчерами в боинке)!
А насчёт приза ... Только у меня и только в задаче #3 поиска 19-252 уже потрачена практически вся сумма приза только на электричество. Сколько сожгли кранчеры можно прикинуть отдельно (2млн.ч по пусть 50Вт по 5р/кВтч выйдет полмиллиона рублей! вот такова цена "бесплатных" вычислений).