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

[Yadryara]

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

Ещё, раз код именно такой, то в нём оказывается нет "терапевтики" т.е. отброса цепочек в которых простые 3..53 попали внутрь цепочки и увеличили степень.

Только недавно написал, что у меня она есть.
На 2-й фильтрации терапевтика по 2 и 3.
А на 3-й фильтрации — остальная, до 73 включительно.

И уже ранее писал, что степень 3-ки в нужном месте именно 5-я, так как я делаю 6-кратный шаг, но в отдельных программах задаю остатки 243 и 486 по модулю 729. Но не 0.

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

Этим кажется Антон и занимается.

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

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

[Dmitriy40]

wrest в сообщении #1720549 писал(а):

Так я-то думал что их там просто не может быть

Вот потому я и спрашивал про какой конкретно код речь, у меня и у Антона их быть не может, цепочки с ними исключаются ещё до попыток факторизации. А у Вас оказывается нет.

wrest в сообщении #1720549 писал(а):

Тут сейчас назревает вопрос: а нифиг нам вообще знать из какого паттерна собрана цепочка...
Просто считать делители, да и всё.

Да, разумеется можно и так. Только придётся подсчитать и простые начиная с 2, а это типа лишняя работа уже проведённая при составлении паттерна.
Плюс паттерн нам нужен для получения n0 и m и потом из них n цепочки. Не для факторизации - если не обращать внимания что простые 2..53 из чисел цепочки уже исключены (кроме высших степеней) как раз паттерном.

wrest в сообщении #1720549 писал(а):

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

Так это тоже требует вызова ispseudoprime, причём уже без второго аргумента, ибо ошибка тут уже недопустима! И немало таких вызовов будет впустую, она вернёт 0 и придётся копить делители дальше и снова вызывать её же. Фактически должно получиться что ispseudoprime вызывается не раз на цепочку, а для каждого найденного делителя для любого места в цепочке - чтобы проверить точную недостаточность делителей. Т.е. в разы больше раз на цепочку. А ispseudoprime как раз самая медленная из всех использованных и Вы хотите её вызывать чаще ... Т.е. фильтровать то будет наверное лучше, это да, но зато сильно тормознее.

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

Только недавно написал, что у меня она есть.

А я комментировал не Ваш код, а wrest-а по его ссылке.

[Yadryara]

wrest
Сейчас глянул ваше число. Так оно всего лишь 48-значное. Поиск D(48,21) разве ж актуален... Между 48-ми и 58-значными очень неслабая разница.

Я же вам актуальные наборы дал, для D(96,20). Или у вас не получается запустить?

Специально посмотрел, думаю: разве ж у Дмитрия на 24-странице терапевтики не было?? Да вот же она:

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

