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

[Dmitriy40]

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

А где можно посмотреть, что Демис уже проверил и что проверяет в данный момент?

Предпочитаю чтобы на это ответил Yadryara как основной координатор нашей работы с Demis-ом, он же и лог может переслать. Я пока ещё даже не смотрел те логи ... Мне тут полсотни плат спаять надо, срочно ...

-- 07.11.2022, 16:49 --

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

Как обстоят дела с паттернами со следующим по величине шагом 14642258400?

У меня - никак. Я выше сказал что ничего полностью не проверяю. Только что-то сильно выборочно.

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

Я имею в виду проверяли ли паттерны с этим шагом Дмитрий и Евгений?

С шагом 14642258400 я ничего не проверял.

-- 07.11.2022, 16:51 --

EUgeneUS
Запрошенную оценку добавил в прошлое сообщение, посмотрите там.

[EUgeneUS]

Про перекрывающиеся паттерны:

"Overlap-N" - количество перекрывающихся паттернов в группе (к которой относится данный паттерн), если игнорировать уменьшение количества проверяемых чисел.
"Overlap-L" - длина перекрывающегося участка в группе (к которой относится данный паттерн), если игнорировать уменьшение количества проверяемых чисел.
"BAD Overlap" - если не пусто, то перекрытия по полной группе приводят к уменьшению проверяемых чисел. Нужно выкинуть один паттерн из группы.
"tmp" - служебное поле для проверки.
"MAIN" - если "Y", паттерн остался в группе.
"Secandary" - если "Y", паттерн "выкинули" из группы, для сохранения количества проверяемых чисел. Его нужно проверять отдельно.
"Overlap-L2" - длина перекрывающегося участка в группе (к которой относится данный паттерн), если избегать уменьшение количества проверяемых чисел.
"To count" - если "Y", паттерн нужно считать.

Как перекрываются паттерны для линейного перебора с ускорителями - разобрался.
А вот как перекрываются паттерны для квадратичного перебора - нужно изучать отдельно.

[Yadryara]

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

Предпочитаю чтобы на это ответил Yadryara как основной координатор нашей работы с Demis-ом, он же и лог может переслать.

Вообще я попробую Демиса на форум пригласить...

[EUgeneUS]

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

Итого 168 дней.

Скорость AVX2 ускорителя для n=5+1 (5 мест уже есть в паттерне, одно добавляем перебором) можно взять 4e8, всего в 10 раз быстрее, т.е. 116 дней могут сократиться раз в 10, до 12 дней, но 52 дня так и останутся, ну и общий итог сократится до примерно 64 дней. Это для лучшего паттерна с шагом 554400.

С учётом количества таких паттернов, всё равно уходим в годы....

А вот начало лога с запуском наихудшего паттерна в программе Хуго:

001 pcoul(12 11) -f11 -g3 -x9887353188984012120346 -b111
305 11.17^2 2.5^2 3 2^5 7.19^2 2.3^2 5 2^2 3 2 13^2: 368617932 / 505749056 (600.00s)

Как видно, тут происходит подстановка (и перебор) трех квадратов простых. "Трехкратный квадратичный перебор".
Это с одной стороны сильно увеличивает LCM для каждого набора простых. Что уменьшает время счета.
А с другой стороны, три позиции простых перебирать - это долго. ИМХО, всё равно получится десятки дней или около года.

Однако, тут получается уже пять шесть проверяемых чисел, а не три. И ускорители должны бы сильно ускорить, если их прикрутить к "трехкратному квадратичному перебору". (Или наоборот: "трехкратный квадратичный перебор" прикрутить к ускорителям ).

Ещё видим, что квадраты простых расставляются по краям 11-ки. Это убивает сокращение паттернов за счёт перекрытия.

[Yadryara]

EUgeneUS, corporaltermit вроде бы проверяет b111 и b112.

[Dmitriy40]

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

Как видно, тут происходит подстановка (и перебор) трех квадратов простых. "Трехкратный квадратичный перебор".

Да, поэтому и надо бы мне сделать честный рекурсивный перебор, а не ваять на коленке одно- и двух-кратные переборы. Но время ... Вот допаяю платы и сделаю.

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

