2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1 ... 170, 171, 172, 173, 174, 175, 176 ... 215  След.
 
 Re: Пентадекатлон мечты
Сообщение18.11.2022, 22:19 
Аватара пользователя


11/12/16
14036
уездный город Н
Dmitriy40 в сообщении #1570396 писал(а):
По моему не должны, ведь все такие $p$ будут сильно меньше $\sqrt{M/N}$ и останутся в проверке. А программа выше проверяет любые цепочки длиной 10+ (по 15).
Кроме $p^2q^3$, этот вариант я похоже пропустил.


Это от $N$ и $M$ зависит, а Вы $N$ не озвучиваете. :wink:
У меня получилось так (требует проверки) если $M = 10^{22}$, а $N < 10^7$, то для факторизации $p^3q^2$ можем не проверять, для $p^5q$ - тем более.

-- 18.11.2022, 22:34 --

Huz в сообщении #1570394 писал(а):
but this reads as if you want to play guessing games,

Dmitry formulated the main idea on November 9th. But then it was assumed that this would require modification of pcoul. But pcoul already has the required key, which specified, it will allocate (see below) only powers of primes p < N.
This post is a summary of this idea.

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение18.11.2022, 22:44 
Заслуженный участник


20/08/14
11867
Россия, Москва
Типа я жадный, да? ;-)
Давайте прикидывать для $p^3q^2$: $q\ge13, M=10^{22} \to p<\sqrt[3]{10^{22}/13^2}\approx 4\cdot10^6$ или $N$ для $p^2N$ больше чем примерно $10^5$ (решения около 3e18), настолько большие $N$ я проверять не предлагал (это где-то на пару лет счёта в один поток). :mrgreen:

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение18.11.2022, 22:50 


05/06/22
293
EUgeneUS в сообщении #1570399 писал(а):
Dmitry formulated the main idea on November 9th. But then it was assumed that this would require modification of pcoul. But pcoul already has the required key, which specified, it will allocate (see below) only powers of primes p < N.
This post is a summary of this idea.

Thanks, I think I understand it. As described it appears to be quite specific to 12 divisors, I wonder whether it can be made more general and still remain useful.

It would probably be easy to add a new option to pcoul for a more specialized restriction on the maximum prime to allocate, eg to say "don't allocate $p^2$ with $p > p_{\max}$, but continue to allocate other powers without restriction". But pcoul knows nothing about specific factorizations, so I do not think it would be able to distinguish between $p^2qr$ and $p^2q^3$.

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение18.11.2022, 23:13 
Заслуженный участник


20/08/14
11867
Россия, Москва
Huz
Hugo, it is not necessary to distinguish $p^2qr$ and $p^2q^3$ in pcoul, just separately (not by pcoul) check both that they do not give solutions for $p>p_{\max}$.

For another number of divisors you can also apply, in $N=qr$ there will be only not the product of two prime numbers, but a larger number or corresponding combinations of prime numbers in powers. But of course there will be more of these combinations and it will take longer to prove it directly. But for sure there $M$ will be much larger (1e22) and $p$ will have to go much, much farther, which will devalue the idea.

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение18.11.2022, 23:35 
Аватара пользователя


11/12/16
14036
уездный город Н
Huz в сообщении #1570402 писал(а):
As described it appears to be quite specific to 12 divisors,

Yes, in this form it is specific to 12 divisors.
But we have a lot of profit:
1. pcoul, as a universal software, it does not require specific modifications. Everything we need is already there.
2. calculation time is reduced tenfold.

We just need to check that everything is done neatly, and nothing is missed.

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение19.11.2022, 04:44 
Аватара пользователя


29/04/13
8307
Богородский
Статистика по данным на вчера. Софокл и Маруся продолжают свой труд.

Серым отмечен квадратик, все паттерны которого или уже проверены или в работе. Через 3-4 дня уже досчитаются все основные паттерны с 7-ю проверяемыми числами. И он позеленеет.

