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

[Yadryara]

Dmitriy40, а зачем всё-таки продолжать считать выше уже найденной 15-шки?

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

Кроме того, антиолловский способ намного быстрее и точнее олловского. При той же точности он быстрее в сотни, если не
в тысячи раз.

Что сейчас делать людям которые хотят помочь с поиском? Совсем недавно такой работы было полно. А сейчас?

Сделайте, пожалуйста, замену 37 на 41. И тогда работы снова будет немало. Если можно, покажите для 32-х разрядов Асмовские исходники и джипишные проги до и после переделки.

Если смогу разобраться, то буду переделывать дальше самостоятельно.

[Dmitriy40]

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

Конечно. Как назвать-то этот подкласс ? К41-11 нельзя, ибо не указано какое число заменяется. Может просто 11-22 ? 11 одиночных простых и шаг на 22% больше минимального.

Чем раньше найдётся новая 15-ка, тем быстрее будут завершаться новые проверки. Даже если не найдётся, они будут завершаться всё быстрее и быстрее. Но она найдётся, против тервера не попрёшь.

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

Что сейчас делать людям которые хотят помочь с поиском? Совсем недавно такой работы было полно. А сейчас?

Сделайте, пожалуйста, замену 37 на 41. И тогда работы снова будет немало.

А объясните пожалуйста смысл этого? Зачем искать пятнашку в другом подклассе? На её поиск мне потребуется до двух недель счёта. Потом 37 заменим не на 41, а на 43, и ещё две недели счёта. И т.д. Не улавливаю в этом смысла, ведь сколь нибудь близкую к минимальной пятнашку так не найдём (разве только за десятилетия поисков). Уменьшить порог в несколько раз ценой месяцев счёта ...
Или задача просто загрузить вычислительные мощности? Так интересных задач полно. Да хоть вон возьмите у VAL его кучу .gp программ и считайте новые мировые рекорды. Ну да, без ускорителей (хотя для М36 их точно можно использовать, другие не проверял, главное список паттернов как-то сформировать, хоть руками), но хотя бы так.
Про исходники отвечу в личке, технология их компиляции слишком запутана и не отказоустойчива для выкладывания публично.

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

Dmitriy40, а зачем всё-таки продолжать считать выше уже найденной 15-шки?

Уже отвечал, но повторю: других полезных вариантов что считать в данной теме пока нету (мои попытки выявить подходящий подкласс паттернов М36 пока безуспешны), а потратить 3-4 дня чтобы не выбрасывать насчитанное другими участниками (20% 7e37 и 82% 9e37) и сохранения непрерывной статистики считаю возможным, это не месяцы и годы.

-- 09.04.2022, 13:48 --

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

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

Кроме того, антиолловский способ намного быстрее и точнее олловского. При той же точности он быстрее в сотни, если не
в тысячи раз.

Это верно только для $P_2$, а $P_1$ после фильтрации (ускорителями или просто использования паттернов) нельзя считать независимо по 11-ти местам, только по всем, а тогда почти без разницы проверять все совпадения или все несовпадения (считать $P_1^{11}$ или $1-P_1^{11}$), в штуках разница огромная, в точности одинаковая (числа $A$ и $1-A$ очевидно имеют одинаковую точность потому что $1$ точна).

[Yadryara]

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

А объясните пожалуйста смысл этого? Зачем искать пятнашку в другом подклассе?

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

Да, выполнимость этой задачи под большим вопросом. Но задача такая есть и Вы об этом знаете: A292580

"start of the first run" - это как раз о минимальности.

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

На её поиск мне потребуется до двух недель счёта. Потом 37 заменим не на 41, а на 43, и ещё две недели счёта. И т.д.

То есть Вы считаете, что Вам никто не поможет? И даже если так, Ваша прикидка неверна.

Как считать вероятности, Вы знаете, стало быть вполне можете прикинуть как шаг и наименьшая 15-шка будут двигаться навстречу друг другу:

$ 2.6 \cdot 10^{27}\to \leftarrow 6.6 \cdot 10^{37}$

А если повезёт(прикиньте какой шанс найти 15-шку, например, ниже $3\cdot 10^{37}$), то время поиска для каждого подкласса паттернов сразу же снизится в разы.

Ну и шаг в паттернах весьма быстро возрастает: на 22%, на
35%, на 61%, на 75%, ...

Кроме того, есть возможность попутно улучшить минимумы и для непрерывных цепочек 10-14.

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

Или задача просто загрузить вычислительные мощности? Так интересных задач полно.

Конечно полно. Но только эти задачи я в этой теме считаю оффтопом. Потому и обсуждаю единственную онтопную.

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

