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

[EUgeneUS]

Dmitriy40
Не помню, писал уже или нет.
Известная 11-ка принадлежит паттерну b1626, (LCM42688800-23186745-7, в Вашей нотации).
Хорошо бы проверить, найдется она "быстрым" способом или нет.

[Dmitriy40]

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

Меня интересует.

Насколько мне известно x32 версии pcoul нет в природе.
Но Вы могли бы помочь остальным проверив моё обоснование допустимости ускорения счёта. Там кроме PARI (или любой другой программы проверки больших чисел на простоту и факторизацию) ничего не требуется.

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

Хорошо бы проверить, найдется она "быстрым" способом или нет.

Разумеется находится (скрин с сокращениями):

T:\M12minimal\Hugo>pcoul -f11 -g3 -x1e22 -b1626 12 11
001 pcoul(12 11) -f11 -g3 -x10000000000000000000000 -b1626 *RT*
202 Candidate 9887353188984012120346 (1004.10s)
367 coul(12, 11): recurse 460156065, walk 461092605, walkc 2248676700 (3108.04s)
200 f(12, 11) = 9887353188984012120346 (3108.04s)

Более того, она разумеется находится и сверхбыстрым способом, который я обосновать для всех паттернов не могу (скрин с сокращениями):

T:\M12minimal\Hugo>pcoul -f11 -g3 -x1e22 -b1626 12 11
001 pcoul(12 11) -f11 -g3 -x10000000000000000000000 -b1626 *RT*
202 Candidate 9887353188984012120346 (8.30s)
367 coul(12, 11): recurse 177252, walk 330853, walkc 8346387 (9.27s)
200 f(12, 11) = 9887353188984012120346 (9.27s)

Впечатлившись 45-кратным ускорением запустил посчитаться один из самых трудных паттернов (LCM=554400, n=3) (скрин с сокращениями):

001 pcoul(12 11) -f11 -g3 -x9887353188984012120346 -b1952 *RT*
305 17^2 2.5^2 3 2^2 7.412273^2 2.3^2 5 2^5 3 2 11.4903^2 (2955.50s)
305 19^2 2.5^2 3 2^2 7.727^2 2.3^2 5 2^5 3 2 11.23^2: 2589 / 88347 (3553.06s)
305 19^2 2.5^2 3 2^2 7.17^2 2.3^2 5 2^5 3 2 11.701^2: 59916 / 173934 (4150.62s)
305 23^2 2.5^2 3 2^2 7.617^2 2.3^2 5 2^5 3 2 11.13^2: 134750 / 262006 (4748.23s)
367 coul(12, 11): recurse 4805692655, walk 4924685015, walkc 23306257650 (35365.99s)

Полученное ускорение неизвестно, его и аналогичные паттерны вроде ещё никто не просчитал до конца. Но если кто-то считает аналогичные паттерны, то можно оценить ускорение снизу, ведь у меня он проверился за менее чем 10ч, значит если аналогичный у кого-то проверяется уже больше 18 дней, то ускорение минимум 45х реализуется (с поправкой на различие компов). Я на 3 недели запускать для проверки не собираюсь.
Специально для Евгения показал переход от 19 к 23 в самом медленном месте, т.е. к этому моменту выполнено не менее 11% всей работы, у него это заняло не менее 5 дней, значит весь счёт будет порядка 40-60 дней, что как раз хорошо стыкуется с расчётными 18 днями для меня (тест выше показал что у меня pcoul почему-то в 2.5 раза быстрее). Так что ускорение порядка 40-50 раз вполне реально не только у меня.

[EUgeneUS]

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

Насколько мне известно x32 версии pcoul нет в природе.

в README написано:

Цитата:

...
It seems likely that on a 32-bit Windows system the same approach will
work (except the "C:\cygwin64" directory will be different).

[Yadryara]

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

Но Вы могли бы помочь остальным проверив моё обоснование допустимости ускорения счёта.

Ок, публикуйте, посмотрю придирчиво.

[Dmitriy40]

Объяснение было в теме выше, программа (в таком виде работать будет сутками, может и больше недели, я запускал по частям с разными qrmin и qrmax и в несколько потоков) (показываю с сокращениями, без вывода любой статистики и прогресса, только вычисления):