$\tikz[scale=.08]{
\fill[green!90!blue!50] (110,150) rectangle (125,180);
\fill[grey!25] (85,170) rectangle (95,180);
\fill[green!90!blue!50] (0,120) rectangle (140,150);
\draw  (0,210) rectangle  (10,220);
\draw  (10,210) rectangle  (45,220);
\draw  (45,210) rectangle  (55,220);
\draw  (55,210) rectangle  (65,220);
\draw  (65,210) rectangle  (75,220);
\draw  (75,210) rectangle  (85,220);
\draw  (85,210) rectangle  (95,220);
\draw  (95,210) rectangle  (110,220);
\draw  (110,210) rectangle  (125,220);
\draw  (125,210) rectangle  (140,220);
\draw  (0,200) rectangle  (10,210);
\draw  (10,200) rectangle  (45,210);
\draw  (45,200) rectangle  (55,210);
\draw  (55,200) rectangle  (65,210);
\draw  (65,200) rectangle  (75,210);
\draw  (75,200) rectangle  (85,210);
\draw  (85,200) rectangle  (95,210);
\draw  (95,200) rectangle  (110,210);
\draw  (110,200) rectangle  (125,210);
\draw  (125,200) rectangle  (140,210);
\draw  (0,190) rectangle  (10,200);
\draw  (10,190) rectangle  (45,200);
\draw  (45,190) rectangle  (55,200);
\draw  (55,190) rectangle  (65,200);
\draw  (65,190) rectangle  (75,200);
\draw  (75,190) rectangle  (85,200);
\draw  (85,190) rectangle  (95,200);
\draw  (95,190) rectangle  (110,200);
\draw  (110,190) rectangle  (125,200);
\draw  (125,190) rectangle  (140,200);
\draw  (0,180) rectangle  (10,190);
\draw  (10,180) rectangle  (45,190);
\draw  (45,180) rectangle  (55,190);
\draw  (55,180) rectangle  (65,190);
\draw  (65,180) rectangle  (75,190);
\draw  (75,180) rectangle  (85,190);
\draw  (85,180) rectangle  (95,190);
\draw  (95,180) rectangle  (110,190);
\draw  (110,180) rectangle  (125,190);
\draw  (125,180) rectangle  (140,190);
\draw  (0,170) rectangle  (10,180);
\draw  (10,170) rectangle  (45,180);
\draw  (45,170) rectangle  (55,180);
\draw  (55,170) rectangle  (65,180);
\draw  (65,170) rectangle  (75,180);
\draw  (75,170) rectangle  (85,180);
\draw  (85,170) rectangle  (95,180);
\draw  (95,170) rectangle  (110,180);
\draw  (110,170) rectangle  (125,180);
\draw  (125,170) rectangle  (140,180);
\draw  (0,160) rectangle  (10,170);
\draw  (10,160) rectangle  (45,170);
\draw  (45,160) rectangle  (55,170);
\draw  (55,160) rectangle  (65,170);
\draw  (65,160) rectangle  (75,170);
\draw  (75,160) rectangle  (85,170);
\draw  (85,160) rectangle  (95,170);
\draw  (95,160) rectangle  (110,170);
\draw  (110,160) rectangle  (125,170);
\draw  (125,160) rectangle  (140,170);
\draw  (0,150) rectangle  (10,160);
\draw  (10,150) rectangle  (45,160);
\draw  (45,150) rectangle  (55,160);
\draw  (55,150) rectangle  (65,160);
\draw  (65,150) rectangle  (75,160);
\draw  (75,150) rectangle  (85,160);
\draw  (85,150) rectangle  (95,160);
\draw  (95,150) rectangle  (110,160);
\draw  (110,150) rectangle  (125,160);
\draw  (125,150) rectangle  (140,160);
\draw  (0,140) rectangle  (10,150);
\draw  (10,140) rectangle  (45,150);
\draw  (45,140) rectangle  (55,150);
\draw  (55,140) rectangle  (65,150);
\draw  (65,140) rectangle  (75,150);
\draw  (75,140) rectangle  (85,150);
\draw  (85,140) rectangle  (95,150);
\draw  (95,140) rectangle  (110,150);
\draw  (110,140) rectangle  (125,150);
\draw  (125,140) rectangle  (140,150);
\draw  (0,130) rectangle  (10,140);
\draw  (10,130) rectangle  (45,140);
\draw  (45,130) rectangle  (55,140);
\draw  (55,130) rectangle  (65,140);
\draw  (65,130) rectangle  (75,140);
\draw  (75,130) rectangle  (85,140);
\draw  (85,130) rectangle  (95,140);
\draw  (95,130) rectangle  (110,140);
\draw  (110,130) rectangle  (125,140);
\draw  (125,130) rectangle  (140,140);
\draw  (0,120) rectangle  (10,130);
\draw  (10,120) rectangle  (45,130);
\draw  (45,120) rectangle  (55,130);
\draw  (55,120) rectangle  (65,130);
\draw  (65,120) rectangle  (75,130);
\draw  (75,120) rectangle  (85,130);
\draw  (85,120) rectangle  (95,130);
\draw  (95,120) rectangle  (110,130);
\draw  (110,120) rectangle  (125,130);
\draw  (125,120) rectangle  (140,130);
\node at (4.7,215){\text{1044}};
\node at (28,215){\text{LCM}};
\node at (50,215){\text{3}};
\node at (60,215){\text{4}};
\node at (70,215){\text{5}};
\node at (80,215){\text{6}};
\node at (90,215){\text{7}};
\node at (103,215){\text{Total}};
\node at (118,215){\text{Done}};
\node at (133,215){\text{Work}};
\node at (5.6,205){\text{1.}};
\node at (36,205){\text{554400}};
\node at (50,205){\text{8}};
\node at (60,205){\text{30}};
\node at (70,205){\text{28}};
\node at (104,205){\text{66}};
\node at (90,205){\text{}};
\node at (5.6,195){\text{2.}};
\node at (35,195){\text{3880800}};
\node at (50,195){\text{8}};
\node at (60,195){\text{46}};
\node at (70,195){\text{60}};
\node at (80,195){\text{28}};
\node at (103,195){\text{142}};
\node at (133,195){\text{1}};
\node at (5.6,185){\text{3.}};
\node at (35,185){\text{6098400}};
\node at (50,185){\text{8}};                       
\node at (60,185){\text{46}};
\node at (70,185){\text{78}};
\node at (80,185){\text{48}};
\node at (103,185){\text{180}};
\node at (133,185){\text{1}};
\node at (5.6,175){\text{4.}};
\node at (34,175){\text{42688800}};
\node at (50,175){\text{8}};
\node at (60,175){\text{54}};
\node at (70,175){\text{94}};
\node at (80,175){\text{60}};
\node at (90,175){\text{10}};
\node at (103,175){\text{226}};
\node at (118,175){\text{5}};
\node at (133,175){\text{7}};
\node at (5.6,165){\text{5.}};
\node at (32,165){\text{1331114400}};
\node at (50,165){\text{}};
\node at (60,165){\text{8}};
\node at (70,165){\text{30}};
\node at (80,165){\text{28}};
\node at (104,165){\text{66}};
\node at (118,165){\text{6}};
\node at (133,165){\text{1}};
\node at (5.6,155){\text{6.}};
\node at (32,155){\text{8116970400}};
\node at (50,155){\text{}};
\node at (60,155){\text{8}};
\node at (70,155){\text{26}};
\node at (80,155){\text{24}};
\node at (104,155){\text{58}};
\node at (118,155){\text{25}};
\node at (133,155){\text{1}};
\node at (5.6,145){\text{7.}};
\node at (31,145){\text{14642258400}};
\node at (60,145){\text{8}};
\node at (70,145){\text{42}};
\node at (80,145){\text{66}};
\node at (90,145){\text{36}};
\node at (103,145){\text{152}};
\node at (118,145){\text{152}};
\node at (133,145){\text{}};
\node at (5.6,135){\text{8.}};
\node at (31,135){\text{56818792800}};
\node at (60,135){\text{8}};
\node at (70,135){\text{38}};
\node at (80,135){\text{40}};
\node at (90,135){\text{10}};
\node at (104,135){\text{96}};
\node at (118,135){\text{96}};
\node at (5.6,125){\text{9.}};
\node at (28,125){\text{19488845930400}};
\node at (70,125){\text{8}};
\node at (80,125){\text{26}};
\node at (90,125){\text{24}};
\node at (104,125){\text{58}};
\node at (118,125){\text{58}};
}$

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение19.11.2022, 11:45 
Аватара пользователя