Это с одной стороны сильно увеличивает LCM для каждого набора простых. Что уменьшает время счета.
А с другой стороны, три позиции простых перебирать - это долго. ИМХО, всё равно получится десятки дней или около года.

Три позиции будут только пока скорость второй низкая и выгоднее запустить третий чем ждать второй.
Другое дело что почему-то каждый квадратичный перебор довольно долгий, у меня вон на тормозном PARI он занимает 5-35 минут, а у Hugo сильно больше (смотреть надо там где простые больше корня из 1e22/LCM, т.е. шаг получается больше предела и проверяется одно начальное число если оно меньше предела и всё).

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

Однако, тут получается уже пять шесть проверяемых чисел, а не три.

Не шесть, Hugo расставляет простые в пустые места, что уменьшает количество перебираемых простых, но не добавляет проверяемых мест.
Примерную скорость ускорителей Вы и сами может из логов извлечь. Я для оценок брал 2e7,4e7,1e8,4e8,1e9 соответственно для 3,4,5,6,7 проверяемых мест, но это для AVX2 версии.

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

И ускорители должны бы сильно ускорить,

Должны. И ускоряют. Примеры были выше. Осталось лишь их корректно прикрутить не к парочке выделенных паттернов, а к любым. И убедиться что прикручено правильно.
А самое правильное было бы переписать PARI компилятор таблиц для ускорителей на C, добавить туда сразу же и код самого ускорителя (и AVX2 и SSE, в зависимости от версии ОС) и выдать Hugo чтобы он встроил в свою программу вместо существующего линейного перебора. Будет и гарантия надёжности и высокая скорость линейного перебора (про квадратичный остаются вопросы почему тормозной PARI обгоняет Hugo, если конечно обгоняет, надо внимательно сверить).

[EUgeneUS]

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

corporaltermit вроде бы проверяет b111

А можно его спросить, про оценки времени расчета до 1е22?

[Huz]

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

Huz
Please tell me, is it possible to run your code so that when it starts with patterns for a chain of length 11, it outputs to the log found continuous chains of length from 8 to 11?

It would not be possible to get that information from my code without substantial changes, and those changes would make it much slower. At each level of the code, it is designed to reject specific chains of length 11 as early and as quickly as possible.

This is why I said before that changing my code to handle overlaps would need a complete rewrite.

-- 07.11.2022, 14:54 --

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

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

Right, the b-number is intended only as a convenient handle to allow a human or a computer to find the actual pattern.

-- 07.11.2022, 14:56 --

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

А разве есть информация какие паттерны проверил сам Hugo?

This is now available on a wiki page at https://github.com/hvds/divrep/wiki/D(12,11).
There are likely more batches that have been completed, but for which I have not yet received and checked the log files.

[EUgeneUS]

Huz в сообщении #1569241 писал(а):

It would not be possible to get that information from my code without substantial changes, and those changes would make it much slower. At each level of the code, it is designed to reject specific chains of length 11 as early and as quickly as possible.

Well, we close the topic with overlapping patterns for your code completely.

Huz в сообщении #1569241 писал(а):

This is now available on a wiki page at https://github.com/hvds/divrep/wiki/D(12,11)
.

It's fine!

I have developed a strategy for choosing patterns for calculation. I'm ready to post it below (in Russian, sorry).
But I want to ask right away, will you mind if I consider your code (for Windows), but I will choose the patterns myself for the calculation? Considering patterns that are already distributed.

I will count using your code until Dmitry implements "recursive quadratic enumeration with accelerators" as he described [url]=https://dxdy.ru/post1569239.html#p1569239]in this post[/url]

[Yadryara]

Ура! Hugo берёт на себя роль координатора. Но только по своим программам.

А Дмитрий мог бы координировать счёт по своим программам. Хотя лучше, чтоб был единый координатор.

Поскольку Правила форума рекомендуют как можно больше инфы постить прямо в теме, цитирую Hugo:

Цитата:

b0-b99: nobody
b100-b199: Natalia
b200-b302: nobody
b303-b510: done
b511-b599: DemIS
b530-b531, b540-b541, b550-b552, b560-b562, b570, b576, b578-b580, b590-b591: done
b600-b649: nobody
b650-b962: done
b963-b1204: nobody
b1205-b1473: done
b1473-b1599: nobody
b1600-b1637: Hugo
b1626-1628: done
b1638-b1835: done
b1836-b2166: nobody
b2167-b2470: done

[EUgeneUS]

С использованием кода Хуго начал считать паттерны:

b2006:
b2007:
b2008:
b2011:
b2012:
b2041:
b2113:
b2157:

Следующая очередь:

b1937:
b1979:
b1982:
b1983:
b1986:
b1988:
b1989:
b2003:

-- 07.11.2022, 19:22 --

Стратегия отбора паттернов:

1. Идем от бОльшего LCM к меньшему.
2. Внутри одного LCM идем от большего количества проверяемых чисел к меньшему.
3. Не берем паттерны, которые можно объединить. Пока оставляем их за спиной. До реализации Дмитрием "рекурсивного квадратичного перебора с ускорителями". А там посмотрим, сколько из них надо будет считать.

[Huz]

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

But I want to ask right away, will you mind if I consider your code (for Windows), but I will choose the patterns myself for the calculation? Considering patterns that are already distributed.

Absolutely fine, just email me which pattern or range of patterns you plan to work on.

Please note that recent improvements in the code make it about 20% faster. (But it should be fine to start with the current build, then stop and recover with a new build when it is available.)

The README file has been updated with instructions on how to build on Windows (using Cygwin), thanks to the very helpful CorporalTermit.

[Dmitriy40]

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

про квадратичный остаются вопросы почему тормозной PARI обгоняет Hugo, если конечно обгоняет, надо внимательно сверить

Вот программа на PARI перебора только больших простых:

v=[45,2,1,12,49,50,363,32,1,18,5]; idx=3;\\Паттерн b1850 и какое место перебирать квадратично
stop=1e22;\\Верхний предел проверки
flog="M12n11_q.txt";\\Куда сохранить найденное