stop=1e22; qrmin=13*2; qrmax=10000;\\Границы перебора решений и qr
{WriteLog(p,q,r)=my(h,s,d,w,k,t,x,maxlen);\\Вывод в лог в удобном формате, на работу не влияет
   h=round(p^2*q*r/32)*32-7;
   s=vector(15,d,numdiv(h+d-1)); k=#select(x->(x==12),s);
   w=strprintf("%d*%d*%d^2:%d:",r,q,p,h);
   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))));
   print(w); write("check_small_qr.txt",w);
}
pmax=sqrt(stop/qrmin); rmax=precprime(sqrt(qrmax));\\Перебирать меньшее из двух чисел q и r достаточно лишь до корня из максимума произведения
{forprime(p=0e9,pmax,
   M=stop/p^2; rr=min(rmax,M/13);\\Максимально безопасная граница перебора r
   forprime(r=2,rr,
      q0=max(qrmin/r,r+1); qq=min(qrmax,M)/r;\\Максимально безопасные границы перебора q
      forprime(q=q0,qq,
         h=p^2*q*r; nn=round(h/32); if(h>stop, break, !ispseudoprime(nn), next);\\Получаемая цепочка и начало её проверки
         h=nn*32; x=h%18;\\В h величина 32x
         if(x==2,   if(!ispseudoprime((h-2)/18) || numdiv(h+2)!=12, next);
         , x==16,   if(!ispseudoprime((h+2)/18) || numdiv(h-2)!=12, next);
         ,      next;\\Другие варианты исключены
         );
         if(numdiv(h-1)!=12 || numdiv(h+1)!=12, next);\\Все 4 числа вокруг 32x должны быть правильными
         WriteLog(p,q,r);\\Что-то нашли
      );
   );
)}

Если она не найдёт решений длиной 11 до 1e22 и qr<10000, то это и позволит получать ускорение 40-50 раз на любых паттернах для цепочек длиной 11 без изменения программы Hugo. Ну а если вдруг найдёт, то это будет новая минимальная 11-ка. Ну а если найдёт цепочку длиннее, то это будет вообще сенсация. У меня нашлись лишь 12 цепочек длиной 7, часть которых перечислена в сообщении с объяснением идеи.

-- 18.11.2022, 16:07 --

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

в README написано:

Но не написано что это реально проверено и работает.

-- 18.11.2022, 16:44 --

Если/когда будете считать этой программой, рекомендую сначала поставить qrmax=221 и посчитать все p до 2e10 (нигде указывать не надо, вычислится само), потом же везде указывать qrmin=221 и p будут перебираться уже почти втрое быстрее. И вообще поделить работу на небольшие кусочки по qrmax-qrmin (зависимость времени счёта квадратична от величины этого интервала) по несколько сотен и потом тысячу-две и каждый раз обновлять qrmin, это снизит границу перебора для p, ведь PARI не так уж и быстро их перебирает в forprime.

-- 18.11.2022, 17:00 --

А потом, подняв stop до 1.21e23 и затратив грубо вдесятеро больше времени (т.е. порядка 10 недель в один поток), можно тот же трюк использовать и для аналогичного ускорения доказательства 12-ки.
Вот с 13+ это уже плохо проходит, слишком много придётся перебирать простых. Хотя при реализации на С или асме тоже не за гранью реальности.

[Huz]

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

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

Хорошо бы проверить, найдется она "быстрым" способом или нет.

Разумеется находится (скрин с сокращениями):

T:\M12minimal\Hugo>pcoul -f11 -g3 -x1e22 -b1626 12 11
001 pcoul(12 11) -f11 -g3 -x10000000000000000000000 -b1626 *RT*
202 Candidate 9887353188984012120346 (1004.10s)
367 coul(12, 11): recurse 460156065, walk 461092605, walkc 2248676700 (3108.04s)
200 f(12, 11) = 9887353188984012120346 (3108.04s)

I don't understand what you are showing here - is this a version of pcoul that you have built yourself with modifications? If so, can I see the changes you have made?

[Dmitriy40]

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

I don't understand what you are showing here - is this a version of pcoul that you have built yourself with modifications? If so, can I see the changes you have made?

No, I did not build any version of pcoul, this is running a completely standard windows version 20221113. I just intentionally removed from the screenshot exactly how it was starting - let the interested parties first prove that I do everything correctly, and then we will find out if everything is run correctly and whether the results of this calculation are correct.
Moreover, I will ask you also not to explain publicly how can get such an acceleration of calculations, you can easily understand what I did. I will beat the skeptics and formalists with their own weapons: first the proof that it is possible and only then the profit. Let them follow their own declared principles. Yes, let me be offended. After all, they need it, not me. And they make me look guilty or owed something...