29/04/13
8307
Богородский
Наконец-то сделал первую попытку объединить результаты счёта по программам Дмитрия и Hugo.

$\tikz[scale=.08]{
\fill[green!90!blue!50] (110,150) rectangle (125,200);
\fill[grey!25] (85,170) rectangle (95,180);
\fill[green!90!blue!50] (0,120) rectangle (140,150);
\draw  (0,210) rectangle  (10,220);
\draw  (10,210) rectangle  (45,220);
\draw  (45,210) rectangle  (55,220);
\draw  (55,210) rectangle  (65,220);
\draw  (65,210) rectangle  (75,220);
\draw  (75,210) rectangle  (85,220);
\draw  (85,210) rectangle  (95,220);
\draw  (95,210) rectangle  (110,220);
\draw  (110,210) rectangle  (125,220);
\draw  (125,210) rectangle  (140,220);
\draw  (0,200) rectangle  (10,210);
\draw  (10,200) rectangle  (45,210);
\draw  (45,200) rectangle  (55,210);
\draw  (55,200) rectangle  (65,210);
\draw  (65,200) rectangle  (75,210);
\draw  (75,200) rectangle  (85,210);
\draw  (85,200) rectangle  (95,210);
\draw  (95,200) rectangle  (110,210);
\draw  (110,200) rectangle  (125,210);
\draw  (125,200) rectangle  (140,210);
\draw  (0,190) rectangle  (10,200);
\draw  (10,190) rectangle  (45,200);
\draw  (45,190) rectangle  (55,200);
\draw  (55,190) rectangle  (65,200);
\draw  (65,190) rectangle  (75,200);
\draw  (75,190) rectangle  (85,200);
\draw  (85,190) rectangle  (95,200);
\draw  (95,190) rectangle  (110,200);
\draw  (110,190) rectangle  (125,200);
\draw  (125,190) rectangle  (140,200);
\draw  (0,180) rectangle  (10,190);
\draw  (10,180) rectangle  (45,190);
\draw  (45,180) rectangle  (55,190);
\draw  (55,180) rectangle  (65,190);
\draw  (65,180) rectangle  (75,190);
\draw  (75,180) rectangle  (85,190);
\draw  (85,180) rectangle  (95,190);
\draw  (95,180) rectangle  (110,190);
\draw  (110,180) rectangle  (125,190);
\draw  (125,180) rectangle  (140,190);
\draw  (0,170) rectangle  (10,180);
\draw  (10,170) rectangle  (45,180);
\draw  (45,170) rectangle  (55,180);
\draw  (55,170) rectangle  (65,180);
\draw  (65,170) rectangle  (75,180);
\draw  (75,170) rectangle  (85,180);
\draw  (85,170) rectangle  (95,180);
\draw  (95,170) rectangle  (110,180);
\draw  (110,170) rectangle  (125,180);
\draw  (125,170) rectangle  (140,180);
\draw  (0,160) rectangle  (10,170);
\draw  (10,160) rectangle  (45,170);
\draw  (45,160) rectangle  (55,170);
\draw  (55,160) rectangle  (65,170);
\draw  (65,160) rectangle  (75,170);
\draw  (75,160) rectangle  (85,170);
\draw  (85,160) rectangle  (95,170);
\draw  (95,160) rectangle  (110,170);
\draw  (110,160) rectangle  (125,170);
\draw  (125,160) rectangle  (140,170);
\draw  (0,150) rectangle  (10,160);
\draw  (10,150) rectangle  (45,160);
\draw  (45,150) rectangle  (55,160);
\draw  (55,150) rectangle  (65,160);
\draw  (65,150) rectangle  (75,160);
\draw  (75,150) rectangle  (85,160);
\draw  (85,150) rectangle  (95,160);
\draw  (95,150) rectangle  (110,160);
\draw  (110,150) rectangle  (125,160);
\draw  (125,150) rectangle  (140,160);
\draw  (0,140) rectangle  (10,150);
\draw  (10,140) rectangle  (45,150);
\draw  (45,140) rectangle  (55,150);
\draw  (55,140) rectangle  (65,150);
\draw  (65,140) rectangle  (75,150);
\draw  (75,140) rectangle  (85,150);
\draw  (85,140) rectangle  (95,150);
\draw  (95,140) rectangle  (110,150);
\draw  (110,140) rectangle  (125,150);
\draw  (125,140) rectangle  (140,150);
\draw  (0,130) rectangle  (10,140);
\draw  (10,130) rectangle  (45,140);
\draw  (45,130) rectangle  (55,140);
\draw  (55,130) rectangle  (65,140);
\draw  (65,130) rectangle  (75,140);
\draw  (75,130) rectangle  (85,140);
\draw  (85,130) rectangle  (95,140);
\draw  (95,130) rectangle  (110,140);
\draw  (110,130) rectangle  (125,140);
\draw  (125,130) rectangle  (140,140);
\draw  (0,120) rectangle  (10,130);
\draw  (10,120) rectangle  (45,130);
\draw  (45,120) rectangle  (55,130);
\draw  (55,120) rectangle  (65,130);
\draw  (65,120) rectangle  (75,130);
\draw  (75,120) rectangle  (85,130);
\draw  (85,120) rectangle  (95,130);
\draw  (95,120) rectangle  (110,130);
\draw  (110,120) rectangle  (125,130);
\draw  (125,120) rectangle  (140,130);
\node at (4.7,215){\text{1044}};
\node at (28,215){\text{LCM}};
\node at (50,215){\text{3}};
\node at (60,215){\text{4}};
\node at (70,215){\text{5}};
\node at (80,215){\text{6}};
\node at (90,215){\text{7}};
\node at (103,215){\text{Total}};
\node at (118,215){\text{Done}};
\node at (133,215){\text{Work}};
\node at (5.6,205){\text{1.}};
\node at (36,205){\text{554400}};
\node at (50,205){\text{8}};
\node at (60,205){\text{30}};
\node at (70,205){\text{28}};
\node at (104,205){\text{66}};
\node at (90,205){\text{}};
\node at (133,205){\text{?}};
\node at (5.6,195){\text{2.}};
\node at (35,195){\text{3880800}};
\node at (50,195){\text{8}};
\node at (60,195){\text{46}};
\node at (70,195){\text{60}};
\node at (80,195){\text{28}};
\node at (103,195){\text{142}};
\node at (118,195){\text{6}};
\node at (133,195){\text{?}};
\node at (5.6,185){\text{3.}};
\node at (35,185){\text{6098400}};
\node at (50,185){\text{8}};                       
\node at (60,185){\text{46}};
\node at (70,185){\text{78}};
\node at (80,185){\text{48}};
\node at (103,185){\text{180}};
\node at (118,185){\text{9}};
\node at (133,185){\text{?}};
\node at (5.6,175){\text{4.}};
\node at (34,175){\text{42688800}};
\node at (50,175){\text{8}};
\node at (60,175){\text{54}};
\node at (70,175){\text{94}};
\node at (80,175){\text{60}};
\node at (90,175){\text{10}};
\node at (103,175){\text{226}};
\node at (118,175){\text{22}};
\node at (133,175){\text{?}};
\node at (5.6,165){\text{5.}};
\node at (32,165){\text{1331114400}};
\node at (50,165){\text{}};
\node at (60,165){\text{8}};
\node at (70,165){\text{30}};
\node at (80,165){\text{28}};
\node at (104,165){\text{66}};
\node at (118,165){\text{33}};
\node at (133,165){\text{?}};
\node at (5.6,155){\text{6.}};
\node at (32,155){\text{8116970400}};
\node at (50,155){\text{}};
\node at (60,155){\text{8}};
\node at (70,155){\text{26}};
\node at (80,155){\text{24}};
\node at (104,155){\text{58}};
\node at (118,155){\text{37}};
\node at (133,155){\text{?}};
\node at (5.6,145){\text{7.}};
\node at (31,145){\text{14642258400}};
\node at (60,145){\text{8}};
\node at (70,145){\text{42}};
\node at (80,145){\text{66}};
\node at (90,145){\text{36}};
\node at (103,145){\text{152}};
\node at (118,145){\text{152}};
\node at (133,145){\text{}};
\node at (5.6,135){\text{8.}};
\node at (31,135){\text{56818792800}};
\node at (60,135){\text{8}};
\node at (70,135){\text{38}};
\node at (80,135){\text{40}};
\node at (90,135){\text{10}};
\node at (104,135){\text{96}};
\node at (118,135){\text{96}};
\node at (5.6,125){\text{9.}};
\node at (28,125){\text{19488845930400}};
\node at (70,125){\text{8}};
\node at (80,125){\text{26}};
\node at (90,125){\text{24}};
\node at (104,125){\text{58}};
\node at (118,125){\text{58}};
}$

