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

[Yadryara]

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

Но ИМХО нет смысла по ним считать, слишком медленно. Разве что лишь паттерны с самыми большими шагами/модулями.

Ну вот, наконец-то сверил скорости по Вашей проге и по Hugo.

Паттерн b101.

 . 50p 363p 32p 16807p 18p 5p^2q 4pq 3p^2q 2p^2q .

В нотации Дмитрия: LCM14642258400-2398005945-4.

Время счёта в один поток.

Hugo: 3 часа.
Ахиллес: 4 часа.
Паровозик: 11 часов.

Прошу Дмитрия и Евгения тоже замерить скорость для этого паттерна.

Я не считал все 11 часов. Лучшее, что нашлось за 2 часа:

397205950551315115545: 64, 32, 12, 96, 12, 12, 12, 12, 12, 12, 12, 12, 8, 8, 4, va=9, max=8

421504074747029961945: 96, 32, 12, 12, 12, 12, 12, 12, 12, 12, 8, 12, 8, 8, 16, va=9, max=8

1009343400513912197145:384, 32, 12, 12, 12, 12, 12, 12, 12, 12, 8, 12, 8, 8, 8, va=9, max=8

1014914306831596843545:160, 32, 16, 12, 8, 12, 12, 12, 12, 12, 12, 12, 12, 16, 8, va=9, max=8

[EUgeneUS]

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

Ну вот, наконец-то сверил скорости по Вашей проге и по Hugo.

