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

[vicvolf]

Huz в сообщении #1703362 писал(а):

However if you are looking for $p^2q$ then the probability for a given $n$ is something more like $\sum_{p \in \mathbb{P}}{ \frac{1}{p^2 \ln{n/p^2}} }$, i.e. the probability over all primes in the appropriate range that a) $n$ is divisible by $p^2$, and b) the result of the division is a prime. That's a much higher chance than for $p^2$, and it grows again for $p^2qr$ - and of course more possibilities means more work searching through them all.

If $n=p^2q$ then $q=n/p^2 \geq 2$ and the probability is $P(x) \sim \sum_{p^2 \leq n}\frac {1}{p^2\ln(n/p^2)}$.
First, note that the condition $p^2 < n $ is equivalent to $p < \sqrt{n} $. Also, we can write:
$\ln(n/p^2) = \ln n - 2\ln p.$
For large$n $ and small$p $, the term$2\ln p $ is small compared to$\ln n $, so we can expand:
$\frac{1}{\ln(n/p^2)} = \frac{1}{\ln n} \cdot \frac{1}{1 - \frac{2\ln p}{\ln n}} = \frac{1}{\ln n} \left(1 + \frac{2\ln p}{\ln n} + \left(\frac{2\ln p}{\ln n}\right)^2 + \cdots \right).$
Thus, the sum becomes:
$S(n) = \frac{1}{\ln n} \sum_{p < \sqrt{n}} \frac{1}{p^2} + \frac{2}{(\ln n)^2} \sum_{p < \sqrt{n}} \frac{\ln p}{p^2} + O\left(\frac{1}{(\ln n)^3}\right).$
Now let's estimate the sums over primes. It is known that the series$\sum_p \frac{1}{p^2} $ converges to a constant:
$P = \sum_p \frac{1}{p^2} \approx 0.452247.$
Similarly, the series$\sum_p \frac{\ln p}{p^2} $ converges.
Substituting these estimates, we obtain:
$S(n) = \frac{P}{\ln n} + O(\frac{1}{(\ln n)^2}).$

[Yadryara]

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

А помогать не только советом начну прямо сейчас.

Там есть паттерны на 3, 4, и 5 простых.
Без ускорителей Дмитрия случай 3-х простых самый перспективный. Но это без ускорителей.

Формат xlsx пока не смог открыть. Просьба:

1. Выберите ровно один паттерн D(48,21) с тремя одиночными простыми, который считаете наиболее перспективным. Если таковых несколько, всё равно выберите ровно один по какому-то критерию(например с минимальным шагом) и запостите его прямо здесь текстом внутри тега [code][/code]

2. Если уже пытались искать D(48,21) на PARI просьба запостить программу. Посмотрю как её можно будет ускорить.

3. Просьба запостить программу по которой была найдена D(48,20). С той же целью.

[VAL]

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

Формат xlsx пока не смог открыть.

Это же Excel. Даже если он у Вас не установлен, любым (из тех, что я знаю) браузером можно смотреть.

Цитата:

Просьба:

1. Выберите ровно один паттерн D(48,21) с тремя одиночными простыми, который считаете наиболее перспективным. Если таковых несколько, всё равно выберите ровно один по какому-то критерию(например с минимальным шагом) и запостите его прямо здесь текстом внутри тега

2. Если уже пытались искать D(48,21) на PARI просьба запостить программу. Посмотрю как её можно будет ускорить.

3. Просьба запостить программу по которой была найдена D(48,20). С той же целью.

Сейчас покопаюсь в архивах.

-- 30 сен 2025, 10:40 --

Вот программа, нашедшая 20-ку

(Оффтоп)

 \l e:\VAL\math\projects\equidivisible_numbers\PARI\P20\res\res19tau48_3_0_12_I___2-8