[Yadryara]

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

Объяснение было в теме выше

Ну так я это видел. Придрался только к формулировке. Больше вроде не к чему. Более-менее стандартный приём: предвычисление.

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

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

Какой предел был и докуда снизили в настоящий момент?

[Dmitriy40]

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

Какой предел был и докуда снизили в настоящий момент?

Досчитал до удобной цифры и бросил. Дальше надо слишком много времени (зависимость квадратичная), уже того не стоит на мой взгляд.

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

Больше вроде не к чему. Более-менее стандартный приём: предвычисление.

Есть к чему (не только тогда, вообще): что так вообще можно и никакие решения не пропускаются, что пределы qr указаны верные, что конкретная реализация без ошибок, что действительно не находит решений, что можно так запустить pcoul и она отработает верно (именно в том смысле в каком ограничиваем перебор), может и ещё к чему-то.
И придраться надо было, если кому-то интересно ускорить счёт, и потребовать моих объяснений, логов, текста программы, и так далее. Ничего этого сделано не было. Значит делаю вывод что никому не интересно (ну или пропустили, хотя все заинтересованные лица мои сообщения комментировали, значит видели). Выходит это мне больше всех нужно?! Хотя я вообще не занимаюсь счётом 11-ки программой Hugo, легко проверить у него на вики что мне ни одного паттерна не выделено. Я даже оставшиеся глюки в его программе (правда только под винду) бросил обсуждать, ну и что что у меня глючит, остальным же нормально, а на счёт не влияет.

Yadryara

(По SSE версии с компиляцией на лету)

Некогда её делать и тестировать. У меня последние недели две со временем напряг всё хуже и хуже, и так будет ещё минимум неделю. А всё что делаю - это в "перекурах" или как отдых от работы. Запустить отдельные тесты много времени не занимает. Даже свои ускорители перестал запускать - надо время аккуратно готовить им исходные данные для счёта. Потому фактически версия с однократным квадратичным перебором с компиляцией на лету у меня есть (без разницы AVX2 или SSE, всё отличие в строке запуска компилятора и в паре констант скоростей), а практически я её выдать не могу потому что она под каждый паттерн и каждый комп затачивается вручную. Да и не проверено как оно будет работать в других условиях, не у меня где всё давно настроено. Даже чтобы выбрать те пару констант (на самом деле больше, десяток где-то) надо или провести множество тестов или написать код автоматического их измерения (что сильно предпочтительней). И то и другое это время, которого ну никак нет.

[Yadryara]

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

Полученное ускорение неизвестно, его и аналогичные паттерны вроде ещё никто не просчитал до конца. Но если кто-то считает аналогичные паттерны, то можно оценить ускорение снизу, ведь у меня он проверился за менее чем 10ч, значит если аналогичный у кого-то проверяется уже больше 18 дней,

CorporalTermit вроде бы считает как и Софокл — с 5-го ноября. 3 таких паттерна считает. Докуда дошёл — не знаю.

[EUgeneUS]

Dmitriy40

(Оффтоп)

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

Ничего этого сделано не было.

Вы объявили, что изучаете вопрос ускорения в разы, путем изменения некой константы в коде, и описали идею.
Идея с первого взгляда возражений не вызвала, поэтому комментариев не было. Все ждали результатов.
Результаты превзошли все ожидания, это так. И код pcoul править не нужно, нужный ключик там уже есть, и ускорение не в разы, а более чем на порядок.
Так сразу и возник активный интерес.

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

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

Планирую поразбираться с первыми 1-3 вопросами на выходных, если получится.

А пока сразу вопрос: как исключаются варианты, когда мелкие простые оказываются в степени больше двух, в пятой, например?

-- 18.11.2022, 19:49 --

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

Специально для Евгения показал переход от 19 к 23 в самом медленном месте, т.е. к этому моменту выполнено не менее 11% всей работы, у него это заняло не менее 5 дней
, значит весь счёт будет порядка 40-60 дней

Специально перепроверил, паттерн b1942 (он считается на более медленном компе), переход от 19 к 23 произошел в районе 538 тысяч секунд.
Если это около 11%, то прогноз - 57 дней.
Считается с самого начала на версии pcoul с поправленными итераторами простых.

[Dmitriy40]

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

А пока сразу вопрос: как исключаются варианты, когда мелкие простые оказываются в степени больше двух, в пятой, например?

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