Да, есть совпадения и по медленным паттернам. Например:

Код:
b1981:LCM1331114400-753575449-8
      LCM1331114400-753575449-8: end, time: 168137.319s

b2123:LCM1331114400-748264441-8
      LCM1331114400-748264441-8: end, time: 538927.729s


Комп EUgeneUS и Софокл дважды считали один и тот же паттерн с шагом 1331114400. Причём во втором случае Софокл потратил более 6-ти суток.

Конечно есть плюс в том что можно время сравнить, но надо ли нам и дальше считать одно и то же ? Или всё-таки будем действовать согласованно ?

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение19.11.2022, 17:57 
Аватара пользователя


11/12/16
14036
уездный город Н
Yadryara
Время расчета pcoul на моей стороне:
b1981 - 102372.03s
b2123 - 122281.30s
Yadryara в сообщении #1570442 писал(а):
Или всё-таки будем действовать согласованно ?

И действительно.

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение19.11.2022, 22:20 
Аватара пользователя


11/12/16
14036
уездный город Н
Посмотрел код из этого поста.
1. Вот это
Код:
qrmin=13*2;
завязано на том, что в паттерне обязательно есть "пустое" место, куда буде расставляться $p^2qr$, а $r > q \ge 13$
Для нашего случая, у всех паттернов с $32s$ это выполняется.

