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

[EUgeneUS]

vicvolf в сообщении #1708245 писал(а):

Поскольку в статистике указано, что найдено 1 кандидат с Valids=3, это означает, что как минимум одна из гарантированных позиций не прошла?

Почему?
Valids=3 - это две гарантированных и ещё одна.

[Yadryara]

vicvolf в сообщении #1708245 писал(а):

Тогда Valids должен быть как минимум 2.

Ну да, ни одного меньше 2-х и нету.

vicvolf в сообщении #1708245 писал(а):

Возможно, что в статистику включены кандидаты, которые не прошли полную проверку?

Конечно они не прошли полную проверку. Иначе была бы скукота, печатались бы только искомые цепочки с Valids=19.

По-моему у Хьюго программа так до сих пор и работает, как и три года назад. Прогресс и паттерны выводит, а приближения — фиг. Только искомый результат.

Между тем я вчера изменил подход и считал по $576\cdot8=4608$ комплектов паттернов, но гораздо выше. Статистика будет позже.

Теперь в топе уже только дро:

Start                                              Location           Valids
8364169077803931886262150138136203893351571        11111111 1111111111    18  An
11216590251510551171384848791827346209344411       111111111111111 111    18  An
12470239760851875734263909780258237339024411       11111111111 1111111    18  An
279867836228959400853234290858645426540921171      111111111 111111111    18  An
364032173546127247181260920124922317318241171      11111111111 1111111    18  An
447297881236843138579169819124405559017702811      1 11111111111111111    18  An
483417290466547919966198285087691589283015644      111111111111111111     18  Hu
488900003598703704335810037459507226590256411      111111111111111111     18  Vl
178346408411285248655809093745448085246706354011   111111111111111111     18  Vl

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

[Huz]

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

По-моему у Хьюго программа так до сих пор и работает, как и три года назад. Прогресс и паттерны выводит, а приближения — фиг. Только искомый результат.

My current code shows stats in the logs of how many candidates were rejected after 0, 1, ... k-1 elements were accepted, so you can get at least some sense of the probability of finding a complete sequence. It does not show values for near-misses though.

For example, here is the data from the last log line in a long-running process working on D(48,10):

  [1493833732241 324444877876 76749038219 12503642693 1590117318 139770912 7418567 238319 3971 24]

This shows that 1.5e12 candidates were rejected after 0 elements had been accepted, and 24 were rejected after 9 elements had been accepted (about 1 in 167 of those with at least 8 elements accepted).

I have several other improvements too, so I plan to ask Demis to make a fresh Windows build in a few days after I've done some more checks.

[Yadryara]

Good.

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

were rejected after 0, 1, ... k-1 elements were accepted,

Does this correspond to valids, a more familiar term. Does this mean any numbers in a 10-wide pattern strip that have 48 divisors, or only those that are consecutive?

[Dmitriy40]

Насколько помню у него порядок проверки чисел в кортеже может меняться при изменении паттерна (смены расстановки).
Так что это и не valids (потому что проверяется не весь кортеж, а лишь до первого несовпадения), и не обязательно последовательные места. Это сколько мест проверено до первого несовпадения. Можно сказать что valids точно не меньше вот этих величин.
Вообще точное вычисление valids (после первого несовпадения) довольно затратно, одна единственная factor/numdiv может затормозить проверку точно неподходящего кортежа на секунды (если там pq вместо более длинного варианта и оба делители немаленькие), а ведь ненужных уже проверок может быть и с десяток. Потому например для тестов скорости брал интервал где все предпроверки не проходил ни один кортеж, до полной факторизации дело не доходило.

[Yadryara]

$\tikz[scale=1.5, transform shape, font=\fontsize{11}\selectfont, black!70!]{ \node at (4.79,10)[shading=ball,ball color=green!70!violet!100!, white] {\color{yellow}\Huge\textbf{D(24, 19)}} }$

$\tikz[scale=.67, transform shape, font=\fontsize{11}\selectfont, black!70!]{ \node at (4.79,10)[shading=ball,ball color=red!70!violet!100!, white] {\color{yellow}\Huge\textbf{18852797512788010920723387591494690548010011}} }$

[Dmitriy40]

Yadryara
Поздравляю!
Вот что правильная организация вычислений даёт.

[EUgeneUS]

Yadryara
Поздравляю.

