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

[EUgeneUS]

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

Ну и как тут координировать? Проверка и перепроверка, конечно дело нужное, но зачем же считать одно и то же, если есть огромное количество девственно чистых паттернов

Я бы на данный момент разделил процессы счета по программам Дмитрия и по программам Хуго.
На это есть причины (и более простая координация не главная из них).

[Yadryara]

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

Я бы на данный момент разделил процессы счета по программам Дмитрия и по программам Хуго.

Они и так на данный момент разделены.

И мы делаем биекцию, главным образом для того, чтобы сопоставить две таблицы, увидеть, что уже посчитано и что считается. А зачем нам это надо? В первую очередь для того,

чтобы не считать одно и то же.

Не согласны?

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

На это есть причины (и более простая координация не главная из них).

Ну так и назовите эти причины, и главную и не главную...

[EUgeneUS]

Главная причина.

Мы решаем две задачи:
1. Найти цепочку, меньшую, чем известная.
2. Доказать минимальность цепочки (вновь найденной или известной, если меньшая не найдется).

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

1. Код Хуго имеет доказательную силу. Мы же принимаем доказательства минимальности других цепочек с его использованием, не так ли?

2. А вот код Дмитрия, при всем к нему уважении, доказательной силы не имеет. Если бы я поленился или не догадался проверить ускорители на двух известных цепочках, то ошибка бы не была найдена до ди сих пор. Sad but true.

-- 08.11.2022, 10:50 --

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

Но заниматься этим сейчас смысла нет, так как паттерны с малыми LCM всё равно будут считаться по полгода каждый.

UPD: Когда\если будет код, реализующий "рекурсивный квадратичный перебор с компиляцией ускорителей в run-time", вот тогда можно заняться покрытием его тестами для обеспечения его доказательной силы.

[VAL]

$M(1296)\ge 9$

(Оффтоп)

n=933494781513052510360737869469783494742530661062540398614674556519250312192643367569341971941328459081984137162249809299999997 
n+3 = 2^(8) * 5^(8) * 1733 * 12487 * 3 996378 432681 067844 718548 401603 (31 digits) * 107 941540 907394 801908 777653 963461 881480 331726 407723 522345 522588 606949 716465 362661 (81 digits)  
n+4 = 13^(2) * 23^(2) * 37^(2) * 47^(2) * 1523 * 1 071023 * 25 910236 520718 682921 * 81 695902 669176 843070 822805 244825 134592 009579 053181 323283 200648 425711 013102 609192 208509 (86 digits)

PS: Извините, что я не в ногу

[EUgeneUS]

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

Извините, что я не в ногу

Тоже хорошо
Принимайте поздравления!

[VAL]

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

Тоже хорошо
Принимайте поздравления!

Спасибо!

Сначала подумал, что достижение слишком локальное для поздравлений. Но потом нашел оправдание: найдена первая цепочка длиннее 8, для $k>1000$

[Yadryara]

VAL, поздравляю! Мы тоже не в ногу

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

1. Код Хуго имеет доказательную силу. Мы же принимаем доказательства минимальности других цепочек с его использованием, не так ли?

Не так, конечно. Я ведь специально аккуратно формулировал:

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

10-ка уменьшена в 238 раз и заявлена в качестве минимально возможной;

Обратите внимание: не сказано, что доказана минимальность и не сказано что "мы принимаем доказательства минимальности".

Заявлена в качестве минимально возможной.

Вот что я сказал. Так что по-хорошему проверять-то надо. Лично я проверял минимальность вплоть до 6-ки включительно и об этом сказано примерно на 20-й странице.

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

2. А вот код Дмитрия, при всем к нему уважении, доказательной силы не имеет. Если бы я поленился или не догадался проверить ускорители на двух известных цепочках, то ошибка бы не была найдена до ди сих пор. Sad but true.

Нет, тоже неверно. Вы молодец, что проверили известную 9-ку. Но если бы этого не сделали Вы, это сделал бы лично я. Планы такие были. И главное здесь не та 9-ка. Мне и раньше не нравилось называть непроверяемыми малопроверяемые места. И хотел спросить конкретно про них.