2. Метод проверки завязан на наличие в паттерне $32s$, и что одно из из чисел $32s \pm 2$, опять же это выполняется в нашем случае.

Проблема в другом.
Dmitriy40 в сообщении #1570376 писал(а):
Если она не найдёт решений длиной 11 до 1e22 и qr<10000, то это и позволит получать ускорение 40-50 раз на любых паттернах для цепочек длиной 11 без изменения программы Hugo.

Если $M = 10^{22}$, проверены $qr \le 10^4$, то $p_{\text{max}} < \sqrt{M/N} = 10^9$
Запустил расчет ранее посчитанного паттерна b2155 теперь с ключом
Код:
-p1^1000000001

Ускорение в разы наблюдается, но не в 40-50 раз. На первых записях в лог ускорение было в 7-8 раз. Сейчас колеблется в районе 3-5 раз.

-- 19.11.2022, 22:47 --

Dmitriy40
Вот что не понимаю.
Код:
001 pcoul(12 11) -p1:1000000001 -f11 -g16 -x9887353188984012120346 -b2155 *RT*
305 13^2 2 3 2^2.7 5.17^2 2.3^2 23^2 2^5 3.11^2 2.5^2 7^2: 1711644 / 4482247 (597.17s)
305 13^2 2 3 2^2.7 5.151287523^2 2.3^2 31^2 2^5 3.11^2 2.5^2 7^2 (1193.09s)
305 13^2 2 3 2^2.7 5.600119087^2 2.3^2 41^2 2^5 3.11^2 2.5^2 7^2 (1790.00s)
...