m =  15763313547330727349557157245556968800
p1 = 144989573913151252516120361049319706881
a = 3234
u2 = [0,1,2,3,5,8,10,11,14,15,16,18];
U2 = [5887, 12, 3757, 50, 32, 4805, 5043, 2738, 15463, 338, 5547, 605];
F = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]; uu = [0,1,2,3,4,5,6,8,9,10,11,12,14,15,16,17,18]
MM = [5887, 12, 3757, 50, 9, 32, 529, 4805, 4, 5043, 2738, 361, 15463, 338, 5547, 4, 605]

i1 =    57000000000
i2 = i1+20000000000

P=[59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263];
T={[
Set([44, 46, 48]), Set([20, 31, 42]), Set([43, 46, 49]), Set([16, 45, 66]), Set([19, 28, 37]), Set([3, 18, 50]), Set([16, 57, 78]), Set([3, 11, 19]), Set([55, 59, 63]), Set([11, 39, 67]), Set([13, 26, 71]), Set([20, 75, 101]), Set([43, 90, 105]), Set([3, 44, 75]), Set([2, 67, 98]), Set([6, 34, 109]), Set([29, 102, 134]), Set([45, 97, 132]), Set([53, 112, 143]), Set([79, 83, 87]), Set([20, 70, 120]), Set([51, 82, 148]), Set([17, 148, 166]), Set([4, 47, 112]), Set([93, 132, 171]), Set([18, 27, 113]), Set([53, 108, 189]), Set([51, 134, 161]), Set([26, 47, 68]), Set([3, 52, 153]), Set([169, 170, 171]), Set([56, 131, 204]), Set([29, 84, 139]), Set([75, 104, 133]), Set([45, 94, 229]), Set([76, 79, 82]), Set([3, 57, 190]), Set([134, 151, 168]), Set([150, 168, 186]), Set([83, 156, 229])
]}
s=0;s1=0;t=0;t1=0
{for(i=i1,i2,
if(i%5!=3 && i%7!=0 && i%11!=9 && i%13!=9 && i%17!=16 && i%19!=13 && i%23!=20 && i%29!=22 && i%31!=5 && i%37!=36 && i%41!=24 && i%43!=8 && i%47!=6 && i%53!=28, 
tf=1;for(j=1,40, if(setsearch(T[j],i%P[j]),tf=0;break));if(tf, p=p1+i*m;
if(ispseudoprime(p),n=a*p-7;if(ispseudoprime((n+13)/360) && ispseudoprime((n+19)/286518), s=s+1;
f1=1; for(j=1,16, if(ispseudoprime((n+uu[j])/MM[j]),f1=0;break)); 
 if(f1, s1=s1+1; f3=1; for(j=1,12, ng=(n+u2[j])/U2[j]; g=factor(ng,3000000); na=matsize(g)[1];
 if(!((na<3 && !ispseudoprime(g[na,1])) || (na==3 && ispseudoprime(g[na,1]))), f3=0; break));
 if(f3, E=[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0];ss=0;t=t+1; for(j=1,17,if(numdiv(n+uu[j])==48,E[j]=1;ss=ss+1)); F=F+E; s=s+ss;if(ss>12, 
 print((i-i1)/(i2-i1)*100.); t1=t1+1;if(ss==17,print(n," YES!!! ");break); print(n);print("# ",E," ",ss+3)))))))));
 print(s," ",s1," ",t," ",t1);print(F)};"3_0_12_I___2-8"

Значение переменной i, при котором нашлась 20-ка, может не попадать в указанный диапазон: программа перезапускалась с другого компа для разных значений диапазона.

[DemISdx]

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

Формат xlsx пока не смог открыть.

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

Это же Excel. Даже если он у Вас не установлен

Тут может быть совсем другой момент.

Например, если ёксел 2003, то он действительно не умеет открывать xlsx.
Но MS еще в 2007-2009 годах выпускал специальный бесплатный расширитель (add-on), который был доступен для скачки даже в 2023 году (потом не проверял, кажется).

После установки которого спокойно открываются и редактируются указанные файлы (равно как и docx от ворда и т.п.).

Там есть только один нюанс при сохранении.
Который обязательно нужно помнить и перепроверять.