Может быть Вы и не заметили, но я и после обнаружения этой ошибки проверял проги Дмитрия на других цепочках. На данный момент ошибок счёта в последней версии не выявлено.

Есть ещё кое-что, что я хотел бы проверить, но об этом позже.

Так что проги Дмитрия и Hugo в моих глазах равноправные. Но проги Дмитрия будут в разы, а то и в десятки раз быстрее.

[EUgeneUS]

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

Но проги Дмитрия будут в разы, а то и в десятки раз быстрее.

Насколько понимаю,
1. Программы Дмитрия, которые есть в общем доступе сейчас, условно их назовем "линейный перебор с ускорителями", далеко не всегда быстрее кода Хуго. Даже сам Дмитрий предлагал считать кодом Хуго:

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

Думаю надо прекращать счёт выложенными SSE ускорителями, это слишком долго. Лучше считать программой Hugo, раз она вроде как уже есть под винду.
Когда (и если) доделаю компиляцию на лету, тогда и посмотрим.

2. Дмитрий сейчас работает, насколько понимаю, над "рекурсивным перебором с компиляцией ускорителей в run-time". Вот это должно бы быть в разы или на порядки быстрее. На что сильно надеюсь.

-- 08.11.2022, 13:07 --

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

Так что проги Дмитрия и Hugo в моих глазах равноправные.

Я тоже считаю, что код Дмитрия, который общедоступен сейчас, свободен от критичных ошибок. Но это всего лишь Ваше и моё мнения. Для верификации кода нужно больше аргументов. И заниматься этим сейчас, в отношении кода "с линейным перебором с ускорителями" смысла не вижу, так как паттерны с малым LCM он считает долго.

[Yadryara]

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

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

Но проги Дмитрия будут в разы, а то и в десятки раз быстрее.

Насколько понимаю,
1. Программы Дмитрия, которые есть в общем доступе сейчас, условно их назовем "линейный перебор с ускорителями", далеко не всегда быстрее кода Хуго.

Послушайте, ну я же ведь специально написал "будут". Сейчас выделил и в цитате болдом.

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

Есть ещё кое-что, что я хотел бы проверить, но об этом позже.

Вот что имел в виду. Проги Дмитрия проверяют до $10^{22}$. А вот эта цепочка хоть и незначительно, но всё-таки повыше:

LCM14642258400-4552831417-8:10000190907136349587417: 4, 32, 16, 12, 32, 12, 12, 12, 12, 12, 8, 12, 4,128, 12, valids=8, maxlen=5

[Dmitriy40]

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

Dmitriy40, а где можно увидеть биекцию в краткой форме, то есть только имена паттернов?

Командой в консоли: for /f "tokens=3,5 delims=b*@" %a in (patterns_sort_by_Hugo.txt) do @echo b%a:%b>>patterns_only_b_and_lcm.txt
Для файла patterns_sort_by_Dmitriy.txt тоже разумеется сработает.

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

2. Отсутствие у Hugo компа с Виндой.

Совершенно не мешает координировать работу.
Языковый барьер да, хуже, но запросить паттерны по списку, отослать логи и сказать какие посчитаны - несложно, гугло переводчик точно справится.

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

Кстати, нашёл, что Вы собирались считать именно шаг 14642258400:

Передумал.

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

Хотя от этого диапазон уменьшается всего лишь на 0.03%.

Вот именно. И столько экономить ...
Плюс вдруг Hugo ошибся и что-то пропустил, считаю вполне можно пожертвовать совершенно жалкие 0.03% времени ради лишней перепроверки.

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

2. А вот код Дмитрия, при всем к нему уважении, доказательной силы не имеет.

И я с этим вполне согласен. Почему и не хочу (пока что) что-то считать полностью, ведь для нахождения почти всех цепочек достаточно проверить лишь самые малые простые (в квадратах), что решает первую задачу из указанных.
Полностью согласен и с комментарием о покрытии тестами.

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