Как видно в последних двух приведенных строчках, в позицию с $5$ подставляются квадраты больших простых. И эти большие простые будут ограничены $10^9$.
Но мы же в предрасчете не проверяли для $qr = 5r$...

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение19.11.2022, 23:19 
Заслуженный участник


20/08/14
11867
Россия, Москва
EUgeneUS в сообщении #1570504 писал(а):
Как видно в последних двух приведенных строчках, в позицию с $5$ подставляются квадраты больших простых. И эти большие простые будут ограничены $10^9$.
Но мы же в предрасчете не проверяли для $qr = 5r$...
Проверяли: $r$ в цикле идёт от $2$, а $q$ от $qrmin/r$ (но не меньше чем $r+1$) до $qrmax/r$ для каждого $r$, так что все варианты $5x$ были проверены при $r=5$. И у меня принято что $q>r, q\ge13$, я об этом прямо сказал, возможно из-за этого у Вас некоторая путаница.

EUgeneUS в сообщении #1570504 писал(а):
завязано на том, что в паттерне обязательно есть "пустое" место, куда буде расставляться $p^2qr$, а $r > q \ge 13$
Нет, это завязано на том что в любой непустой позиции есть простое не меньше $2$, а после подстановки $p^2$ останется неизвестное простое не меньше $13$.
В пустую позицию подставляться будет $p^2$, а $qr$ там может быть не менее чем $13\times17=221$ (все меньшие простые уже расставлены).