[VAL]

А это одна из программ, тщетно пытавшихся набрать очко

(Оффтоп)

 \l  e:\VAL\math\projects\equidivisible_numbers\PARI\res21\res21tau192_3-0-13-5__II_1
allocatemem(2^28)

m =  554159729309947409007752567806326895200
p1 = 30475766721704852566432501877740394775491
a = 320226
     
M =  [3698, 3971, 12, 49, 50, 5043, 362024, 529, 18, 4805, 28, 4107, 242, 841, 480, 289, 4418, 63, 4, 845, 320226]
u  = [1, 2, 3, 4, 5, 6, 8, 9,10,11,12,13,14,16,17,18,19,20];
nu = [3, 3, 3, 4, 3, 3, 8, 9,10,11,12,13,14,16,17,18,19,20]; 

i1 =       432000000000
i2 =   i1+ 100000000000

P=[61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523];
T={[
Set([16, 35, 59]), Set([0, 46, 47]), Set([19, 30, 44]), Set([21, 30, 55]), Set([13, 49, 51]), Set([40, 51, 80]), Set([5, 15, 87]), Set([15, 39, 57]), Set([63, 71, 86]), Set([51, 93, 98]), Set([47, 85, 100]), Set([19, 36, 88]), Set([32, 39, 98]), Set([70, 95, 117]), Set([16, 39, 82]), Set([16, 63, 134]), Set([50, 107, 134]), Set([60, 108, 145]), Set([57, 108, 132]), Set([21, 38, 118]), Set([6, 24, 48]), Set([65, 118, 143]), Set([45, 57, 126]), Set([67, 110, 129]), Set([104, 130, 175]), Set([34, 74, 166]), Set([51, 76, 143]), Set([97, 139, 164]), Set([82, 149, 181]), Set([91, 93, 166]), Set([16, 153, 192]), Set([142, 149, 211]), Set([18, 51, 163]), Set([86, 133, 206]), Set([39, 78, 124]), Set([9, 80, 84]), Set([56, 141, 248]), Set([42, 141, 167]), Set([6, 43, 180]), Set([21, 178, 208]), Set([1, 53, 62]), Set([68, 126, 172]), Set([13, 56, 207]), Set([44, 152, 227]), Set([43, 147, 225]), Set([36, 126, 250]), Set([94, 125, 245]), Set([112, 204, 254]), Set([154, 185, 210]), Set([220, 245, 297]), Set([190, 203, 297]), Set([124, 138, 221]), Set([24, 99, 106]), Set([78, 87, 334]), Set([263, 287, 319]), Set([80, 145, 238]), Set([14, 29, 367]), Set([153, 247, 272]), Set([187, 199, 215]), Set([58, 348, 371]), Set([163, 170, 286]), Set([12, 102, 293]), Set([173, 218, 354]), Set([244, 312, 333]), Set([45, 280, 351]), Set([117, 266, 321]), Set([140, 153, 267]), Set([1, 300, 334]), Set([62, 143, 397]), Set([26, 286, 394]), Set([241, 269, 290]), Set([155, 276, 410]), Set([56, 101, 214]), Set([27, 320, 391]), Set([167, 193, 452]), Set([88, 97, 469]), Set([151, 222, 462]), Set([182, 222, 413]), Set([139, 373, 383]), Set([108, 284, 485]), Set([351, 371, 498]), Set([41, 82, 141])
]}
s=0;t=0;
{for(i=i1,i2,
if(i%5!=4 && i%7!=3 && i%11!=3 && i%13!=6 && i%17!=11 && i%19!=15 && i%23!=17 && i%29!=1 && i%31!=18 && i%37!=19 && i%41!=21 && i%43!=22 && i%47!=3 && i%53!=23 && i%59!=27, 
tf=1;for(j=1,82, if(setsearch(T[j],i%P[j]),tf=0;break));if(tf, p=p1+i*m;
if(ispseudoprime(p),n=a*p-20; if(ispseudoprime((n+6)/M[7]) && ispseudoprime((n+14)/M[15]),
tf1=1; for(j=1,18,if(ispseudoprime((n+u[j]-1)/M[u[j]]), tf1=0; break)); 
if(tf1, s=s+1; tf2=1; for(j=1,18, ng=(n+u[j]-1)/M[u[j]]; g=factor(ng,300000); na=matsize(g)[1];
 if(!((na==nu[j] && ispseudoprime(g[na,1])) || (na<nu[j] && !ispseudoprime(g[na,1]))), tf2=0; break));
 if(tf2, tf3=1; E=[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0];ss=0;t=t+1; for(j=1,18,if(numdiv(n+u[j]-1)==48,E[j]=1;ss=ss+1);
 if(j>ss+1, if(j>10,printf("%.4g",(i-i1)/(i2-i1)*100.); printf(" ")); break)); 
 if(ss>11, print(); print(n); print("# ",E," ",ss+3);if(ss==18,print(n," YES!!! ");break)))))))));
 print(s," ",t)};"res21tau192_3-0-13-5__II_1"

