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

[Yadryara]

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

В этом Вы ошибаетесь: "Ну и шаг в паттернах весьма быстро возрастает: на 22%, на 35%, на 61%, на 75%, ...", вот табличка увеличения шага при замене одного любого числа на другое:

Нет, это Вы ошибаетесь.

Что такое $1.1081$ в Вашей таблице? Это $\frac{41}{37}$ не так ли ? А почему Вы в квадрат не возвели? И ни одну из дробей не возвели? Вот же формула шага:

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

$$2^63^3\prod_{i=3}^{12}p_i^2=Step$$

Разве не так надо считать:

$$\left(\dfrac{41}{37}\right)^2 \approx 1.2279$$

Это я ещё пол взял, а так-то ближе к 23%.

[Yadryara]

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

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

Ну почему gp-программок-то ? Ведь уважаемый Dmitriy40 убедительнейшим образом доказал, что нужен симбиоз ассемблера и gp.

Зачем же ехать на карете со скоростью 8 метров в секунду вместо того чтобы лететь на ракете со скоростью 8 километров в секунду ??

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

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

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

А почему не у себя на компе?

[Dmitriy40]

Yadryara
Да, правы, про квадрат забыл. Вот исправленная табличка:

? forprime(p=41,97, print1("\t",p)); print; forprime(x=17,37, print1(x,":"); forprime(p=41,97, printf("\t%6.3f",(p/x)^2)); print)
        41      43      47      53      59      61      67      71      73      79      83      89      97
17:      5.817   6.398   7.644   9.720  12.045  12.875  15.533  17.443  18.439  21.595  23.837  27.408  32.557
19:      4.657   5.122   6.119   7.781   9.643  10.307  12.435  13.964  14.762  17.288  19.083  21.942  26.064
23:      3.178   3.495   4.176   5.310   6.580   7.034   8.486   9.529  10.074  11.798  13.023  14.974  17.786
29:      1.999   2.199   2.627   3.340   4.139   4.424   5.338   5.994   6.337   7.421   8.191   9.419  11.188
31:      1.749   1.924   2.299   2.923   3.622   3.872   4.671   5.246   5.545   6.494   7.169   8.242   9.791
37:      1.228   1.351   1.614   2.052   2.543   2.718   3.279   3.682   3.893   4.559   5.032   5.786   6.873

И всё равно два числа под замену появляются уже при шаге $\frac{41\times43}{37\times31}\approx2.363$.
Но так да, выходит всего примерно 156 вариантов замен, 300ч=2недели на компиляцию плюс счёт (мне примерно столько же для проверки по 1e35 в расчёте на везение), уже более разумно, да плюс повезти может и крупно ... А если не повезёт, то 156 раз по 2.5 недели мне, это до 8 лет счёта. Такую задачу надо изначально ставить по другому и оптимизировать не перебор каждого паттерна в глубину, а ускорять перебор всего множества паттернов. Это практически полное переписывание программы.
В силу этого и остальных пунктов я заниматься не буду.

-- 10.04.2022, 15:35 --

Yadryara
Не обязательно ассемблер, для расчётов на GPU нужен С/С++ (про другие не знаю), ассемблера там вообще нет. А кроме языка ещё и понимание принципов работы GPU. Впрочем в сети полно примеров как надо делать. А если не упираться в CUDA, то при использовании кроссплатформенного OpenCL вычисления могут идти и на CPU (не на встроенном видеоядре, а именно на основных вычислительных ядрах), и на GPU (и от AMD в том числе, и на встроенных в CPU), и даже одновременно и там и там.

[Yadryara]

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

Да, правы, про квадрат забыл.

Но как это можно было забыть ??

Вы же в этом же посте писали:

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

формат КМК

И что означает последняя буква "К" ?

Кроме того, я на всякий случай, специально чтоб Вы не забыли, не ленился писать слово "подквадратные". Например:

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

подквадратные 17-37

Неужто Вы опять невнимательно читали мои посты? Я Ваши стараюсь читать внимательно.

Так Вы и сами писали:

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

Программа понятия не имеет про все эти подквадратные числа

Но Вы-то имеете понятие и прекрасно знали, что в паттернах КМК37-11 все эти числа стоят в квадратах...

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

Не обязательно ассемблер,

Так я и не говорил, что обязательно.

Лично мне представляется гораздо более простым разобраться как сделали именно Вы. Потому что я могу задавать вопросы автору и знаю, что Вы с готовностью идёте на контакт и не склонны бросать дело на полдороге. Что и позволило добиться успеха в поиске 15-шки.