[Yadryara]

Спасибо, друзья.

Теперь стату ещё досчитаю, дополню и позже покажу. С полным приводом (с обсчётом 4608 паттернов) поднимался вот докуда:

24-19   2-10-7-4!x4!    2304     70 e43   Done
24-19   2-10-7-4!x4!z   2304     70 e43   Done

И, не увидев явного преимущества этого метода, и понимая что дальнейший подъём заметно ухудшит показатели, решил вновь спуститься вниз и опять поискать по 322560 паттернам, понимая что вполне можно улучшить ещё и 18-ку. Она и правда на порядок улучшена.

D(24, 20) начала маячить где-то на горизонте.

[Huz]

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

$18852797512788010920723387591494690548010011$

Congratulations!

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

Насколько помню у него порядок проверки чисел в кортеже может меняться при изменении паттерна (смены расстановки).

Yes, and it is worse than that: I do a lot of the checks in parallel, so for example I will check all numbers for divisibility by small primes before even an is-prime() check, which pushes a lot of extra rejections into the 0 bucket.

[Dmitriy40]

Huz
Another acceleration method.
As far as I remember, factor uses LCM to find divisors, so instead of performing LCM to the end at each location, you can perform one (ten, one hundred) curves check at each location and move on to the next even if the factorization is not completed, of course, remembering the intermediate state and continuing next time from it further.
The advantage here is that you don't have to wait long for a complex place to decompose if there is a simpler place that will discard the candidate faster (with fewer verified curves). The advantage lies in faster discarding of unsuitable candidates, because usually the complexity of LCM factorization varies greatly for different places (and not only for places, but also for specific numbers), and thus you can more quickly find a reason to discard a candidate.
Of course, this will have to get inside the LCM and cut the calculation into pieces, which is not easy. But it's probably not that difficult, because there's probably a loop of iterating over curves, and you can break it and save the state so that you can return to it later.
To check, try adding counters on how many curves the LCM checked for each location (and how long it took), it will be a reason to reflect on how much more profitable it could be.

-- 04.11.2025, 22:12 --

You can also do this without delving into LCM: run a separate thread for each location and perform factorization in it, as soon as there are enough conditions at any location to discard a candidate, stop and close all threads. It will work, of course, and on single-threaded CPUs, just not so well (the step of calculations will be almost a multiple of ticks, usually 18ms). This way, you can use standard OS methods without changing the LCM source.

[VAL]

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

$\tikz[scale=.67, transform shape, font=\fontsize{11}\selectfont, black!70!]{ \node at (4.79,10)[shading=ball,ball color=red!70!violet!100!, white] {\color{yellow}\Huge\textbf{18852797512788010920723387591494690548010011}} }$

Поздравляю с ожидаемым (в отличие от D(48,21) успехом!

У меня освободились 32 потока

[Yadryara]

Спасибо.

VAL в сообщении #1708319 писал(а):

У меня освободились 32 потока

Самое время разобраться что было не так при запуске из консоли.

А у меня 12 потоков пока не освободились. Досчитываю ранее запланированное, в том числе чтобы убедиться что ещё ниже 19-ка пока не найдётся.

[DemISdx]

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

$\tikz[scale=1.5, transform shape, font=\fontsize{11}\selectfont, black!70!]{ \node at (4.79,10)[shading=ball,ball color=green!70!violet!100!, white] {\color{yellow}\Huge\textbf{D(24, 19)}} }$

$\tikz[scale=.67, transform shape, font=\fontsize{11}\selectfont, black!70!]{ \node at (4.79,10)[shading=ball,ball color=red!70!violet!100!, white] {\color{yellow}\Huge\textbf{18852797512788010920723387591494690548010011}} }$

Вау!
Yadryara
Поздравляю!

[Yadryara]

Спасибо, Демис.

Ну что, за двадцаточку возьмёмся? У Вас насколько помню, проблем с запуском не было. В том числе из консоли. А если и были, то успешно решались.

К тому же предлагают от 20 до 27 потоков:

https://boinc.progger.info/odlk/forum_thread.php?id=365&postid=18037 писал(а):

Насколько понимаю, в поиске следующих цепочек помощь Ядряре не требуется.
То есть я хочу сказать - моя помощь.
А то могу предложить 20 или даже 27 потоков.
Предлагаю, но не навязываю.