Про исходники отвечу в личке, технология их компиляции слишком запутана и не отказоустойчива для выкладывания публично.

Как скажете.

[EUgeneUS]

Несколько соображений\ИМХО.

1. Искать минимальную 15-ку с 12 делителями - дело безнадежное. Меньшую найти - реально. Но это особо ничего не даст, кроме некоторого улучшения в A292580.
2. Если и искать минимальную цепочку, то начинать где-то с 10-ки с 12 делителями. То есть с минимальной цепочки, по которой есть только оценка, а не точное значение. При этом сразу нужно озаботиться, чтобы метод поиска обеспечивал доказательство минимальности цепочки.
3. Что касается не найденных цепочек. То из вариантов:

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

$11 \le M(36) \le 15$...
$17 \le M(24) \le 31$...
$18 \le M(48) \le 31$...

имхо, лучше выбрать тот, который лучше ляжет на "ускорение".
Пока же, насколько понимаю, уважаемый Dmitriy40 рассматривал возможность ускорения только первого варианта.

4. Когда "целевой" вариант будет выбран, все таки хотелось бы вернуться к вопросу об ускорении на GPU.

[VAL]

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

3. Что касается не найденных цепочек. То из вариантов:
VAL в сообщении #1552106

писал(а):
$11 \le M(36) \le 15$...
$17 \le M(24) \le 31$...
$18 \le M(48) \le 31$...
имхо, лучше выбрать тот, который лучше ляжет на "ускорение".
Пока же, насколько понимаю, уважаемый Dmitriy40 рассматривал возможность ускорения только первого варианта.

Так и предполагалось, что за 36 делителей возьмется Дмитрий, а за 48 - я.
Остальные при желании могут присоединяться или решать другие задачи, например, по поиску минимальных цепочек. Разумеется, начинать следует с более реалистичных задач, чем минимальная пятнашка по 12 делителей. (Хотя не исключено, что она уже найдена )

[VAL]

Jon E. Schoenfield интересуется:

Цитата:

Also, if you have time, do you happen to have an upper bound for A292580(15,4)?

Полагаю, это перспективнее, чем искать минимальную пятнашку.

[Yadryara]

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

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

Нет, для тех кто в теме новичок, начинать надо с уже существующих проверенных программ. Сами же говорили:

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

А пока думаете, комп может посчитать,

А что прямо сейчас можно посчитать?

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

Jon E. Schoenfield интересуется:

Цитата:

Also, if you have time, do you happen to have an upper bound for A292580(15,4)?

Полагаю, это перспективнее, чем искать минимальную пятнашку.

Это про 4-ку с 30 делителями.

Вполне возможно, что это перспективнее. Но что делать человеку, который хочет именно помочь посчитать? Какую программу ему запускать на своём компе?

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

Ну, основная оптимизация - замена PARI на что-нибудь более быстрое...

И Вы заменили PARI на что-нибудь более быстрое при последней работе с 48-ю делителями?

[EUgeneUS]

VAL

Всё таки нужно учитывать следующие факторы:

1. Большая разница в вычислительных мощностях у участников. У меня в разы меньше, чем у уважаемого Dmitriy40, а у него в разы меньше, чем у Вас. Первое - если ориентироваться на счет "с ускорителями", на "голом" PARI/GP разница должна быть не столь большая, или нет. Второе - судя по озвученным количествам потоков.

2. Большая разница в подготовке участников. Минимальный уровень (сужу по себе): "PARI/GP увидел три недели назад, теорией чисел не занимался никогда".

3. Мотивацию участников, работающих "на энтузиазме". А мотивация одна - получение результата (пусть не лично, а в команде) за обозримое время. В этом контексте очень важны прогнозы - какой результат за какое время можно получить. И их уточнение в процессе счета на эмпирических данных.

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

[Yadryara]

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

1. Большая разница в вычислительных мощностях у участников. У меня в разы меньше, чем у уважаемого Dmitriy40, а у него в разы меньше, чем у Вас.

Впс даже не упомянули. Скажу сам: у меня в разы меньше, чем у уважаемого EUgeneUS.

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

если ориентироваться на счет "с ускорителями", на "голом" PARI/GP разница должна быть не столь большая, или нет.

Огромная разница, зачастую тысячекратная, выше это уже многократно отмечалось.

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

Неслучайно же сказано:

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

Спасибо за предложение!
С удовольствием воспользуюсь.

Но пока не видно, что воспользовался.

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

а) предлагать методы решения

Так предлагайте уже, кто ж против-то.

[EUgeneUS]

Yadryara

(Оффтоп)

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

Впс даже не упомянули. Скажу сам: у меня в разы меньше, чем у уважаемого EUgeneUS