for(i=1,oo,\\Не знаю до какого индекса перебирать чтобы накопить 100000 кандидатов на проверку
if(kpod==100000, break);\\Будем копить 100000 кандидатов на проверку
n=n0+m*i*2;\\Получение числа начала кандидата
if((n+#v-1)%3^6==21-19, next);\\Такие n не подходят
if((n+#v-1)%5^3==21-7, next);\\Такие n не подходят
if((n+#v-1)%7^3==21-8, next);\\Такие n не подходят
if((n+#v-1)%11^3==21-14, next);\\Такие n не подходят
if((n+#v-1)%13^3==21-14, next);\\Такие n не подходят
if((n+#v-1)%17^3==21-3, next);\\Такие n не подходят
if((n+#v-1)%19^3==21-2, next);\\Такие n не подходят
kpod++; removeprimes(addprimes());\\Оставшиеся n подходят, будем их проверять и только такие учитываются в 100000

Она конечно весьма ручная, но зато может лучше понятно как делается.

Можете и для моих чисел сделать так же. Только 3^6 проверять не надо.

И цепочки у меня перебираются чуть иначе:

не n=n0+m*i*2

а n = v[1] * (n0 + m * i)

[Dmitriy40]

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

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

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

Может. Но вероятность слишком мала чтобы реально учитывать.
Смотрите, вероятность что в цепочку попадёт квадрат простого $p$ примерно $20/p^2$ (для цепочки длиной 20), а вероятность что в цепочку попадёт куб примерно $20/p^3$. Уже для $p=79$ она всего лишь $20/79^3\approx0.004\%$. И с ростом p она дальше падает. Т.е. с такой вот вероятностью куб простого не будет обнаружен и цепочка пойдёт проверяться дальше и может дойти до факторизации (если она есть в проверках) и куб снова будет найден. Либо, если факторизации нет, то дойдёт до записи в лог и будет перепроверен правильным numdiv и даст правильный valids.
Единственный вариант когда куб может быть полезен - в варианте $p^3q$ вместо требуемых $pqrs$, когда он в паре с ispseudoprime даёт причину отбросить цепочку. В остальных случаях что есть он (и проверили), что нет или не проверили - разницы никакой, цепочка будет проверяться дальше (а время на проверку куба и вызов медленной ispseudoprimt потрачено!). Учитывая редкость такого варианта тратить на него время не считаю выгодным.

[wrest]

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

Я же вам актуальные наборы дал, для D(96,20). Или у вас не получается запустить?

Мне не понравилось, что вы их дали через приват. Неровён час, опубликую

-- 18.03.2026, 19:10 --

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

Т.е. в разы больше раз на цепочку. А ispseudoprime как раз самая медленная из всех использованных и Вы хотите её вызывать чаще ...

Хотел-то пореже, конечно.
Ну оно пореже и вызывается, кстати. Немножко.
"Старая" проверка при помощи em3() 1100107, а новая 1091202
Около 1%
Но теперь учитыватся высшие степени табличных простых, через valuation.
Я проверяю делимость желаемой сигма-ноль (48) на степень простого плюс единица.
Но 48 делится на 2,3,4,6,8,12 соответственно через фильтр проходят 1,2,3,5,7,11 степени (не уверен что степени выше 4 попадаются).
Видимо, надо проверять делимость уже произведения, т.е. "накопленной" сигмы-ноль. Это мысль!
О терминах. Если $n=\prod p_i^{a_i}$ то сигма-ноль это $ \sigma _0(n)=\prod (a_i+1)$

P.S. Действительно, откидывание плохих степеней помогает: количество проверкок простоты уменьшилось на полпроцента. А скорость возросла на 5%

[Yadryara]

wrest в сообщении #1720575 писал(а):

Мне не понравилось, что вы их дали через приват.

Окей, в другой раз сообщу через виват

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

Но вероятность слишком мала чтобы реально учитывать.

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

[wrest]

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

Обычно это делается примерно так: после получения правильного длинного n выполняем x=n+#v-1; if(x%3^6<#v, next); forprime(p=5,53, if(x%p^3<#v, next(2)); ); - всё, это отбросит цепочку если внутрь попали простые 3..53 (те что расставлены в паттерн, в данном случае в паттерне есть 3^5, остальные только в квадратах) и повысили свою степень (на чужие места они попасть не могут, только к себе же). Не знаю почему в Вашем коде этого нет, это прилично фильтрует неподходящие цепочки, ну или я не заметил.

Добавил, скорость возросла в 4 раза
Оно точно лишнее не убирает?

[Dmitriy40]

wrest в сообщении #1720575 писал(а):

Видимо, надо проверять делимость уже произведения, т.е. "накопленной" сигмы-ноль.

Это можно делать и без деления: if(!bittest(mask48, sigma0), next), где маска сформирована заранее например так mask48=vecsum([2^t | t<-divisors(48)]).

wrest в сообщении #1720575 писал(а):

P.S. Действительно, откидывание плохих степеней помогает: количество проверкок простоты уменьшилось на полпроцента. А скорость возросла на 5%

5% уже интересно ... Я думал будет меньше.

wrest в сообщении #1720575 писал(а):

О терминах. Если $n=\prod p_i^{a_i}$ то сигма-ноль это $ \sigma _0(n)=\prod (a_i+1)$

Получается $\sigma _0(n)\equiv\operatorname{numdiv}(n)$.

wrest в сообщении #1720595 писал(а):

Добавил, скорость возросла в 4 раза
Оно точно лишнее не убирает?

Ну ... Она уберёт и допустимые $3^7, 3^{11}, 3^{15}, 3^{23}, 3^{47}$ (как и $p^3, p^5, p^7, p^{11}, p^{15}, p^{23}$ для остальных p, только эти уже не все допустимы), это так важно? Мы же были согласны игнорировать старшие степени ...
Если не игнорировать, то запускайте свою проверку накопления сигмы0 не с 59 (или 79), а сразу с 3, тогда ничего пропущено не будет.

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

Ты знаешь, что отвечать не по шансам, но всё равно колируешь. Ты заплатил чтобы взглянуть на руку или на куб.

Не понимаю. Проигнорировано.

[wrest]

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

Получается $\sigma _0(n)\equiv\operatorname{numdiv}(n)$.

Да. Ну можно наверное говорить и "нумдив" Звучит не очень.

-- 18.03.2026, 21:58 --

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

Если не игнорировать, то запускайте свою проверку накопления сигмы0 не с 59 (или 79), а сразу с 3, тогда ничего пропущено не будет.

Я пробовал, скорость падает катастрофически.

-- 18.03.2026, 21:59 --

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

Ну ... Она уберёт и допустимые

У меня "терапевтика" убирает 73% цепочек.
Код:

? {len=21;k_start=0;k_len=10^7; q=0;
my(n0=283938699868309713921641266159023371777169):int;
my(m=229403502054304075118105309394590566946400):int;
for(k:small=k_start,k_start+k_len-1, \\ идём по цепочкам
\\ "терапевтика"
   n=n0+2*k*m+len-1;
   if(n%3^6<len, q++;next);
   forprime(p=5,53, if(n%p^3<len, q++; next(2)));
   );
print(q);}

7278222
time = 36,391 ms.
?

[Yadryara]

Так и должно быть:

? 1 - vecprod(primes([3,53]) - vector(15,i,1)) / vecprod(primes([3,53])) + .
%9 = 0.72782593143153891716165330773181968809