-- 18.11.2022, 20:34 --

Вот кстати и ещё недостаток выбранной Hugo стратегии расстановки простых в квадратах: если мы докажем что qr<222 решений не даёт, то во первых нет разницы куда расставлять простые (на пустые места или уже с простым в первой), во вторых при расстановке в занятые места добавление простого в пятой приводит к проверке ровно одной цепочки вместо запуска перебора (линейного или квадратичного) для полученного паттерна. И эту одну проверку тоже можно исключить вовсе: прямо перебрать что все варианты $\{2,3,5,7,11\}p^5, p<\lceil\sqrt[5]{10^{22}/2}\rceil=21868$ не дают решений, дело нескольких минут секунд. Если такое решение найдётся, это будет фантастическое везение, у меня не нашлось, даже за 5с до 1e35 (т.е. даже для 15-ки).
Но это уже точно потребует изменения кода, от чего Hugo отбрыкивается (и правильно делает), а получаемый выигрыш не сказать чтоб велик, проще оставить как есть. Мне уж точно проще.

-- 18.11.2022, 20:55 --

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

Если такое решение найдётся, это будет фантастическое везение, у меня не нашлось, даже за 5с до 1e35 (т.е. даже для 15-ки).

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

[EUgeneUS]

Dmitriy40
Если правильно понимаю (где неправильно, просьба поправить).

1. Пусть $n_x = p^2 qr \leqslant M$, где $M$ - верхняя граница, до которой нужно проверить.
2. Проверяем все сочетания $qr \leqslant N$, на то, что $n_x$ и $32s$ не составляют цепочки длиной 11 или более. Это потребует перебора больших $p$, но это делается один раз, а не 1044 раза (в каждом "небыстром" паттерне).
3. После чего мы через ключик говорим pcoul, что числа $p > \sqrt{M/N}$ проверять не нужно, "там рыбы нет".
Чем и достигается ускорение.

Но, опять же насколько понимаю, ключик запретит pcoul использовать простые $p > \sqrt{M/N}$ в любых степенях больше $1$ в любых возможных факторизациях. Если так, то мы должны также проверить, что если $p > \sqrt{M/N}$, то невозможны цепочки длиной более 11 (до верхней границы $M$) с факторизациями чисел:
1. $p^5 r$
2. $p^2 q^3$
3. $p^3 q^2$

Вычислительно это будет гораздо меньше, чем для $p^2qr$, но это нужно не забыть сделать.

[Huz]

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

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

I don't understand what you are showing here - is this a version of pcoul that you have built yourself with modifications? If so, can I see the changes you have made?

No, I did not build any version of pcoul, this is running a completely standard windows version 20221113. I just intentionally removed from the screenshot exactly how it was starting - let the interested parties first prove that I do everything correctly, and then we will find out if everything is run correctly and whether the results of this calculation are correct.
Moreover, I will ask you also not to explain publicly how can get such an acceleration of calculations, you can easily understand what I did. I will beat the skeptics and formalists with their own weapons: first the proof that it is possible and only then the profit. Let them follow their own declared principles. Yes, let me be offended. After all, they need it, not me. And they make me look guilty or owed something...

I'm sorry, but I don't understand what you are talking about here. Maybe it is a problem of translation, but this reads as if you want to play guessing games, which does not interest me - I think this problem is already hard enough even if everyone works together.

Цитата:

I even stopped discussing the remaining glitches in his program (albeit only under Windows)

I would still like to hear about any glitches you encounter. (But I have no new ideas for the crash you experience when running with '-a'. If you are able to run it in a debugger, it might be possible to find out more.)

[Dmitriy40]

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

но это делается один раз, а не 1044 раза (в каждом "небыстром" паттерне).

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

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

Чем и достигается ускорение.

Да.

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

Если так, то мы должны также проверить, что если $p > \sqrt{M/N}$, то невозможны цепочки длиной более 11 (до верхней границы $M$) с факторизациями чисел:

По моему не должны, ведь все такие $p$ будут сильно меньше $\sqrt{M/N}$ и останутся в проверке. А программа выше проверяет любые цепочки длиной 10+ (по 15).
Кроме $p^2q^3$, этот вариант я похоже пропустил. Вот и польза от перекрёстной проверки, как идеи, так и реализации. Впрочем таких $q$ мало и их можно допроверить быстро.

-- 18.11.2022, 22:12 --

Допроверил, вообще ничего не нашлось.