Приношу извинения, что не упомянул - не было информации, как оценить вычислительные мощности на Вашей стороне.

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

EUgeneUS в сообщении #1552276

писал(а):
если ориентироваться на счет "с ускорителями", на "голом" PARI/GP разница должна быть не столь большая, или нет.
Огромная разница, зачастую тысячекратная, выше это уже многократно отмечалось.

Это фраза была чуть про другое.

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

Так предлагайте уже, кто ж против-то.

Свой уровень в данной теме обозначил. Вряд ли стОит ждать от меня предложений по методам решения.

[Yadryara]

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

Это фраза была чуть про другое.

Про что именно?

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

Свой уровень в данной теме обозначил. Вряд ли стОит ждать от меня предложений по методам решения.

Тогда вряд ли стОит высказываться столь категорично, Вы не находите?

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

Искать минимальную 15-ку с 12 делителями - дело безнадежное.

А уровень повысить можно, да ещё как.

[EUgeneUS]

Yadryara

(Оффтоп)

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

Про что именно?

Сравнивалась вычислительная мощность на мой стороне и на стороне уважаемого Dmitriy40, в двух вариантах:
А) с использованием ускоритетей. Разница в разы. Не в последнюю очередь, из-за того, что у меня нет AVX2.
Б) Без использования "ускорителей". Тут разница может быть меньше.
Вы же пишете об ускорении, то есть сравнивается другое.

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

Тогда вряд ли стОит высказываться столь категорично, Вы не находите?

Категорично!? Когда через слово вставляю "IMHO"...

[kotenok gav]

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

И сказать работает ли первый (второй работать обязан всегда и везде).

Второй работает, первый нет (Illegal instruction).
Процессор 64-битный AMD A8-7410 APU. AVX2 он, кажется, не поддерживает, да...

[Dmitriy40]

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

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

Это совершенно нереально, по нескольким причинам:
1. Не доказано (или я не помню) что минимальная пятнашка имеет формат КМК. Например проверить что нет решений с $p^{11}$ легко за пару минут, а вот проверка отсутствия решений с $p^5q$ (например для чисел 5-13) уже потребует сравнимого с затраченным времени. А ещё в принципе может быть и $p^3q^2$ и $p^2qr$. Да, все эти варианты намного реже КМК, но не доказано что они не дают меньшего решения, вдруг какая аномалия.
2. Компиляция каждого набора паттернов занимает пару часов, даже не считая вычисления по ним, только на компиляцию всех 2700 вариантов замены одного 37 на другие простые (чтобы прокрутить все паттерны за один раз по 227e6 проверок в моей программе) надо $2700\times2/24/30=7.5$ месяцев! Только на компиляцию! Плюс они ещё сколько-то времени будут считать. Очень сильно вряд ли Вам повезёт прямо с первыми проверенными вариантами замен и ещё до 1e34 (до которой мне считать порядка 2ч в один поток).
И это замена только одного числа. А ведь менять можно и другие числа, в том числе одновременно несколько ...
3. В этом Вы ошибаетесь: "Ну и шаг в паттернах весьма быстро возрастает: на 22%, на 35%, на 61%, на 75%, ...", вот табличка увеличения шага при замене одного любого числа на другое:

? forprime(p=41,97, print1("\t",p)); print; forprime(x=17,37, print1(x,":"); forprime(p=41,97, printf("\t%0.4f",p/x)); print)
        41      43      47      53      59      61      67      71      73      79      83      89      97
17:     2.4118  2.5294  2.7647  3.1176  3.4706  3.5882  3.9412  4.1765  4.2941  4.6471  4.8824  5.2353  5.7059
19:     2.1579  2.2632  2.4737  2.7895  3.1053  3.2105  3.5263  3.7368  3.8421  4.1579  4.3684  4.6842  5.1053
23:     1.7826  1.8696  2.0435  2.3043  2.5652  2.6522  2.9130  3.0870  3.1739  3.4348  3.6087  3.8696  4.2174
29:     1.4138  1.4828  1.6207  1.8276  2.0345  2.1034  2.3103  2.4483  2.5172  2.7241  2.8621  3.0690  3.3448
31:     1.3226  1.3871  1.5161  1.7097  1.9032  1.9677  2.1613  2.2903  2.3548  2.5484  2.6774  2.8710  3.1290
37:     1.1081  1.1622  1.2703  1.4324  1.5946  1.6486  1.8108  1.9189  1.9730  2.1351  2.2432  2.4054  2.6216

