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

[VAL]

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

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

Что-то никто не впечатлился моей семеркой...
Зацените первое число: 1443057619548759324563885307547336300159955669896378237626325853026937254054590483069867763714829098682111332988609699003926929222870960480012656760045215487480163574218749

-- 11 апр 2022, 13:18 --

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

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

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

По поводу чисел имеющих по 48 делителей. После пробного запуска изучил статистику и обнаружил закономерность, которую пока не могу объяснить.
Я эмпирически нашел наиболее вероятное количество делителей после отделения тех, которые гарантированы методом поиска.
В исследуемом диапазоне картина оказалась такая:

[0.07105, 0.22585, 0.30775, 0.22905, 0.11330, 0.041650, 0.01135]

Это вероятности того, что интересующее нас число будет иметь: 1; 2; 3; 4; 5; 6; более 6 различных простых делителей.
Соответственно система модулей подбиралась так, чтобы как можно больше исследуемых чисел должны были бы иметь по 3 делителя.
Вот один из соответствующих паттернов:

[7*29^2, 3*2^2, 13*17^2, 2*5^2, 3^2, 2^5, 19^2, 11*(2*3)*7^2, 5*31^2, 2^2, 3*37^2, 2*41^2, 23^2, 5*2^3*3^2, 7*43^2, 2*13^2, 3*47^2, 2^2, 5*11^2, 17*(2*3)*53^2]

Так вот, пробные запуски надежно согласуются с ожидаемой картиной, за исключением позиции $5\cdot 11^2$. В ней требуемое число множителей возникает в 2 раза реже, чем в остальных аналогичных.
Наверняка этому есть объяснение, которое я пока не вижу.

[Dmitriy40]

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

Сомневаюсь.

Вот его кусок кода с первой страницы темы с if, про который речь:

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