[Dmitriy40]

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

Если уже пытались искать D(48,21) на PARI просьба запостить программу. Посмотрю как её можно будет ускорить.

Это практически бессмысленно, помнится ещё в 2022 уже выжали всё что можно. Вот например в данных программах проверка setsearch(T[j],i%P[j]) - самая быстрая из возможных (ну разве что на bittest заменить), дальше там кучка относительно быстрых isprime (и тоже почти не ускоряемых), а остальные проверки дальше срабатывают слишком редко чтобы сильно влиять.
Разве что factor(...,300000) можно переставить пораньше, он может быть и быстрее isprime для больших чисел ...

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

Вот я не зря спрашивал про скиллы. Пока прог не было, я решил протестировать старую прогу, ту что в самом конце 1-й страницы нынешней темы.
Результат превзошёл все ожидания: применив лишь один приём ускорения, удалось ускорить её в низине в 18 раз!! И это в рамках всё того же PARI.

Это в них кажется уже сделано, как раз setsearch. Стоило поискать в теме самую последнюю прогу/доработку, они публиковались.

[DemISdx]

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

Не на рекорд. Зато полегче.

Реально полегче...

(Результат по 66781...)

Total factoring time = 3789.1834 seconds


***factors found***
P45 = 772269262549813637626038642073628912409521873
P107 = 86474026052043163309091946494058086083786388989966884782119278396171514669633958849358376846356557013532003

***factorization:***
66781232328924746144700600153327235567658407032359389501313387736577475901690875089816432663672349587875156137903480623549453572992027112083648214001619=772269262549813637626038642073628912409521873*86474026052043163309091946494058086083786388989966884782119278396171514669633958849358376846356557013532003

Число 33546... еще в расчете и там надолго.

[Yadryara]

VAL, DemISdx, Спасибо, буду разбираться.

Пока что прога для 48-21 запустилась из ПАРИ, но не запускается из консоли.

А вот старая прога, та что в самом конце 1-й страницы нынешней темы, успешно запустилась из консоли и я её тестировал.

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

Значение переменной i, при котором нашлась 20-ка, может не попадать в указанный диапазон: программа перезапускалась с другого компа для разных значений диапазона.

Сообщите плиз такие значения i1 и i2, чтобы после запуска 20-ка нашлась в течение 1-2 минут.

[DemISdx]

У меня еще вопрос к Дмитрию, по YAFU:

(Оффтоп)

у программы есть ключики:

cgbn                        :                   : use cgbn with gpu-ecm (external ecm binary enabled with this option must exist)
use_gpuecm                  :                   : use gpu-ecm (external ecm binary enabled with this option must exist)
use_gpudev <value>          : (Integer < 32-bit): gpu device number

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

Погуглил этот момент, но что-то ничего не нашел...

[VAL]

DemISdx в сообщении #1703875 писал(а):

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

Не на рекорд. Зато полегче.

Реально полегче...