[VAL]

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

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

писал(а):
Могу выслать несколько gp-программок для нахождения цепочки 18 чисел по 48 делителей.
Ну почему gp-программок-то ? Ведь уважаемый Dmitriy40 убедительнейшим образом доказал, что нужен симбиоз ассемблера и gp.

Зачем же ехать на карете со скоростью 8 метров в секунду вместо того чтобы лететь на ракете со скоростью 8 километров в секунду ??

Но у нас же несколько разных задач.
Насколько я понимаю (и Дмитрий это подтверждает) нахождение цепочек по 36 делителей хорошо ложится на его идеи (или наоборот, его идеи подходят для этой задачи). А, например, 19 чисел по 48 делителей я нашел за неделю, не используя ассемблерных кодов.

Мне представляется, что найти 18 чисел по 24 делителя вполне вероятно удастся быстрее, чем разработать код на ассемблере.
Я же написал, что прогноз по времени обнадеживающий.

[Yadryara]

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

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

А нахождение цепочек по 48 делителей плохо ложится на его идеи? Я ведь только что уже отметил:

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

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

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

[VAL]

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

А нахождение цепочек по 48 делителей плохо ложится на его идеи?
[..]
И это касается самого разного количества делителей, ведь проверка огромных чисел на простоту нужна во всех случаях.
Стало быть, не может такого быть, чтобы идеи Dmitriy40 не принесли ощутимого ускорения и для этой задачи и для многих других аналогичных. Так что подход надо пересматривать.

Сравните.
Оптимальный вариант при поиске пятнашки по 12 делителей: 11 из 15 проверяемых чисел должны быть простыми.
Оптимальный вариант при поиске двадцатки по 48 делителей: 3 из 20 проверяемых чисел должны быть простыми.

Разумеется, можно организовать поиск так, что все 20 проверяемых чисел должны быть простыми. Скорость проверки возрастет в тысячи раз.
Только вот вероятность успеха упадет в триллионы или квадрильоны раз.

[Yadryara]

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

Оптимальный вариант при поиске двадцатки по 12 делителей: 3 из 20 проверяемых чисел должны быть простыми.

Подождите, не надо про другое. Да и что это за 20-ка по 12 делителей?

Речь шла про 48 делителей. Вы в джипи прогах проверку чисел на простоту используете ? Если да, то для скольких чисел?

[VAL]

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

Да и что это за 20-ка по 12 делителей?

Исправил.

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

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

Для трех (там же написано). Причем мелкие делители отсекаются, еще до проверки на псевдопростоту, что ускоряет проверку в 3 раза.

[Dmitriy40]

Три числа тоже можно проверять (причём тогда можно порог простых повысить до 32768), и это даже даёт эффект фильтрации, но по сравнению с 11-ю числами на выход пробивается слишком много кандидатов. Плюс для длинных цепочек числа большие и они заметно чаще не имеют малых делителей (что и проверяет моя программа), т.е. с возрастанием чисел качество фильтрации ухудшается.

По М(36)=15.
У меня получается что в паттерны можно разместить 20 чисел, т.е. количество вариантов паттернов немногим меньше $19!$, что ну совершенно неподъёмно. Кроме того, если подставлять все 20 чисел, то это простые по 101, т.е. минимальный шаг выходит $2^{5}\prod\limits_{p=3}^{101} p^2 \approx 10^{77..82}$, PARI при попытке numdiv страшно тормозит (ждал несколько минут, не дождался), isprime правда работают быстро, но тут уже моя фильтрация слишком слаба, из десятков тысяч кандидатов ни один не прошёл даже трёх isprime (часто не проходят даже 32p).
Попытка уменьшить количество подставляемых чисел увеличением степени с квадрата до 5 или 9 резко раздувает шаг, до $10^{125}$ и более, а вероятность что-то найти похоже действительно падает (не учитывая даже уменьшение частоты простых).
Если же на места произведения квадратов простых ничего не подставлять, то 99.99% найденных цепочек имеют на этих местах неправильное количество делителей (кажется вообще ни разу не видел чтобы обнаружилось произведение простых в квадратах там где не потребовал).
Пока не знаю что со всем этим делать.
На глобальное недопонимание указывает и недоумение как получена M(30)=5, там же простое под квадратом имеет 27 цифр, как его подобрали то ...

[Yadryara]

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

Для трех (там же написано).