t0=getwalltime(); n1=0; pp=chinese(vector(#v,i,Mod(-i+1,v[i])));
pmax=floor(sqrt(stop/if(v[idx]==1, 13*17, v[idx]*13)));\\До какого числа надо перебрать простые (если место пустое, то перебираем меньше)
pmin=ceil(sqrt(stop/pp.mod));\\С этого числа шаг становится больше stop и перебрать надо лишь одно начальное число
w=strprintf("v=%d, p at v[%d] from %d to %d, check up to %0.3fe18",v,idx,pmin,pmax,stop/1e18); print(w); write(flog,w);
{forprime(p=pmin,pmax,
   L=chinese(pp,Mod(-idx+1,v[idx]*p^2));\\Новый LCM и число
   if(lift(L)>=stop, next);\\Начальные числа больше предела пропускаем
   h=round(lift(L)/32); n1++;\\Число x в 32x и сколько их попало на проверку
   if(!ispseudoprime(h), next);\\Оно должно быть простым
   h*=32;\\Число 32x в цепочке
   if(numdiv(h-2)!=12 || numdiv(h-1)!=12 || numdiv(h+1)!=12 || numdiv(h+2)!=12, next);\\Все 5 чисел вокруг 32x должны быть правильными
   s=vector(15,d,numdiv(h+d-8)); k=#select(x->(x==12),s);
   w=strprintf("%d^2:%d:",p,h-7);
   foreach(s,d, w=strprintf("%s%3d,",w,d));
   w=strprintf("%s  valids=%d, maxlen=%d", w,k,t=0;maxlen=vecmax(vector(#s,d,if(s[d]==12,t++,t=0))));
   if(maxlen>=1, print(w); write(flog,w););
)}
w=strprintf("Checked %d primes, %0.3fs",n1,(getwalltime()-t0)/1e3); print(w); write(flog,w);

Желающие могут поиграться с любыми паттернами и перебором по любому месту в них.
Запуск её с показанными параметрами под PARI x64 записывает в лог (и на экран):

Используется синтаксис Text

v=[45,2,1,12,49,50,363,32,1,18,5], p at v[3] from 15305342 to 6726727939, check up to 10000.000e18
17959243^2:5703312417421106256345: 64, 16, 12, 96, 64, 12, 12, 12, 12, 12, 32, 48,  4, 64,  8,  valids=6, maxlen=5
21193591^2:1857664413781973981145: 48,  8, 24, 96, 48, 12, 12, 12, 12, 12, 32,192,  8, 64,  8,  valids=5, maxlen=5
35372723^2:8636290281640881197145: 32,  4, 24, 12, 24, 12, 12, 12, 12, 12, 16, 24, 32,  8,  4,  valids=6, maxlen=5
Checked 875174 primes, 303.978s

Т.е. хватило 5 минут проверить все большие простые, указано откуда и докуда.
Проверка кандидата на делители довольно простая и не слишком быстрая, но и такой хватает, ведь она выполняется очень редко, меньше миллиона раз для указанных условий, что занимает всего несколько секунд, для проверки можно убрать весь код после n1++ и сравнить время без проверки вообще, только перебора простых с КТО, у меня оказалось 285с, т.е. на такую простую медленную проверку ушло суммарно всего 19с.
Программа Hugo по моей оценке (хотите перепроверьте, это предложенный EUgeneUS паттерн b1850) затратит на такую проверку примерно 2800с (если будет перебирать по 3-у или 9-у месту, если по другому то в коде выше можно указать любое желаемое место). Почему в 9 раз дольше и так не быстрого PARI — это вопрос к Hugo.

Дополнительно, запуск в самом медленном варианте, с idx=2, тоже под PARI x64:

Используется синтаксис Text

v=[45,2,1,12,49,50,363,32,1,18,5], p at v[2] from 15305342 to 19611613513, check up to 10000.000e18
190303199^2:8704204308324237465945: 48, 24, 48, 24,192, 12, 12, 12, 12, 12, 32, 12, 32,  8, 16,  valids=6, maxlen=5
Checked 876056 primes, 922.258s

Даже так, в самом медленном варианте, получается втрое быстрее моей оценки программы Hugo.
Обращаю внимание что кроме изменения времени проверки ещё и нашлись разные цепочки! Кто хочет разложите найденные цепочки и проверьте почему они не нашлись в другом варианте перебора.

-- 07.11.2022, 19:42 --

Huz в сообщении #1569241 писал(а):

This is now available on a wiki page at https://github.com/hvds/divrep/wiki/D(12,11).

That's great!

-- 07.11.2022, 19:45 --

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

А Дмитрий мог бы координировать счёт по своим программам.

Не хочу, с этим прекрасно справится Hugo, ведь теперь есть способ преобразовать мой ID в его номер и обратно (сорри, пока не проверил, но всегда можно руками найти прямо по записи чисел паттерна).

[EUgeneUS]

Huz
The patterns that I took into work and I'm going to take will be announced in this thread, if you don't mind. As in the post above. So that other participants receive this information as quickly as possible.
I will send you the results in the form of log files by e-mail.
I will not rebuild executable files. I think I could figure it out, but it will take time, which I can not allocate for this task.

-- 07.11.2022, 19:50 --

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

(сорри, пока не проверил, но всегда можно руками найти прямо по записи чисел паттерна).

Кстати, биекцию хорошо бы проверить. Делал её в полуручном режиме. Могут быть человеческие ошибки
Кстати, нашел новую формализацию для "New-ID" в части семерок - нужно указывать позицию и степень семерки в позициях от 5 до B. Семёрка там обязательно есть и обязательно в одной позиции.

[Dmitriy40]

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

Кстати, биекцию хорошо бы проверить. Делал её в полуручном режиме. Могут быть человеческие ошибки

Я простите сделаю проще: как будет время напишу программку (на PARI чтобы сюда выложить) конвертации списка Hugo в числа паттерна и поиска его в моём списке и выдачи результата как биекции. Ещё и поэтому не хочется вручную разбираться в огромном файле с кучей лишних полей ...