EUgeneUS в сообщении #1570504 писал(а):
Запустил расчет ранее посчитанного паттерна b2155 теперь с ключом -p1^1000000001
Ускорение в разы наблюдается, но не в 40-50 раз. На первых записях в лог ускорение было в 7-8 раз. Сейчас колеблется в районе 3-5 раз.
Во первых там вроде бы двоеточие должно быть. Во вторых не от 1 (впрочем это неважно). В третьих я запускал с ключом -g3, он оказался быстрее -g9 и -g16. В четвёртых возможно дальше ускорение будет выше, я же сравнивал только конечный результат. В пятых я не обещал ускорения 40-50 раз на всех паттернах, на паттернах с одним перебором оно будет меньше 6х (ускорится только конец первого перебора и всё). В шестых имеет смысл поиграться с -g, теперь ведь второй-третий перебор можно запускать чаще прежнего, они же быстрее выполняются (т.е. можно посмотреть на первые 10-20 минут в логе и сравнить сколько времени занял линейный поиск и сколько квадратичный и не стоит ли уменьшить/увеличить -g).

-- 19.11.2022, 23:24 --

Dmitriy40 в сообщении #1570514 писал(а):
В пятых я не обещал ускорения 40-50 раз на всех паттернах, на паттернах с одним перебором оно будет меньше 6х (ускорится только конец первого перебора и всё).
Но возможно будет выгодно запустить второй перебор (указанием соответствующего -g) и тогда выигрыш может станет и больше. А может и не стать, если линейный перебор для каждого простого и так был быстрее квадратичного с ограничением $p$.
Да, про то что выигрыш будет 45 раз на любых паттернах я погорячился. Где-то меньше, где-то больше. Я же не проверял их все.

-- 19.11.2022, 23:29 --

EUgeneUS
В начале много линейных переборов, а они не ускоряются. Вот когда линейных переборов станет меньше, останутся лишь квадратичные, вот они то и ускорятся. И так на каждом уровне перебора.

-- 19.11.2022, 23:34 --