Может быть Вы и не заметили, но я и после обнаружения этой ошибки проверял проги Дмитрия на других цепочках. На данный момент ошибок счёта в последней версии не выявлено.

Спасибо! По идее это должен делать я и сам, но как обычно или времени нет, или не подумал, или проверил лишь частично (как например глюк с ненахождением известной минимальной 11-ки).
И всё же я больше согласен с EUgeneUS: если уж цепочка нашлась, то это 100% верно, а вот если ничего не нашлось, то остаётся место для сомнений. В частности и поэтому доказательство минимальности существенно труднее нахождения решения. И покрыть тестами как бы не сложнее написания кода, без знания тонкостей реализации невозможно гарантированно покрыть тестами всю возможную область (сколько раз и я и Вы обнаруживали неочевидные причины пропуска каких-то цепочек).

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

Насколько понимаю,
1. Программы Дмитрия, которые есть в общем доступе сейчас, условно их назовем "линейный перебор с ускорителями", далеко не всегда быстрее кода Хуго.

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

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

Вот что имел в виду. Проги Дмитрия проверяют до $10^{22}$. А вот эта цепочка хоть и незначительно, но всё-таки повыше:
LCM14642258400-4552831417-8:10000190907136349587417: 4, 32, 16, 12, 32, 12, 12, 12, 12, 12, 8, 12, 4,128, 12, valids=8, maxlen=5

Поясняю: при поиске других цепочек (15, 14, 13) внутри самого глубокого цикла стояла проверка что получаемое число не выше порога, даже если ускоритель немного и зашёл за него и вернул кандидатов. В текущем коде такой проверки нет (и ради скорости, и ради простоты кода, хотите добавьте, см. ниже). А интервал для проверки ускорителю передаётся фиксированный (1e8) и потому он вполне может заходить на вот эту величину (1e8*шаг_паттерна) за предел и такие цепочки отброшены не будут. У себя в совсем другом коде я это поправил (вычислением интервала для проверки ускорителем на лету):

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

Несколько последних больше 1e22 так как ускорители ночью считали с фиксированным шагом и последний кусок нередко вылетал за верхний предел. Утром и это поправил, больше таких не будет.