{for(i=i1,i2,if(i%5!=1 && i%7!=2 && i%11!=5 && i%13!=4 && i%17!=0 && i%19!=4 && i%23!=4 && i%29!=11 && i%31!=9 && i%37!=17, p=p1+i*m;

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

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

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

И это не совсем так, к простым 2-37 я добавляю лишь одно простое 41 для x32 SSE версии (из-за ограничения на размер требуемой при работе памяти) и два простых 41 и 43 для x64 AVX2 версии (причём добавка состоит не в проверке индексов, а в разворачивании цикла 2х3х41х43 итераций для x64 AVX2 и выкидывании ненужных итераций из таблиц, т.е. по этим простым никаких проверок при работе вообще не производится, они все выполнены на этапе компиляции и формировании таблиц), остальные простые по индексам не проверяются (опять же из-за ограничения по памяти).
А, да, "ограничение на размер памяти" имеется в виду что при увеличении требуемой памяти выше некоего порога (для каждого проца своего) начинаются тормоза, перекрывающие выигрыш от уменьшения объёма вычислений, и этот порог лишь немногим больше максимального размера кэша проца, вовсе не гигабайты основной памяти (и потому сколько имеется гигабайт памяти вообще неважно, лишь бы винде хватало, в том числе и на кэш всех паттернов, программе же хватит и десятка мегабайт).

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

Что-то никто не впечатлился моей семеркой...

Думаю не все поняли в чём сложность, PARI то и с тысяче-цифровыми числами работает на ура. Лично я больше впечатлился той 47-ми страничной таблицей с кучей цепочек разной длины.

[VAL]

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

Думаю не все поняли в чём сложность, PARI то и с тысяче-цифровыми числами работает на ура. Лично я больше впечатлился той 47-ми страничной таблицей с кучей цепочек разной длины.

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

[Dmitriy40]

(Таблица)

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

Найденное число уже занесено в упомянутую таблицу.

Простите, если и занесено, то файл не выложен: ссылка со страницы по прежнему ведёт на файл от 7.4.22 без этого числа.

Про PARI согласен, хотя для чисел, действительно являющихся решениями, и factor и numdiv отрабатывают быстро (числа-то в разложении или простые, или относительно небольшие и в малой степени), а вот для "неправильных" чисел беда ...

[RTM]

Всем привет!

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

[Yadryara]

RTM в сообщении #1552363 писал(а):

Открыт к новым предложениям.

Приветствую Вас! Сейчас пилим софт и совсем скоро приступим к штурму 6-ти мировых рекордов для 12-ти делителей:

$ T(6,10) \leqslant 709132549978045925147\hspace{3.34cm}\text{Jon E. Schoenfield}$

$ T(6,11) \leqslant 10433262941295560748369948 \hspace{2.48cm} \text{Jon E. Schoenfield}$

$ T(6,12) \leqslant 188398449265501253956617945 \hspace{2.33cm} \text{Jon E. Schoenfield}$

$ T(6,13) \leqslant 1932741770848588276411450776345 \hspace{1.63cm} \text{Jon E. Schoenfield}$

$ T(6,14) \leqslant 4894738132059472206526016135636567642 \hspace{.57cm} \text{Dmitry Petukhov}$

$ T(6,15) \leqslant 66387422053662391209161093722597723545 \hspace{.4cm} \text{Dmitry Petukhov}$

[VAL]

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

Простите, если и занесено, то файл не выложен:

Выкладывал...
Но случайно повторно выложил старый.
Надеюсь, теперь удалось.

[Yadryara]

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

Сейчас пилим софт и совсем скоро приступим к штурму 6-ти мировых рекордов для 12-ти делителей:

Ну это я конечно малость того, преувеличил. Ведь рекордные непрерывные 10-ки, 11-ки и 12-ки меньше шага. Так что их пока этим способом улучшить не удастся. Но зато напомнил об актуальных минимумах и их авторах.

[Dmitriy40]

Для T(6,10) шаг составляет почти 1e17 (если ограничиться $2^3$) или почти 4e17 (если поставить $2^5$), что в несколько тысяч раз меньше найденной цепочки. Двойка занимает два места в степени выше первой, и ещё 8 простых можно разложить в квадратах, итого $8\prod_{p=3}^{23}p^2\approx9.954\cdot10^{16}$. Как раз про этот случай я выше говорил что прикидывал как доказать минимальность ...

[Dmitriy40]

Досчитался последний диапазон в низинах до 1e38, всё объединил в один файл Result.0e38.txt и выложил в облако по прежней ссылке (предыдущие логи убил).
Четвёртой пятнашки так и не нашёл.
Удивительным образом повезло товарищам выбрать интервалы как раз с пятнашками ... может они что-то знали?
Напомню (чтобы не затерялось в теме): данные в файле от трёх участников — меня, EUgeneUS, RTM, хотя пятнашку искали также и VAL и Yadryara , а последний ещё и активно занимался математикой и находил мои косяки.

[VAL]

Пр просьбе Шёнфилда улучшил верхнюю оценку для T(15,4) и T(15,5).
Теперь это 1542481711619246942245033414190583122 и 666943262916699588264541522223408446129442752832102497
Причем первая, скорее всего неулучшаема.
Тем временем Шёнфилд куда-то исчез (до этого писал по 5 раз на дню), проигнорировал мои улучшения и опубликовал свою старую оценку.
А обновление A119479 (целых 12 новых членов) так и болтается в черновиках

[kotenok gav]

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

Пока из откликнувшихся на мою просьбу
озвучить модель видюхи известно о наличии лишь одной GPU именно Nvidia.

У меня AMD Radeon R5 Graphics (встроенная).

[Dmitriy40]

kotenok gav
Спасибо, вот значит CUDA и отпадает.
Для справки, очень грубая оценка пиковой скорости: 256 потоков на 0.5ГГц это 128Г, основной проц имеет 4 потока на 2.2ГГц, это 8.8Г, ускорение (теоретическое!) $128/8.8=15$ раз. Практическое — в несколько раз, 2-4. И за него придётся ещё сильно побороться.
Плюс встроенные GPU сильно ограничены скоростью памяти (как и проц), что не позволяет "разменять" память на скорость (ускориться ценой резкого увеличения требуемой памяти, до гигабайтов).
Когда я пытался применить свою Intel HD4600 как GPU для очень похожей задачи, то вместо $20\times1\cdot10^9 / 3\cdot10^9=6.7$ раз теоретического ускорения (на один поток проца) получил замедление вчетверо. Т.е. один и тот же OpenCL код на GPU выполнялся конечно быстрее чем на CPU, но до асм+AVX2 не дотягивался 15-ти кратно (в 4 потока CPU если). Сейчас нашёл и ещё раз запустил, да, OpenCL на CPU в 4 потока даёт 0.8млрд итераций/с, на GPU в 20 потоков 0.9млрд, а 4 потока асм+AVX2 дают 12млрд. Правда OpenCL код почти не оптимизирован ...

[Dmitriy40]

Прикинул тут про M24=31, оно попроще чем M36.
Везде нужен квадрат, двойка даёт 1 высокую степень (хоть 11, хоть 7, хоть минимальную 5), 2 куба и 4 квадрата, остаётся от 26 мест под квадраты. Тройка даёт или три квадрата, или два квадрата и степень выше, остаётся 23-24 места под квадраты. Пятёрка может дать тоже два квадрата и оставить минимум 21 место под другие квадраты. Т.е. шаг никак не может быть меньше восьмикратного квадрата произведения простых 2-89 (21шт начиная с 7), или примерно $10^{70}$.
Расставив 2,3,5 в 11-й степени (ради уменьшения количества вариантов паттернов) и добавив несколько чисел в квадратах, можно получить до 20 проверяемых числа (из которых похоже можно 13-15шт взять непрерывными в центре) при более-менее разумном количестве паттернов. 31 так вряд ли найдётся, шаг выйдет слишком малым, да и совпадение десятка чисел по 24 делителя (пусть даже наиболее вероятных по три простых в каждом) слишком невероятно ...
Правда это оценки очень на глаз, могу и сильно ошибаться.

[VAL]

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

Прикинул тут про M24=31, оно попроще чем M36.

Очень парадоксальное заявление!
Хотя, если иметь в виду составление паттерна... В принципе у меня имеется готовый. Но я для M(36) могу составить. Проблема-то не в этом.
Если вести речь о достижимости цели... Тогда M(48) будет намного реальнее. Хотя тоже абсолютно нереально.
А M(36), конечно, тоже более чем проблематично. Но, если, например, допустить создание подобного проекта на PrimeGrid, то, полагаю, вполне реально.