Это сейчас там написано "48 делителей". А когда я задавал свой вопрос, было написано "12 делителей". Да, можно было догадаться, что вместо "12" надо читать "48". Но зачем путаницу-то плодить?

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

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

Причем мелкие делители отсекаются, еще до проверки на псевдопростоту, что ускоряет проверку в 3 раза.

Ну то есть идея Дмитрия используется и даёт заметный эффект.

Dmitriy40, я правильно понимаю, что с Асмом было бы ещё в разы быстрее?

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

Мне представляется, что найти 18 чисел по 24 делителя вполне вероятно удастся быстрее, чем разработать код на ассемблере.

А кто-то с этими 18-ю числами сильно торопит?

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

У меня есть код (на PARI) для поиска цепочки из 15 чисел. Но прикидка показывает, что на моем (довольно быстром) компе на это потребуется лет 7-10.

После того как Dmitriy40, найдя пятнашку, сэкономил Вам 7-10 лет, уж точно можно пока не торопиться и спокойно разобраться.

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

Я же написал, что прогноз по времени обнадеживающий.

Так озвучьте же этот прогноз. Мы с Дмитрием показывали выше как считать вероятности и указывать результаты в удобной форме.

[kotenok gav]

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

ассемблера там вообще нет

Вообще, он есть (SPIR-V)...

-- 11 апр 2022, 17:57 --

CUDA работает только на NVidia.
Можно использовать или OpenCL, или Vulkan compute shaders. Они оба поддерживают SPIR-V, да.

[VAL]

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

На глобальное недопонимание указывает и недоумение как получена M(30)=5, там же простое под квадратом имеет 27 цифр, как его подобрали то ...

Очень просто. Сначала берем $a=2\cdot 13^2$ и подбираем систему модулей вида $m_i=p_i^4q_i^2$, чтобы сравнения $ax^2-1\equiv 0 (m_1),\quad $ax^2+1\equiv 0 (m_2), \quad $ax^2+2\equiv 0 (m_3),\quad $ax^2+3\equiv 0 (m_4)$ были разрешимы.
Затем с помощью КТО находим $256=4^4$ начальных приближений $x$ по модулю $m=m_1m_2m_3m_4$.
Остается подобрать $i$, чтобы числа $x+im,\quad (a(x+im)^2-1)/m_1,\quad (a(x+im)^2+1)/m_2,\quad (a(x+im)^2+2)/m_3$, \quad $ (a(x+im)^2+3)/m_4 $ одновременно были простыми.

-- 11 апр 2022, 11:16 --

Антон будет ругать меня за оффтоп, но как же не похвастать...

Только что нашел 7-ку чисел, имеющих по 116 делителей (это максимальная длина цепочки).
Для этого пришлось раскладывать на множители заведомо составные 172-значные числа (чего я делать не умею)

[Dmitriy40]

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

Ну то есть идея Дмитрия используется и даёт заметный эффект.

Всё наоборот, это идея как раз VAL, в его программах она с самого начала, в теме её называем проверкой по индексу.

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

Dmitriy40, я правильно понимаю, что с Асмом было бы ещё в разы быстрее?

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

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

Вообще, он есть (SPIR-V)...

Это не ассемблер: "SPIR-V is a high-level intermediate language,". На это же намекает и буква P в обозначении, portable. Всё что не привязано к конкретной архитектуре уже однозначно не ассемблер. И да, я прекрасно понимаю все минусы ассемблера.
Ассемблером является скорее ARB, но про него впервые слышу если честно и надо посмотреть как оно работает и работает ли вообще на новых GPU, пока впечатление что оно устарело лет на 10, ещё когда конвейеры были специализированными (вертексный и текстурный), а не GPU, и больше не поддерживается.

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

CUDA работает только на NVidia.

Я в курсе. Зато она проще и более тонко можно настроить (привязаться к конкретной аппаратуре). Пока из откликнувшихся на мою просьбу озвучить модель видюхи известно о наличии лишь одной GPU именно Nvidia.
Если и буду писать под GPU, то 90% что на OpenCL, именно ради совместимости/переносимости (к тому же его могу проверять (но не оптимизировать) на своём компе со встроенным в проц видеоядром).

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

Очень просто.

Спасибо, чуть позже вникну.

[Yadryara]

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

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

Ну то есть идея Дмитрия используется и даёт заметный эффект.

Всё наоборот, это идея как раз VAL, в его программах она с самого начала, в теме её называем проверкой по индексу.

Сомневаюсь. Давайте-ка попросим уважаемого VAL выложить современную прогу-48 и сравним её со старой прогой-12.