Да, возможно стоило пояснить что поправил лишь у себя, а в выложенном коде всё осталось по прежнему. Но я и не вижу в этом большой проблемы, ну посчитается немного лишнего, для не слишком больших шагов паттерна это слёзы, а для больших всё происходит и так быстро и экономить секунды ... Если очень хотите добавьте в код в условие проверки if(k>=8 ещё и условие h<stop (получится if(h<stop && k>=8) и всё.

-- 08.11.2022, 14:03 --

Да, о планах.
Сейчас фактически ничего не считаю.
Рекурсивный перебор пишу, но медленно. Засада не в самом переборе, его-то сделать легко, а в выборе условий для переключения режимов, и вот тут конкретная засада, слишком они сложные для хорошей точности оценки (которую необходимо производить в реальном времени, а не один раз и навсегда), ставить же "на глаз" может дать проигрыш в несколько раз.

У меня тут другая идея, после сравнения скорости кода Hugo с банальным кодом PARI, похоже код Hugo можно и ещё ускорить без всяких укорителей или добавления чего-то нового, всего лишь уменьшить одну из констант в коде. Вот и занялся проверкой и доказательством этой идеи. И даже если он вдруг и не захочет такого делать, значит ускорю свой (будущий) код. Ценой однократного доказательства допустимости уменьшения константы, думаю за несколько дней счёта справлюсь. Т.е. один раз потратить много времени (дни) чтобы ускорить проверку тотально всех паттернов. Насколько получится ускорить пока непонятно, прикидываю хотя бы в несколько раз (1.5-2-3), надеюсь и до порядка, но тут вопрос сколько потратить времени на доказательство (оно квадратично от коэффициента ускорения всех паттернов). Э, настолько ускорится не проверка всего паттерна, а лишь перебор больших простых в квадрате, но это позволит чаще запускать второй/третий перебор и это тоже даст эффект.

[Dmitriy40]

Huz
Hugo, can you run two tests to find out what exactly is slowing down in your code when iterating over large primes?
1. How long to iterate primes from $0$ (or $10^6$) to $\sqrt{10^{22}/13/17}=6.7\cdot10^9$. Leave only iterate, do not perform any calculations with them (but only so that the optimizer does not throw out all the code at all, for example, calculate their sum and output it to the log at the end, at the same time there will be an additional check).
2. The same iterate primes, but now with the calculation of the CRT over them according to any pattern, for example b1850 for the same conditions with my tests above (and also sum up the numbers obtained after the CRT). Do not perform any checks after the CRT.

Because the situation when your code in C is 9 times slower vs and so not fast code in PARI - is abnormal! And it's interesting to understand what the reason is.

[Huz]

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

$M(1296)\ge 9$

Cool stuff.

Out of curiosity (and to check that my code works for these sorts of numbers), I searched for minimal $D(1296,2)$:

724691077258400 = 2^5.5^2.7^2.61.67^2.181.373
724691077258401 = 3^2.11^2.17^2.19^2.23.29.73.131

It is only a 2-chain, but the result is unusually smooth - no prime factor greater than 373.

-- 08.11.2022, 14:40 --

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

Hugo, can you run two tests to find out what exactly is slowing down in your code when iterating over large primes?

I think I already know one reason: I am calling a next_prime() function that works with large (gmp) integers. There is a TODO note in the code to use a fixed-width 64-bit implementation, but I had forgotten that.

But I will try writing code for some specific timing tests as you request.

Note that I have been sent partial logs for work on b111, which it was suggested could take hundreds of days. Extrapolating total time from progress after 65 hours, I believe it will complete in under 15 days.

I have also pushed a change in the infrastructure code which speeds things up by about 20% for me. A zip file with a 64-bit Windows build of this code prepared by CorporalTermit is now available at release v20221107.

[EUgeneUS]

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

Extrapolating total time from progress after 65 hours, I believe it will complete in under 15 days.

COOL!

[Dmitriy40]

EUgeneUS
Демис прислал лог счёта паттернов с двумя наибольшими шагами (меньший не полностью), он проверял всё тотально без исключения совпадающих (в отличие от нас), так вот, все найденные мной цепочки есть и у него, но есть и много лишних. Подозреваю что они в исключённых мною паттернах, но самое интересное (и возможно неприятное) что много цепочек не совпадает, т.е. найдены лишние цепочки. Но так как речь про maxlen не более 9-ти, то не совсем понятно должны ли они были найтись и в оставленных нами паттернах или нет и нами всё сделано правильно. Позже посмотрю подробнее.

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

I have also pushed a change in the infrastructure code which speeds things up by about 20% for me. A zip file with a 64-bit Windows build of this code prepared by CorporalTermit is now available at release v20221107.

Hugo, it's great that you posted the release executable file right on github.

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

I think I already know one reason: I am calling a next_prime() function that works with large (gmp) integers.

Yes, next_prime() is usually slow regardless of the bits. I'm not sure how exactly you have it. But the primes should not be searched for by getting the next one, but by Sieve of Eratosthenes, which for primes up to 6.7e9 work for less than 10s-30s and require less than 100K bytes of memory. Code in a variety of programming languages is freely available on the web (including wiki), especially for such small numbers (numbers up to 1e10 is small for this task).

[VAL]

$M(1080)\ge 9$

(Оффтоп)

n = 8467260996379052104335996989692097732356922910193603433377498475558657389596992751751472663966813496865624448627893433740108273038671868 
n+5 = 13^(4) * 31^(2) * 41^(2) * 47^(2) * 350281 * 15374 677792 551557 010669 806947 * 15426 241166 591612 139713 278953 918206 797179 230615 608481 345311 876761 639267 025285 782110 208371 (89 digits)  n+8 = 
2^(2) * 17^(4) * 67^(2) * 101^(2) * 74 054561 359003 * 1110 092541 485488 944196 847909 * 6732 617139 610501 513580 053363 964206 339367 328293 781529 194762 844603 594591 168950 465463 (82 digits)