Как писать быстрые программы

[wrest]

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

Для цепочек длиной от 10 с 12-ю делителями обязательным было число $32p$. А нет ли аналогичного обязательного числа для длинных цепочек с 48-ю делителями?

Так VAL же, если я не ошибаюсь, писал по теме в https://doi.org/10.48550/arXiv.1811.05127
У него и maxal и надо спрашивать.

[Yadryara]

wrest, ровно наоборот. Я спрашиваю у тех, кто ещё вроде не очень разбирается в этих задачах, например у Вас, чтобы помочь освоиться.

[wrest]

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

Я спрашиваю у тех, кто ещё вроде не очень разбирается в этих задачах, например у Вас, чтобы помочь освоиться.

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

[Yadryara]

Ну вот вариант анонсированной программы поиска цепочек из 5 последовательных чисел по 6 делителей каждое:

{t0=getwalltime();
print; ost=vector(4); cep=vector(9); kol=vector(5);
inter = 10^19; shag = lcm([2, 9, 25]);
por = [0,3,2,4,1];
ost[1] = lift(chinese([Mod(1,2),Mod(2,9),Mod( 6,25)]));
ost[2] = lift(chinese([Mod(1,2),Mod(2,9),Mod(19,25)]));
ost[3] = lift(chinese([Mod(1,2),Mod(7,9),Mod( 6,25)]));
ost[4] = lift(chinese([Mod(1,2),Mod(7,9),Mod(19,25)]));
for(i=1,#ost, print(i,".   ",ost[i]));print;
print(shag,"     ",#ost,"      ",round(shag/#ost));print;
fin = sqrt((inter+1)/2)/shag;
for(i=0,fin,
for(no=1,#ost,
kan = 2*(ost[no]+i*shag)^2-1;
kcc=0; for(j=1,5, if(numdiv(kan + por[j]) <> 6, next(2), kcc++));
kpod++;kol[kcc]++;
print(kpod,".    ",i,"     ",kan,"     ",kcc,"     ",no);
));
print;print(strtime(getwalltime()-t0));print;
}quit;

Замените в ней 4 символа и ускорьте в 2-3 раза. Условие нахождения всех 19-ти пятёрок до 1e19 прошу соблюдать.

[Yadryara]

Эту программу удалось ускорить в 87 раз, по-прежнему на PARI. Но пока не могу показать.

[Dmitriy40]

(Минутка юмора)

Ну, 87 раз не предел, можно ускорить в миллион раз , заменив все циклы на один:
foreach([71040881,84896719,...,2197567969],p, kan=2*p^2-1; ... );
Заодно и все проверки можно ликвидировать, сразу печатать результат.

-- 28.09.2025, 20:10 --

Заодно поделюсь забавным и непрактичным методом ускорения.
Предположим у нас есть три места с формулой $pqrs$ (например для 48 делителей после размещения простых в квадратах), тогда кандидата можно отбросить проверив лишь делители до корня четвёртой степени для всех мест (если хотя бы где-нибудь не найдётся - значит там делителей не может быть ровно 16).
Непрактично потому что корень четвёртой (и 5-й и 6-й) степени - обычно слишком велик для прямой проверки делителей. К тому же в PARI нереально (насколько я в курсе) сделать поиск лишь одного делителя, максимум можно ограничить величину делителей в factor(x,sqrtnint(x,4)) (или другую степень), но это приведёт к полному перебору простых в этом диапазоне, в отличие от нормальных методов факторизации, и для более-менее больших чисел (с пределом выше скажем 1e9) станет очень долгим.

[gris]

Свыше De profundis был передан универсальный скрипт с проверкой на подозрительном числе. А чего это у него три шестёрки?

gp >{\\find chains of k consecs with the numdiv m in(N1,N2).
m=24;
k=11; \\ k < 150:(
N1=17707503 250 000 000; N2=N1+10^7;
kk=0;
forstep( i=N1,N2,k,
  if(numdiv(i)==m,
    for(j=1,150, if(numdiv(i+j)!=m,j2=j-1;break) );
    for(j=1,150, if(numdiv(i-j)!=m,j1=j-1;break) );
    if(j2+j1+2>k, printf("(%d ... %d) length=%d\n",i-j1,i+j2,j2+j1+1) );
  );
);
}
(17707503256664346 ... 17707503256664356) length=11

+++ Dmitriy40, я чувствовал, как просится while, но запутался в нём:) Не любит он меня. И брат его — until.

[Dmitriy40]

gris
Я расширение цепочки от данного числа x до цепочки [a,b] обычно делаю так:
a=x; while(numdiv(a-1)==24, a--);\\Один вариант цикла
b=x; while(numdiv(b++)==24, ); b--;\\Другой
len=b-a+1;
Разумеется ради скорости можно добавить предварительные проверки.

+++ gris
while очень прост: пока условие верно (не равно нулю) (проверяется перед телом цикла) выполняет тело цикла. until наоборот, выполняет тело цикла пока условие в итоге (проверяется после тела цикла) не станет верным (не равным нулю). Поэтому while (как кстати и forXXX) может не выполниться ни разу, until же выполнится минимум один раз (до первой проверки условия).
Я until практически не применяю, путаюсь с ним, while/for+if+break хватает.

+++ gris
Ещё, чтобы не плодить уровни вложенности и искать закрывающие скобки в конструкциях вида
if(f,
...
);
я предпочитаю то же самое делать делать так:
if(!f, next);
...
Повышается наглядность.

+++ gris
Можно наверное чуть ускорить программу добавив проверку (выделена курсивом) что подходящее число уж точно не одно:
if(numdiv(i)==m && (numdiv(i-1)==m || numdiv(i+1)==m),
Следующие проверки не будут выполняться если оба соседа неподходящи.

-- 28.09.2025, 22:03 --

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

Условие нахождения всех 19-ти пятёрок до 1e19 прошу соблюдать.

Этого недостаточно, вот код отрабатывающий за 0.05с и тем не менее находящий все 19 пятёрок:

shag=98789231; ost=[6505035, 10837466, 21584711, 24204887, 27805835, 36465414, 44511811, 48396554, 54144785, 64849835, 68781488, 70411790, 71040881, 83326440, 84896719, 85150292, 98290304, 98385133];

Всё остальное остаётся как есть.

Разумеется это не считается решением задачи, ведь очень много пятёрок в любом другом диапазоне будет пропущено. Однако хорошая иллюстрация недостаточно корректного условия.

[Yadryara]

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

Однако хорошая иллюстрация недостаточно корректного условия.

Просто недостаточное условие. Тут другое гораздо интереснее. Ведь это проверяется только один паттерн из 4-х возможных. Но пока почему-то находятся все известные решения из A141621:

Интервал   Пятёрок                 Время
0 — 1e17         2                971 ms
0 — 1e18         4              3,032 ms
0 — 1e19        19              9,782 ms
0 — 1e20        39             31,018 ms
0 — 1e21       102       1min, 43,272 ms
0 — 1e22       226       5min, 52,275 ms
0 — 1e23       532      18min, 50,247 ms

[Yadryara]

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

Замените в ней 4 символа и ускорьте в 2-3 раза.

Намекал на изменение порядка. Заменив порядок проверки на противоположный (por = [0,3,2,4,1] на por = [1,4,2,3,0]) можно получить такое ускорение. Для разных интервалов оно разное.

gris
Это что же у Вас за скорость? Для D(6,5) Ваша прога проверила интервал 0 — 1e9 за 2min, 46,949 ms.
Как видно из таблицы выше, гораздо быстрее проверился интервал 0 — 1e21.

Это что, Ваша прога медленнее в 1.6 триллиона раз???

{t0=getwalltime();
print;
m=6; k=5; 
N1=10; N2=N1+10^9;
kk=0;
forstep( i=N1,N2,k,
  if(numdiv(i)==m,
    for(j=1,150, if(numdiv(i+j)!=m,j2=j-1;break) );
    for(j=1,150, if(numdiv(i-j)!=m,j1=j-1;break) );
    if(j2+j1+2>k, printf("(%d ... %d) length=%d\n",i-j1,i+j2,j2+j1+1) );
  );
);
print;print(strtime(getwalltime()-t0));print;
}quit;

[Dmitriy40]

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

Это что, Ваша прога медленнее в 1.6 триллиона раз???

Ну так Вы сравнили, линейный перебор с мелким шагом (всего 5, причём они довольно часто оказываются правильными и проверка уходит вглубь) и квадратичный перебор у себя! Разумеется квадратичный будет быстрее на порядки, и чем больше диапазон, тем больше порядков. Грубо говоря, за время которое линейно проверяются 1e9, квадратично можно проверить 1e18. А за 1е10 можно проверить 1е20. Плюс разница в величине шага (5 и 450/4) даёт ещё почти два порядка разницы, вот и получается что за время 1e9 линейно можно проверить 1e20 квадратично. Остальную разницу можно списать на разную скорость проверки кандидатов. Так что ничего тут удивительного не вижу.

-- 29.09.2025, 15:01 --

Даже такая простая программа квадратичного перебора

forprime(p=7,sqrtint(1e18/2), x=2*p^2;
if(!isprime(round(x/25)) || !isprime(round(x/9)), next);
a=x; while(numdiv(a--)==6,); a++; b=x; while(numdiv(b++)==6,); if(b-a>4, print(a)))

до 1е18 перебирает всего за 23с. А ведь это как раз 1e9 интервал итераций цикла.
Зато цикл идёт только по простым, которых сильно меньше чем каждое 5-е натуральное число, плюс более быстрая предпроверка isprime перед относительно долгим numdiv - всё это и даёт ускорение с 3м (для аналогичной линейной выше) до 23с.

[Dmitriy40]

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

Тут другое гораздо интереснее. Ведь это проверяется только один паттерн из 4-х возможных. Но пока почему-то находятся все известные решения из A141621:

Потому что Вы ошибаетесь считая все 4 паттерна (c 9 и 25) возможными, возможен только один, который и даёт решения.
Паттерны $?,2^2p,3^2p,2p^2,?$ запрещены по модулю 9 (остатки $2p^2\bmod 9 \ne 1$) и по модулю 3, а паттерны $5^2p,2p^2,?,2^2p,?$ запрещён по модулю 25 (остатки $2p^2\bmod 25 \ne 1$) и по модулю 5. Так что даже если 3 и 5 будут без квадратов (т.е. понадобятся большие простые в квадратах), паттерн всё равно будет только с 4,3,5 на тех же местах.

[Yadryara]

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

Так что ничего тут удивительного не вижу.

Как это?
Зачем же gris-у понадобился-то такой жутко медленный перебор, ведь тема не про универсальность, а про скорость?

Интересно что gris ответит. Может не понимал что это будет настолько медленно?

Арифмост строить долго, если нет навыка, но зато прокатиться по нему можно с ветерком:

VAL (который молчит почему-то), как понимаю, нашёл два десятка таких пятёрок. И в OEIS три исследователя нашли в общей сложности 2000 пятёрок. Впс за 3 три часа в одном потоке — 3493 штуки.

Можно и до 10 тысяч догнать и заслать туда, но лень, интереснее с другими тремя паттернами разобраться.

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

Потому что Вы ошибаетесь считая все 4 паттерна (c 9 и 25) возможными, возможен только один, который и даёт решения.

Нет это Вы ошибаетесь, что я так считаю. Перечитайте ММ77, я недавно давал ссылку.

Не 16 паттернов, а 4. С 3 и 5, с 3 и 25, с 3 и 9, с 9 и 25. Хотя может и лишь один, перепроверяю.

[Dmitriy40]

Если же речь про 4 паттерна включая и без 9 или 25, то в них нужны два-три больших простых в квадратах, что встречается крайне редко. Хотя и не запрещены.

-- 29.09.2025, 15:51 --

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

Как это?
Зачем же gris-у понадобился-то такой жутко медленный перебор, ведь тема не про универсальность, а про скорость?

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

[VAL]

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

VAL (который молчит почему-то), как понимаю, нашёл два десятка таких пятёрок.

Вообще-то, я не молчу.
А конкретно на этот вопрос не отвечаю, поскольку все пятерки я нашел еще в 2007 (кажется) году, когда придумал задачу MM77.
Про то, что я не первый придумал эту задачу, я узнал из комментов участников Марафона.
Эти пятерки я искал на медленном компе, используя медленный maple. А времени потратил, разумеется, не помню сколько.
Общей задачей нахождения $M(k)$ я увлекся лет на 7 позже, когда предложил ее Василию Дзюбенко в качестве школьного исследования.
Василий исследование (а также школу, МФТИ и магистратуру) закончил, а я все продолжаю

Лень было писать этот мемуар, но учитывая Вашу настойчивость, решил отписаться