Мне не очень понятно, что с чем Вы сравнивали :(

Вы не могли бы привести время счета для одного и того же компьютера, но для разных программ?

[Yadryara]

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

Мне не очень понятно, что с чем Вы сравнивали :(

Спрашивайте, я поясню.

Я прошу Вас запустить на Вашем SSE-компе тот паттерн, что я указал. В один поток.

В каком блоге смотреть скорость Ахиллеса, надеюсь знаете...

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

Вы не могли бы привести время счета для одного и того же компьютера, но для разных программ?

В настоящее время не могу. У меня же нет программы Хьюго, заточенной под Винду.

У Наталии есть такая. И есть возможность скачать проги Дмитрия. Так что вроде на Ахиллесе можно будет сравнить.

Чтобы на одном и том же компе были обе проги, вроде такого компа пока нет.

Конечно большая надежда есть на расстановку хотя бы ещё одного квадрата и компиляцию на лету. Но решил пока так сравнить.

[Yadryara]

Dmitriy40
Ваша новая прога находит новые цепочки по сравнению со старой. Это ожидаемо.

Но прискорбно то, что есть и обратные примеры:

LCM554400-31545-4:3061508878212000345: 96, 48, 4, 48, 12, 12, 12, 12, 12, 12, 16, 12, 16, 16, 48, valids=7, maxlen=6

LCM554400-31545-4:3064062837929971545: 96, 4, 12, 48, 8, 12, 12, 12, 12, 12, 32, 12, 32, 8, 24, valids=7, maxlen=5.

Новая прога их найти не смогла. В отличие от старой.

[VAL]

$M(1296)\ge 8$

(Оффтоп)

n = 872668217163605424342933356254545973132577966920336193194516080575721375891331648590551271913479678099999998   
n+3 = 11^(2) * 19^(2) * 23^(2) * 37^(2) * 1493 * 503857 * 344199 725985 347677 436465 426339 * 106541 753980 716968 396307 621358 376895 737694 984174 058269 105239 (60 digits)  
n+6 = 2^(2) * 41^(2) * 43^(3) * 59^(3) * 189613 * 2871 154603 * 6512 847820 244396 735422 733403 325907 277091 (40 digits) * 5 687021 907621 489919 626617 419801 056109 309541 (43 digits)

$M(2160)\ge 8$

(Оффтоп)

620407618313091749007503291089480578219725162599418708050180286282791505699542489440631544396818334333083799431132652799999998

Это новый текущий рекорд - самого большого $k$, для которого известна цепочка длиннее 7.
Нашелся неожиданно быстро (меньше часа на все, включая разработку паттерна, реализацию поиска и проверку)!

Как обычно для $k$, кратного 5, прошу уточнить оценку сверху.

[Dmitriy40]

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

Прошу Дмитрия и Евгения тоже замерить скорость для этого паттерна.

До 1e22 ждать несколько часов не стал, посчитал до 1e21, но так как время линейно, то на 10 домножите сами:
Win x64, gp64, AVX2:
LCM14642258400-2398005945-4:50953382534746363545: 12, 16, 16, 12, 64, 12, 12, 12, 12, 12, 12, 12,128, 64, 32, valids=9, maxlen=7
LCM14642258400-2398005945-4:397205950551315115545: 64, 32, 12, 96, 12, 12, 12, 12, 12, 12, 12, 12, 8, 8, 4, valids=9, maxlen=8
LCM14642258400-2398005945-4:421504074747029961945: 96, 32, 12, 12, 12, 12, 12, 12, 12, 12, 8, 12, 8, 8, 16, valids=9, maxlen=8
LCM14642258400-2398005945-4:823933771266299827545: 48, 32, 4, 12, 12, 12, 12, 12, 12, 12, 32, 12, 64, 32, 12, valids=9, maxlen=7
LCM14642258400-2398005945-4:983096238918548688345: 12, 16, 4, 12, 12, 12, 12, 12, 12, 12, 32, 12, 64, 8, 2, valids=9, maxlen=7
LCM14642258400-2398005945-4: end, time: 1083.769s
Win x64, gp32, SSE:
LCM14642258400-2398005945-4:50953382534746363545: 12, 16, 16, 12, 64, 12, 12, 12, 12, 12, 12, 12,128, 64, 32, valids=9, maxlen=7
LCM14642258400-2398005945-4:397205950551315115545: 64, 32, 12, 96, 12, 12, 12, 12, 12, 12, 12, 12, 8, 8, 4, valids=9, maxlen=8
LCM14642258400-2398005945-4:421504074747029961945: 96, 32, 12, 12, 12, 12, 12, 12, 12, 12, 8, 12, 8, 8, 16, valids=9, maxlen=8
LCM14642258400-2398005945-4:823933771266299827545: 48, 32, 4, 12, 12, 12, 12, 12, 12, 12, 32, 12, 64, 32, 12, valids=9, maxlen=7
LCM14642258400-2398005945-4:983096238918548688345: 12, 16, 4, 12, 12, 12, 12, 12, 12, 12, 32, 12, 64, 8, 2, valids=9, maxlen=7
LCM14642258400-2398005945-4: end, time: 1839.615s

Аккуратная оценка времени для ускорения с перебором дополнительного простого для этого паттерна даёт время 30 минут до 1e22. Из которых на перебор простого до 44721359549 и вычисление КТО уходит 25 минут, на компиляцию 138-ми ускорителей для простых до 823 и перебор ими до 1e22 уходит 3 минуты (2 минуты только на компиляцию, с запасом), на перебор в PARI простых от 823 до 826403 и проверку каждого получаемого паттерна до 1e22 уходит 2 минуты, на проверку только начального числа если оно меньше 1e22 (таковых всего 57 тысяч) всех остальных простых уходит меньше секунды. Вместо где-то трёх часов на перебор текущими ускорителями AVX2. Хорошая оценка, мне нравится.

Проверил что будет реально: скомпилил все 138 ускорителей, компиляция заняла минуту, написал перебор в PARI, запустил.
Перебор всеми ускорителями до 1e22 занял 63 секунды.
Перебор в PARI простых от 823 до 826403 с перебором по каждому паттерну до 1e22 тоже в самом PARI занял 188 секунд.
Перебор простых от 826404 до 44721359549 и проверкой получившегося начального числа (их 56825 штук меньше 1e22 и все меньше 2.34e9) занял 35 минут. 98% которых занял перебор простых больше 2e9 и подсчёт КТО, давшая начальное число больше 1e22 и проверке не подлежащее. Есть у меня подозрение что проверять все простые до десятков миллиардов не нужно, КТО вроде бы гарантирует что начиная с некоторого простого все начальные числа будут больше 1e22 и перебор можно оборвать (спустя примерно минуту), осталось лишь аккуратно вычислить это самое простое.
Найдена 21 восьмёрка (все с ускорителями с простыми до 300), в том числе одна из показанных выше (397205950551315115545). Вторая восьмёрка (421504074747029961945) не нашлась так как на перебираемом месте (с 5 в паттерне) имеет не квадрат другого простого.
Суммарное время составило 40 минут. Совпадение с оценкой в 30 минут считаю хорошим.

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

Новая прога их найти не смогла. В отличие от старой.

И это правильно: они обе в позиции F имеют не $11^1$, а $11^2$, т.е. должны находиться по совсем другому паттерну, попробуйте LCM6098400-5575545-4, у меня он их обе находит:

T:\M12n11_x32SSE\M12n11>LCM6098400-5575545-4.exe 502018378297 1
[0x74E2A08A39]
T:\M12n11_x32SSE\M12n11>LCM6098400-5575545-4.exe 502437170065 1
[0x74FB96CB91]

А дальше дело PARI кода проверки.

-- 05.11.2022, 18:57 --

Интересно оценить для другого паттерна, возьму LCM42688800-377145-4 как вероятно наиболее сложный из семейства $7^2 11^2$.
Текущими ускорителями его проверять 1e22/42688800/4e7=68 дней.
Размещая простое до 15300 (их 1780 штук) затратим на компиляцию и работу ускорителей 15.1ч (на компиляцию 0.5ч расчётных), на перебор в PARI простых до 15e6 и каждого паттерна до 1e22 нужно 24 минуты, плюс минут 30-35 на перебор простых до 44721359549 с КТО и проверкой лишь если начальное число меньше 1e22.
Итого порядка 16ч.

[Huz]

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

Как обычно для $k$, кратного 5, прошу уточнить оценку сверху.

I have $M(2160) \le 127$, checking moduli up to 40000.

For these large $k$, it isn't clear how many moduli to check, but 128 is already disallowed with moduli up to 60.

[VAL]

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

I have $M(2160) \le 127$, checking moduli up to 40000.

Thanks!

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

For these large $k$, it isn't clear how many moduli to check, but 128 is already disallowed with moduli up to 60.

Of course.

[Yadryara]

Dmitriy40, благодарю.

То есть ожидается выигрыш по времени в 4-6 раз, но не в 1000.

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

И это правильно: они обе в позиции F имеют не $11^1$, а $11^2$, т.е. должны находиться по совсем другому паттерну,

А старая прога их нашла по тому же паттерну. Почему, интересно...

[Dmitriy40]

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

То есть ожидается выигрыш по времени в 4-6 раз, но не в 1000.

Для того паттерна. Для других может быть и по другому. Особенно для тех, где много долгих переборов - но не настолько долгих чтобы запускать перебор по второму простому ещё на полчаса. Ускорители работают сильно быстрее, а PARI медленнее, потому может быть как выигрыш, так и проигрыш, смотря сколько можно проверить ускорителями.
Это если ещё не получится с КТО, оборвать перебор в полсотни раз быстрее.
Вот к примеру возьмём паттерн b579, который проверен Demis-ом, v=[12,16807,50,3,32,1,18,5,28,3,242], программа Hugo почему-то перебирает позицию с 1, хотя позицию с 5 выгоднее. Проверка простых до 449 заняла 13800с, проверка всего паттерна 18990с. Оценка времени с ускорителями и перебором лишнего простого даёт время 2 минуты на ускорители (82 штуки, включая и компиляцию) (вместо 13800с) плюс 3.5 минуты в PARI до простого 826403 плюс минут 30-35 остальных больших простых. Т.е. снова порядка 40 минут, против 5.28ч, в 8 раз быстрее.
Другой паттерн, тоже от Demis-а, b576, v=[12,16807,50,3,32,11,18,5,28,3,2], здесь у Hugo для первых простых производится и второй перебор, по месту с 5. Перебирая вслед за Hugo позицию с 11 (второй перебор с ускорителями очевидно не нужен) на 343 ускорителя уйдёт 8.5 минут (из которых 5 минут только на компиляцию) (против 20.2ч, т.е. в 150 раз быстрее), на перебор в PARI простых до 2.7e9 ещё 6 минут, и минут 20 на перебор простых до 30e9, итого 35 минут. Против 77133с=21.4ч, в 37 раз быстрее.
А вот паттерн b580 даст обратную картину, в 0.11с не уложится даже компиляция ускорителя, вообще без запуска (который займёт порядка секунды или десятых долей).
Вообще если будут паттерны которые Hugo проверяет заметно менее получаса (но более единиц секунд), то на таких ускорители будут проигрывать.
По другим паттернам искать время проверки программой Hugo лень.

[Huz]

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

Вот к примеру возьмём паттерн b579, который проверен Demis-ом, v=[12,16807,50,3,32,1,18,5,28,3,242], программа Hugo почему-то перебирает позицию с 1, хотя позицию с 5 выгоднее.

Thanks, that's a useful observation.

I recently added a command-line option to select the strategy for choosing which position to target first; the current default strategy is "pick the position for which the remaining required tau() is the greatest". Would you suggest that a better strategy would be "pick the position for which the remaining required tau() is the smallest"? Or do you think it needs more that that?

It should be easy to add other strategies now, and compare them on specific cases.

[Yadryara]

Huz, а как Вы проверяете стартовые(начальные) числа?

Пока продолжаю проверять тот самый паттерн. b085 по Hugo. LCM554400-31545-4 по Дмитрию.

Проверен интервал 297387e13 — 333e16

Лучшая непрерывная находка:

3238732922755761945: 72, 8, 4, 48, 8, 12, 12, 12, 12, 12, 12, 12, 8, 4, 8, va=7, max=7

[Huz]

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

Huz, а как Вы проверяете стартовые(начальные) числа?

Sorry, I don't understand the question. Do you mean the numbers fixed in the pattern (batch)?

[Yadryara]

Нет, в данном примере, стартовое число $31545$.

$31545+554400\cdot5841870351291= 3238732922755761945$

Здесь стартовое число конечно крошечное. $31545$ намного меньше чем $297387e13$.

Но ведь бывают и стартовые числа из интервала

$297387e13$ — $988735e16$ ?

[Yadryara]

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

Есть у меня подозрение что проверять все простые до десятков миллиардов не нужно, КТО вроде бы гарантирует что начиная с некоторого простого все начальные числа будут больше 1e22 и перебор можно оборвать (спустя примерно минуту), осталось лишь аккуратно вычислить это самое простое.

А Вы видели какое-то подтверждение, что в программе Hugo вообще проверяются стартовые числа?

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

Хотя бы то, что нужно учесть обязательно. Ведь не хочется верить, что не в коня корм.

Всё-таки не в коня корм. Меня опять не поняли.

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

А всё потому, что тот перебор трудно назвать умным. Учитывается, что в искомой 11-ке обязательно есть число $32p$. Но ничего не говорится о об использовании того факта, что в искомой 11-ке не менее железобетонно есть число $18p$.

То есть если хочется перебирать именно все возможные паттерны, то как раз и нужно учитывать обязательное наличие числа $18p$, которое есть во всех паттернах.

То есть, например, вместо того чтобы запускать два перебора навстречу друг другу и ждать встречи 20 миллионов лет(по подсчётам Дмитрия), вполне можно было запустить два перебора с $18p$ слева и справа от $32p$, тем самым всё равно покрыть все возможные паттерны, но ускорить процесс за счёт увеличения шага.

Если даже это непонятно, буду сожалеть.