Отлично!
$M(1848) \ge 8$

(Начало цепочки)

n = 3483267590844545558470454473370481833879641615351933575200511155278980222223515920279557242797394986735182095473658541761037354170435774027731563941025534133538857377680544638671870
n + 1 = 3^10 × 37^6 × 67^2 × 76693739341 × 772269262549813637626038642073628912409521873 × 86474026052043163309091946494058086083786388989966884782119278396171514669633958849358376846356557013532003 

[Dmitriy40]

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

Сообщите плиз такие значения i1 и i2, чтобы после запуска 20-ка нашлась в течение 1-2 минут.

Смотрите на формулы из программы

m =  15763313547330727349557157245556968800
p1 = 144989573913151252516120361049319706881
a = 3234
p=p1+i*m
n=a*p-7
i1 =    57000000000
i2 = i1+20000000000

Зная n теперь можно посчитать i и задать i1,i2 чтобы интервал [i1,i2] включал это i.

-- 30.09.2025, 13:22 --

DemISdx
Прирост скорости очевидно даст. Но только на стадии ECM, которая в общем вспомогательная и которую можно и пропустить (хотя иногда она быстро находит делитель). NFS будет считать как обычно, на CPU. Соответственно большого выигрыша не достичь (сами сравните время ecm и общее с nfs, например одно из Ваших: общее 181713.4213 из которых на nfs ушло 158877.0839, значит даже бесконечно быстрый ecm на бесконечно быстрой видюхе не выиграет более 181713.4213-158877.0839=22836.3374).
И потому я не разбирался где взять эти бинарники. Ещё и потому что видюхи у меня нет и ради этих задач я её покупать и не буду. Хотя ключики видел, да.

[VAL]

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

Сообщите плиз такие значения i1 и i2, чтобы после запуска 20-ка нашлась в течение 1-2 минут.

Положите

i1 = 346500000000

-- 30 сен 2025, 13:25 --

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

Зная n
теперь можно посчитать i и задать i1,i2 чтобы интервал [i1,i2] включал это i.

Я так и сделал

[DemISdx]

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

Прирост скорости очевидно даст. Но только на стадии ECM, которая в общем вспомогательная и которую можно и пропустить (хотя иногда она быстро находит делитель). NFS будет считать как обычно, на CPU.

Спасибо за ликбез!

(Оффтоп)

Нашел прикольное сравнение по скоростям факторизации от Dana Jacobsen:
https://ntheory.org/sieves/benchmarks.html
жаль только, что список старый.
YAFU на первом месте...
Удивительно, но perl достаточно хорошую позицию занимает.

И еще факторизатор на GPU, но что это за зверь - не знаю.
https://www.rieselprime.de/ziki/Mfaktc

[Dmitriy40]

(Оффтоп)

DemISdx в сообщении #1703913 писал(а):

И еще факторизатор на GPU, но что это за зверь - не знаю.
https://www.rieselprime.de/ziki/Mfaktc

Насколько вижу это только для чисел Мерсенна $M_n=2^n-1$, YAFU такие (и $2^n+1$) тоже проверяет первым делом, тут даже CUDA не нужна, у нас числа пока не настолько велики чтобы CPU не справился за секунды.

DemISdx в сообщении #1703913 писал(а):

Нашел прикольное сравнение по скоростям факторизации от Dana Jacobsen:
https://ntheory.org/sieves/benchmarks.html

Это что-то другое, не факторизация, скорее всего генерация всех простых в заданном интервале (чаще всего решетом Эратосфена), потому что у меня факторизация чисел порядка $10^{60...70}$ занимает буквально секунды.

[Yadryara]

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

Положите

i1 = 346500000000

И охота Вам с этими нулями возиться. Я положил 346500e6. Действительно, где-то на второй минуте выдача была такая:

0.13283096000000000000000000000000000000

2907131999263647241639125071485412894901874802299547

# [1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1] 16

А единственная 20-ка вроде бы такая:

17668887847524548413038893976018715843277693308027547