Вообще этот ключик -g очень мутный и непонятно как его выбирать кроме как опытным путём. :-(
Когда я буду делать такой универсальный перебор, то склоняюсь всё же к автоматическому выбору на лету, прямо по реальному счёту или тестовому измерению.

-- 19.11.2022, 23:43 --

Ну и да, $qr \le N=10^4$ я проверил, можно пользоваться ключом -p1e9.

-- 19.11.2022, 23:49 --

А может я вообще ошибся в своих тестах и ускорение меньше. :mrgreen:

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение20.11.2022, 00:21 
Аватара пользователя


11/12/16
14036
уездный город Н
Dmitriy40 в сообщении #1570514 писал(а):
Проверяли: $r$ в цикле идёт от $2$, а $q$ от $qrmin/r$ (но не меньше чем $r+1$) до $qrmax/r$ для каждого $r$, так что все варианты $5x$ были проверены при $r=5$. И у меня принято что $q>r, q\ge13$, я об этом прямо сказал, возможно из-за этого у Вас некоторая путаница.

Спасибо за разъяснения. Тогда многое становится на свои места.

Dmitriy40 в сообщении #1570514 писал(а):
Во первых там вроде бы двоеточие должно быть. Во вторых не от 1 (впрочем это неважно). В третьих я запускал с ключом -g3, он оказался быстрее -g9 и -g16.

Да, д.б. двоеточие. Это я при первых запусках опечатался, потом исправил. А для примера, зачем-то взял лог с этой опечаткой :roll:

Сейчас работает два потока с -g16 и -g3

Dmitriy40 в сообщении #1570514 писал(а):
Ну и да, $qr \le N=10^4$ я проверил, можно пользоваться ключом -p1e9.

Тут имеется в виду все таки -p1:1e9 ?

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение20.11.2022, 00:40 
Заслуженный участник


20/08/14
11867
Россия, Москва
EUgeneUS в сообщении #1570522 писал(а):
Тут имеется в виду все таки -p1:1e9 ?
Скорее -p13:1e9. Но нижнюю границу можно же и не указывать.

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение20.11.2022, 02:50 
Заслуженный участник


20/08/14
11867
Россия, Москва
Да, похоже в тестах я замечтался и реальное ускорение будет сильно скромнее (но будет всегда, при тех же прочих параметрах запуска).

Но есть другая идея: я выше прикидывал что pcoul почти на порядок медленнее PARI перебирает большие простые, даже после обновления итератора всё равно в разы медленнее, ну так можно взять каждый конкретный паттерн и проверить на PARI что большие простые в квадрате не дают решений при подстановке во все возможные места паттерна. Это будет не быстро, но точно быстрее pcoul. А снизив так порог простых до миллионов можно запустить pcoul с таким сильным ограничением и получить большой итоговый выигрыш. :mrgreen: Заморочки с qr тут уже не будет, зато будет линейный перебор на PARI, но он будет всего несколько (десятков) итераций для каждого простого (причём можно воспользоваться предыдущим результатом и ограничить простые до 1e9). И только один раз для каждого места в паттерне, а не много-много раз как pcoul. Для паттернов c LCM=554400 и простыми от 1e7 до 1e9 PARI должно хватить минут 20 проверить все варианты ... И пары часов для простых от 1e6 до 1e9.

-- 20.11.2022, 03:10 --

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

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение20.11.2022, 04:10 
Заслуженный участник


20/08/14
11867
Россия, Москва
Для одного из самых трудных паттернов b1952 (LCM=554400, n=3) за 10 минут счёта порог простых опустил с 1e9 до 1e8.
За 22 минуты до 30e6.
30 минут и 20e6.
40 минут и 15e6.
Час и 10e6.

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение20.11.2022, 11:49 
Заслуженный участник


20/08/14
11867
Россия, Москва
Уменьшение порога до 1e6 потребует около 9ч (не увижу так как убегаю, сейчас 460 минут и 1.22e6). Но это всё равно лучше двух месяцев счёта pcoul, с ограничением она должна сильно побыстрее справиться.
Программу покажу вечером, ещё раз обдумаю всё ли правильно.

Начиная с простых порядка 7.5e6 и меньше стали находиться решения длиной 5 и более, сейчас одно 7, три по 6 и 15 по 5.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 3218 ]  На страницу Пред.  1 ... 170, 171, 172, 173, 174, 175, 176 ... 215  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group