Как прекрасно видно, в порядке увеличения шага замены должны идти в порядке (знаменатель что менять, числитель на что, надеюсь не ошибся): $\frac{41}{37};\frac{43}{37};\frac{47}{37};\frac{41}{31};\frac{47}{31};\frac{41}{29};\frac{53}{37};\frac{43}{29};\frac{47}{31};\frac{41}{37};\frac{41\cdot43}{37\cdot31};\frac{59}{37};\ldots$, обратите внимание на предпоследнюю дробь, дальше таких будет только больше, вплоть до замены одновременно всех 6-ти чисел на другие (уже при шаге всего в 64 раза большем).

Я хотел пойти таким путём, перебрать все возможные варианты замен для плавного увеличения шага, правда не для пятнашки, а для 10-ки, там интервал от минимального шага до обнаруженного намного меньше, всего примерно 100 или 1000 (не помню навскидку, искать же точную цифру незачем), но даже и там количество вариантов растёт слишком быстро и без изменения подхода задача неподъёмная. Для пятнашки же у меня получаются оценки в миллионы лет счёта если не повезёт и в тысячи лет если крупно повезёт. Хотите — пробуйте. Я пас.

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

2. Если и искать минимальную цепочку, то начинать где-то с 10-ки с 12 делителями. То есть с минимальной цепочки, по которой есть только оценка, а не точное значение. При этом сразу нужно озаботиться, чтобы метод поиска обеспечивал доказательство минимальности цепочки.

Это я грубо оценивал где-то в сотни-тысячи лет счёта если не повезёт. Слишком много вариантов. В принципе такую задачу поставить можно, но ... нужна активная поддержка участников, и не только запустить счёт, а и с математикой, у меня слишком часты ошибки в ней.
Про GPU я буду думать когда будет известно что именно будем считать и будет хоть какая-то оценка требуемого времени и она будет в месяцы. Потому что достичь теоретически возможного ускорения $\frac{1152\times1\cdot10^9}{4\times3\cdot10^9}=96$ кратного ускорения нереально, хорошо если получится на где-то порядок меньше, 10-30 раз. А вот в AVX2 я достигал почти пиковой скорости (на похожих задачах), о чём писал и здесь на форуме. Поиск пятнашки занял 2.5 недели в 4 потока (Ваше везение с выбором диапазона не учитываю) и пока оценка требуемого времени счёта меньше месяца нет смысла тратить неделю-три на оптимизацию под GPU (тем более для меня ускорения вообще не будет из-за отсутствия дискретного GPU).

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

Jon E. Schoenfield интересуется:

Цитата:

Also, if you have time, do you happen to have an upper bound for A292580(15,4)?

Полагаю, это перспективнее, чем искать минимальную пятнашку.

Полагаю да, всего 4 числа и буквально несколько вариантов паттернов (может и один, пока лишь грубо прикинул).
Кстати и Hugo van der Sanden с OEIS интересовался программами, пока думаю что и как ему ответить.

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

на "голом" PARI/GP разница должна быть не столь большая, или нет.

На одинаковых версиях PARI разница должна быть почти строго равна отношению количества потоков и частот. Но есть некоторая разница в скорости между gp64 и gp32 на x64 компах (и эта разница разная для разных алгоритмов, априори не оценишь, у меня какой-то код выполняется в gp32 быстрее, а большинство быстрее в gp64).

kotenok gav в сообщении #1552289 писал(а):

Второй работает, первый нет (Illegal instruction).
Процессор 64-битный AMD A8-7410 APU. AVX2 он, кажется, не поддерживает, да...

Это не смертельно, но не слишком хорошо, AVX2 заметно быстрее (и немного даже чем ненаписанный AVX). При замерах у меня на компе x32 SSE версия примерно втрое медленнее x64 AVX2 (64с против 23с). Плюс почему-то AMD медленнее Intel на этом коде, хотя по тактам на команды настолько больших отличий не видно. Причина непонятна.
Пока Вам следует пользоваться вариантом x32 SSE (тоже выложен в моём облаке) и запускать под gp64 (если винда x64).
Как будет определена задача объясню подробнее что и как запускать.

[VAL]

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

А что прямо сейчас можно посчитать?

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

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

Могу выслать несколько gp-программок для нахождения цепочки 18 чисел по 48 делителей.
Прогноз по времени благоприятный.

Сообщите только сколько потоков вы можете отдать под эти программки.

-- 10 апр 2022, 13:35 --

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

VAL в сообщении #1547813

писал(а):
Ну, основная оптимизация - замена PARI на что-нибудь более быстрое...
И Вы заменили PARI на что-нибудь более быстрое при последней работе с 48-ю делителями?

По сути, да.
Только не у себя на компе, а инициировав этот процесс у других

-- 10 апр 2022, 13:37 --

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

Кстати и Hugo van der Sanden с OEIS интересовался программами, пока думаю что и как ему ответить.

Мы с ним тоже обменивались мнениями.