2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1 ... 199, 200, 201, 202, 203, 204, 205 ... 215  След.
 
 Re: Пентадекатлон мечты
Сообщение13.01.2023, 19:30 
Аватара пользователя


11/12/16
13195
уездный город Н
Yadryara в сообщении #1576991 писал(а):
Паттерны вот такие:

Спасибо.

Но это как-то не бьётся (хотя бы по количеству паттернов) с информаций от Дмитрия тут:

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


20/08/14
11061
Россия, Москва
EUgeneUS
Потому что я говорил о поиске именно 14, а Антон о поиске 15 (в процессе которого находились и 14, но некоторые и могли и реально пропускались).

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


05/06/22
292
Dmitriy40 в сообщении #1576983 писал(а):
Huz
Is there any way to get pcoul to check the pattern without recompiling?
2.53 . 2^2.3 7 2.5^2 3 2^5 11 2.3^2 5 2^2.7 3 [sq=1]
If I correctly understand the question, then no.

To start at a specific point you can create a fake log file with an appropriate "305" line; but it will accept that only if it is something that could have been generated. Since it never generates an allocation of $53^1$, this is not something it will accept.

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


29/04/13
7126
Богородский
Насчёт того, почему дотошный Антоха не задавал вопросов про суперпрогу Дмитрия. Потому как сказано было:

Dmitriy40 в сообщении #1576867 писал(а):
Перебор везде линейный

То есть это старая версия адаптированная под 13-ки, а не та новая, которую я жду.

Почему работает так быстро? Тоже понятно: и шаг огромный, и количество проверяемых мест(CP) весьма велико.

Кстати, теперь уже указываю количество CP(от 8 до 13) в новой версии таблицы:

$\tikz[scale=.08]{
\fill[green!90!blue!50] (0,20) rectangle (144,50);
\fill[green!70!blue!80] (0,0) rectangle (144,20);
\draw[step=10] (60,0) grid (120,100);
\draw  (0,90) rectangle  (10,100);
\draw  (10,90) rectangle  (60,100);
\draw  (120,90) rectangle  (132,100);
\draw  (132,90) rectangle  (144,100);
\draw  (0,80) rectangle  (10,90);
\draw  (10,80) rectangle  (60,90);
\draw  (120,80) rectangle  (132,90);
\draw  (132,80) rectangle  (144,90);
\draw  (0,70) rectangle  (10,80);
\draw  (10,70) rectangle  (60,80);
\draw  (120,70) rectangle  (132,80);
\draw  (132,70) rectangle  (144,80);
\draw  (0,60) rectangle  (10,70);
\draw  (10,60) rectangle  (60,70);
\draw  (120,60) rectangle  (132,70);
\draw  (132,60) rectangle  (144,70);
\draw  (0,50) rectangle  (10,60);
\draw  (10,50) rectangle  (60,60);
\draw  (120,50) rectangle  (132,60);
\draw  (132,50) rectangle  (144,60);
\draw  (0,40) rectangle  (10,50);
\draw  (10,40) rectangle  (60,50);
\draw  (120,40) rectangle  (132,50);
\draw  (132,40) rectangle  (144,50);
\draw  (0,30) rectangle  (10,40);
\draw  (10,30) rectangle  (60,40);
\draw  (120,30) rectangle  (132,40);
\draw  (132,30) rectangle  (144,40);
\draw  (0,20) rectangle  (10,30);
\draw  (10,20) rectangle  (60,30);
\draw  (120,20) rectangle  (132,30);
\draw  (132,20) rectangle  (144,30);
\draw  (0,10) rectangle  (10,20);
\draw  (10,10) rectangle  (60,20);
\draw  (120,10) rectangle  (132,20);
\draw  (132,10) rectangle  (144,20);
\draw  (0,0) rectangle  (10,10);
\draw  (10,0) rectangle  (60,10);
\draw  (120,0) rectangle  (132,10);
\draw  (132,0) rectangle  (144,10);
\node at (5,95){\text{№}};
\node at (34,95){\text{LCM}};
\node at (65,95){\text{8}};
\node at (75,95){\text{9}};
\node at (85,95){\text{10}};
\node at (95,95){\text{11}};
\node at (105,95){\text{12}};
\node at (115,95){\text{13}};
\node at (125.9,95){\text{Pat}};
\node at (137.8,95){\text{Done}};
\node at (6,85){\text{1}};
\node at (48,85){\text{7207200}};
\node at (95,85){\text{24}};
\node at (105,85){\text{4}};
\node at (115,85){\text{6}};
\node at (126,85){\text{34}};
\node at (5,75){\text{...}};
\node at (5,65){\text{21}};
\node at (40.1,65){\text{253354997095200}};
\node at (95,65){\text{18}};
\node at (105,65){\text{4}};
\node at (115,65){\text{6}};
\node at (126,65){\text{28}};
\node at (5,55){\text{22}};
\node at (40,55){\text{494233458919200}};
\node at (95,55){\text{22}};
\node at (105,55){\text{4}};
\node at (115,55){\text{6}};
\node at (126,55){\text{32}};
\node at (5,45){\text{23}};
\node at (39,45){\text{3013774290727200}};
\node at (95,45){\text{16}};
\node at (105,45){\text{4}};
\node at (115,45){\text{6}};
\node at (126,45){\text{26}};
\node at (138,45){\text{26}};
\node at (5,35){\text{24}};
\node at (38.9,35){\text{3293614962237600}};
\node at (85,35){\text{36}};
\node at (95,35){\text{12}};
\node at (105,35){\text{32}};
\node at (126,35){\text{80}};
\node at (138,35){\text{80}};
\node at (5,25){\text{25}};
\node at (38.8,25){\text{5436568048111200}};
\node at (85,25){\text{50}};
\node at (95,25){\text{32}};
\node at (105,25){\text{26}};
\node at (115,25){\text{2}};
\node at (125.7,25){\text{110}};
\node at (137.7,25){\text{110}};
\node at (5,15){\text{26}};
\node at (37.5,15){\text{21096420035090400}};
\node at (85,15){\text{16}};
\node at (95,15){\text{16}};
\node at (105,15){\text{12}};
\node at (126,15){\text{44}};
\node at (138,15){\text{44}};
\node at (5,5){\text{27}};
\node at (35.5,5){\text{7236072072036007200}};
\node at (95,5){\text{16}};
\node at (105,5){\text{4}};
\node at (115,5){\text{6}};
\node at (126,5){\text{26}};
\node at (138,5){\text{26}};
}$

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


20/08/14
11061
Россия, Москва
Продолжение 13-ек без квадратов:

(494233458919200)

Код:
LCM494233458919200-ch13-pr6-b2850: end, time: 2438.665s
LCM494233458919200-ch13-pr6-b2491: end, time: 2452.304s
LCM494233458919200-ch13-pr5-b4321: end, time: 557.104s
LCM494233458919200-ch13-pr5-b4291: end, time: 558.209s
LCM494233458919200-ch13-pr5-b337: end, time: 557.766s
LCM494233458919200-ch13-pr5-b307: end, time: 557.168s
LCM494233458919200-ch12-pr6-b588: end, time: 2457.405s
LCM494233458919200-ch12-pr6-b580: end, time: 2437.857s
LCM494233458919200-ch12-pr6-b5743: end, time: 2452.426s
LCM494233458919200-ch12-pr6-b5735: end, time: 2437.633s
LCM494233458919200-ch11-pr6-b920: end, time: 2452.813s
LCM494233458919200-ch11-pr6-b913: end, time: 2455.599s
LCM494233458919200-ch11-pr6-b910: end, time: 2440.386s
LCM494233458919200-ch11-pr6-b881: end, time: 6728.161s
LCM494233458919200-ch11-pr6-b872: end, time: 6952.191s
LCM494233458919200-ch11-pr6-b5387: end, time: 7010.812s
LCM494233458919200-ch11-pr6-b5378: end, time: 6996.068s
LCM494233458919200-ch11-pr6-b5323: end, time: 2613.623s
LCM494233458919200-ch11-pr6-b5320: end, time: 2599.706s
LCM494233458919200-ch11-pr6-b5313: end, time: 2597.863s
LCM494233458919200-ch11-pr6-b4850: end, time: 2612.625s
LCM494233458919200-ch11-pr6-b4845: end, time: 2603.900s
LCM494233458919200-ch11-pr6-b4840: end, time: 2600.037s
LCM494233458919200-ch11-pr6-b4798: end, time: 2605.576s
LCM494233458919200-ch11-pr6-b4795: end, time: 2596.451s
LCM494233458919200-ch11-pr6-b4788: end, time: 2571.807s
LCM494233458919200-ch11-pr6-b1349: end, time: 2582.233s
LCM494233458919200-ch11-pr6-b1342: end, time: 2585.870s
LCM494233458919200-ch11-pr6-b1339: end, time: 2555.614s
LCM494233458919200-ch11-pr6-b1296: end, time: 2581.315s
LCM494233458919200-ch11-pr6-b1291: end, time: 2584.556s
LCM494233458919200-ch11-pr6-b1286: end, time: 2569.084s

Yadryara в сообщении #1577057 писал(а):
количество проверяемых мест(CP) весьма велико.
Так как дополнительные простые не расставлялись, то не так уж и велико: от 6 (для LCM>=253354997095200) до 9. Для LCM<=15850052618400 бывает 5 проверяемых мест, а для LCM<=7214407200 и 4 места бывает, до подстановки дополнительных простых в квадратах.

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


29/04/13
7126
Богородский
Dmitriy40 в сообщении #1577063 писал(а):
Так как дополнительные простые не расставлялись, то не так уж и велико: от 6 (для LCM>=253354997095200) до 9.

Я понимаю, что они не расставлялись. Но использовал термин "проверяемые места" в традиционном смысле, ибо раньше-то(с самого начала темы) простые в квадратах расставлялись. С другой стороны, когда делал таблицы для 11-к, указывал именно количество проверяемых мест до расстановки(тогда было от 3 до 7).

Это два разных количества проверяемых мест по идее и обозначать надо по-разному. И вроде бы как раз важнее большее значение CP, ибо для меньших шагов расставлять простые в квадратах всё равно придётся.

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


20/08/14
11061
Россия, Москва
Yadryara в сообщении #1577070 писал(а):
И вроде бы как раз важнее большее значение CP, ибо для меньших шагов расставлять простые в квадратах всё равно придётся.
Но совсем не обязательно весь комплект, ведь для 99.999999% простых достаточно расставить лишь одно и шаг получится достаточно большим для запуска линейного перебора. И лишь для нескольких десятков/сотен наименьших простых придётся расставлять и второе/третье. А четвёртое не придётся никогда потому что линейный перебор будет всегда быстрее квадратичного перебора четвёртого простого, так что CP=13 на практике никогда не достигается. На самом деле не факт что достигнется даже и CP=11 (а CP=12 точно нет), вполне вероятно что выполнить 1e13 итераций линейного перебора (после двух квадратичных) будет быстрее чем запускать ещё один (третий) квадратичный.

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


29/04/13
7126
Богородский
Dmitriy40 в сообщении #1577079 писал(а):
Но совсем не обязательно весь комплект,

Да, вроде бы теперь уже даже для 15-к необязательно весь набор расставлять.

В общем вот две подробные таблички с минимальной и с максимальной расстановками:

(CPmin)

Код:
№                LCM       4   5   6   7   8   9   Total

1                7207200   4  26   4                  34

2               50450400   4  36  56  18             114

3               79279200   4  50  94  16             164

4               93693600   4  36  60  24             124

5              554954400   4  48 124  82  12         270

6              655855200   4  42 108 102   8         264

7             1030629600   4  56 156 142  24         382

8             7214407200   4  50 154 176  34         418

9            17304487200       4  26   4              34

10          105520615200       4  20   4              28

11          190349359200       4  44  74  12         134

12          205844839200       4  24   4              32

13          224958333600       4  34  50  20         108

14          738644306400       4  24  30  14          72

15         1371767997600       4  28  42  20          94

16         1440913874400       4  32  42   4          82

17         2264293231200       4  46  76  12         138

18         2474541669600       4  48 114  90  12     268

19         9602375983200       4  28  60  50         142

20        15850052618400       4  42  88  26         160

21       253354997095200           4  20   4          28

22       494233458919200           4  24   4          32

23      3013774290727200           4  18   4          26

24      3293614962237600           4  26  34  16      80

25      5436568048111200           4  40  58   8     110

26     21096420035090400           4  20  20          44

27   7236072072036007200               4  18   4      26


(CPmax)

Код:
№                LCM        8   9  10  11  12  13   Total

1                7207200               24   4   6      34

2               50450400           48  30  36         114

3               79279200           80  42  40   2     164

4               93693600           64  16  44         124

5              554954400       80  80 102   8         270

6              655855200       84  64 116             264

7             1030629600      140  98 130  14         382

8             7214407200   96 112 186  24             418

9            17304487200               24   4   6      34

10          105520615200               18   4   6      28

11          190349359200           64  36  32   2     134

12          205844839200               22   4   6      32

13          224958333600           56  14  38         108

14          738644306400           24  24  24          72

15         1371767997600           42  14  38          94

16         1440913874400           36  22  24          82

17         2264293231200           64  38  34   2     138

18         2474541669600       96  72  88  12         268

19         9602375983200       36  42  64             142

20        15850052618400       50  50  56   4         160

21       253354997095200               18   4   6      28

22       494233458919200               22   4   6      32

23      3013774290727200               16   4   6      26

24      3293614962237600           36  12  32          80

25      5436568048111200           50  32  26   2     110

26     21096420035090400           16  16  12          44

27   7236072072036007200               16   4   6      26

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


29/04/13
7126
Богородский
Yadryara в сообщении #1577084 писал(а):
В общем вот две подробные таблички с минимальной и с максимальной расстановками:

Это для основных(бесквадратных) 3408 паттернов для 13-к.

Аналогичные сделал и для 14-к, и для 15-к. Если говорить именно о бесквадратных паттернах, то ровно те же все 27 шагов встречаются и в 14-ках:

(14-1044)

Код:
1                7207200     4
2               50450400    28
3               79279200    36
4               93693600    30
5              554954400   100
6              655855200    92
7             1030629600   132
8             7214407200   202
9            17304487200     4
10          105520615200     4
11          190349359200    28
12          205844839200     4
13          224958333600    26
14          738644306400    16
15         1371767997600    26
16         1440913874400    20
17         2264293231200    32
18         2474541669600    90
19         9602375983200    44
20        15850052618400    56
21       253354997095200     4
22       494233458919200     4
23      3013774290727200     4
24      3293614962237600    22
25      5436568048111200    24
26     21096420035090400     8
27   7236072072036007200     4
______________________________
Total                     1044


И в 15-ках:

(15-488)

Код:
1                7207200     2
2               50450400    12
3               79279200    18
4               93693600    14
5              554954400    50
6              655855200    36
7             1030629600    62
8             7214407200    94
9            17304487200     2
10          105520615200     2
11          190349359200    14
12          205844839200     2
13          224958333600    12
14          738644306400     8
15         1371767997600    12
16         1440913874400     8
17         2264293231200    16
18         2474541669600    42
19         9602375983200    20
20        15850052618400    28
21       253354997095200     2
22       494233458919200     2
23      3013774290727200     2
24      3293614962237600    10
25      5436568048111200    12
26     21096420035090400     4
27   7236072072036007200     2
______________________________
Total                      488


Некоторые паттерны с квадратами тоже имеют шаги из этих 27, но большинство — другие.

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


20/08/14
11061
Россия, Москва
Продолжение 13-ек без квадратов:

(253354997095200)

Код:
LCM253354997095200-ch13-pr6-b2843: end, time: 5079.063s
LCM253354997095200-ch13-pr6-b2483: end, time: 5068.133s
LCM253354997095200-ch13-pr5-b4315: end, time: 1151.413s
LCM253354997095200-ch13-pr5-b4284: end, time: 1163.763s
LCM253354997095200-ch13-pr5-b331: end, time: 1154.105s
LCM253354997095200-ch13-pr5-b300: end, time: 1160.482s
LCM253354997095200-ch12-pr6-b578: end, time: 5118.051s
LCM253354997095200-ch12-pr6-b5733: end, time: 4840.702s
LCM253354997095200-ch12-pr6-b5726: end, time: 4831.582s
LCM253354997095200-ch12-pr6-b571: end, time: 4861.637s
LCM253354997095200-ch11-pr6-b870:494423741027766997282272345: 80, 64,  8, 12, 12, 12, 12, 12, 12, 12, 12, 12,  8,  8,128,  valids=9, maxlen=9
LCM253354997095200-ch11-pr6-b870: end, time: 13287.752s
LCM253354997095200-ch11-pr6-b865: end, time: 4948.824s
LCM253354997095200-ch11-pr6-b862: end, time: 13126.166s
LCM253354997095200-ch11-pr6-b5375: end, time: 12980.426s
LCM253354997095200-ch11-pr6-b5370: end, time: 4790.268s
LCM253354997095200-ch11-pr6-b5367:174915780243067459685452441: 16,  8,  8, 12, 12, 12, 12, 12, 12, 12, 12, 12,  4,192, 12,  valids=10, maxlen=9
LCM253354997095200-ch11-pr6-b5367:178559149745874486593567641: 32, 32, 64, 12, 12, 12, 12, 12, 12, 12, 12, 12,  8,192, 64,  valids=9, maxlen=9
LCM253354997095200-ch11-pr6-b5367: end, time: 12924.595s
LCM253354997095200-ch11-pr6-b4838: end, time: 4917.321s
LCM253354997095200-ch11-pr6-b4834: end, time: 4845.819s
LCM253354997095200-ch11-pr6-b4829: end, time: 4845.200s
LCM253354997095200-ch11-pr6-b4786: end, time: 4900.237s
LCM253354997095200-ch11-pr6-b4783: end, time: 5128.707s
LCM253354997095200-ch11-pr6-b4777:347917049663896368011913817: 32,256,  4, 12, 12, 12, 12, 12, 12, 12, 12, 12,  8, 64, 96,  valids=9, maxlen=9
LCM253354997095200-ch11-pr6-b4777:481829708641820137489848217:  4, 32, 32, 12, 12, 12, 12, 12, 12, 12, 12, 12, 16,128, 32,  valids=9, maxlen=9
LCM253354997095200-ch11-pr6-b4777: end, time: 5072.952s
LCM253354997095200-ch11-pr6-b1337: end, time: 5147.920s
LCM253354997095200-ch11-pr6-b1331: end, time: 5070.175s
LCM253354997095200-ch11-pr6-b1328: end, time: 5256.073s
LCM253354997095200-ch11-pr6-b1284: end, time: 5445.505s
LCM253354997095200-ch11-pr6-b1279: end, time: 5228.400s
LCM253354997095200-ch11-pr6-b1275: end, time: 5033.153s
На этом по видимому и закончу, меньшие шаги считаются часов по 20 каждый паттерн.
При этом запускать квадратичный перебор на PARI в полном диапазоне p<2.4e12 для 13 всё ещё невыгодно, даже пустой цикл по простым (с вычислением КТО, реальная скорость у меня составила 2e7/c) будет выполняться порядка 33ч. т.е. для получения выгоды надо кардинально понижать порог -p, что требует нескольких недель отдельного счёта (в одном потоке).

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


29/04/13
7126
Богородский
$\tikz[scale=.08]{
\fill[green!90!blue!50] (0,20) rectangle (81,70);
\fill[green!70!blue!80] (0,0) rectangle (81,20);
\draw  (0,100) rectangle  (10,110);
\draw  (10,100) rectangle  (55,110);
\draw  (55,100) rectangle  (68,110);
\draw  (68,100) rectangle  (81,110);
\draw  (0,90) rectangle  (10,100);
\draw  (10,90) rectangle  (55,100);
\draw  (55,90) rectangle  (68,100);
\draw  (68,90) rectangle  (81,100);
\draw  (0,80) rectangle  (10,90);
\draw  (10,80) rectangle  (55,90);
\draw  (55,80) rectangle  (68,90);
\draw  (68,80) rectangle  (81,90);
\draw  (0,70) rectangle  (10,80);
\draw  (10,70) rectangle  (55,80);
\draw  (55,70) rectangle  (68,80);
\draw  (68,70) rectangle  (81,80);
\draw  (0,60) rectangle  (10,70);
\draw  (10,60) rectangle  (55,70);
\draw  (55,60) rectangle  (68,70);
\draw  (68,60) rectangle  (81,70);
\draw  (0,50) rectangle  (10,60);
\draw  (10,50) rectangle  (55,60);
\draw  (55,50) rectangle  (68,60);
\draw  (68,50) rectangle  (81,60);
\draw  (0,40) rectangle  (10,50);
\draw  (10,40) rectangle  (55,50);
\draw  (55,40) rectangle  (68,50);
\draw  (68,40) rectangle  (81,50);
\draw  (0,30) rectangle  (10,40);
\draw  (10,30) rectangle  (55,40);
\draw  (55,30) rectangle  (68,40);
\draw  (68,30) rectangle  (81,40);
\draw  (0,20) rectangle  (10,30);
\draw  (10,20) rectangle  (55,30);
\draw  (55,20) rectangle  (68,30);
\draw  (68,20) rectangle  (81,30);
\draw  (0,10) rectangle  (10,20);
\draw  (10,10) rectangle  (55,20);
\draw  (55,10) rectangle  (68,20);
\draw  (68,10) rectangle  (81,20);
\draw  (0,0) rectangle  (10,10);
\draw  (10,0) rectangle  (55,10);
\draw  (55,0) rectangle  (68,10);
\draw  (68,0) rectangle  (81,10);
\node at (5,105){\text{№}};
\node at (31,105){\text{LCM}};
\node at (62,105){\text{Pat}};
\node at (75,105){\text{Done}};
\node at (6,95){\text{1}};
\node at (45,95){\text{7207200}};
\node at (63,95){\text{34}};
\node at (5,85){\text{...}};
\node at (37,85){\text{}};
\node at (63,85){\text{}};
\node at (5,75){\text{20}};
\node at (38,75){\text{15850052618400}};
\node at (62,75){\text{160}};
\node at (5,65){\text{21}};
\node at (37,65){\text{253354997095200}};
\node at (63,65){\text{28}};
\node at (75,65){\text{28}};
\node at (5,55){\text{22}};
\node at (37,55){\text{494233458919200}};
\node at (63,55){\text{32}};
\node at (75,55){\text{32}};
\node at (5,45){\text{23}};
\node at (36,45){\text{3013774290727200}};
\node at (63,45){\text{26}};
\node at (75,45){\text{26}};
\node at (5,35){\text{24}};
\node at (35.9,35){\text{3293614962237600}};
\node at (63,35){\text{80}};
\node at (75,35){\text{80}};
\node at (5,25){\text{25}};
\node at (35.8,25){\text{5436568048111200}};
\node at (62,25){\text{110}};
\node at (74,25){\text{110}};
\node at (5,15){\text{26}};
\node at (34.5,15){\text{21096420035090400}};
\node at (62,15){\text{44}};
\node at (75,15){\text{44}};
\node at (5,5){\text{27}};
\node at (32.5,5){\text{7236072072036007200}};
\node at (62,5){\text{26}};
\node at (75,5){\text{26}};
}$

Dmitriy40 в сообщении #1577355 писал(а):
для получения выгоды надо кардинально понижать порог -p, что требует нескольких недель отдельного счёта (в одном потоке).

А кто-нибудь занимается понижением этого порога?

Yadryara в сообщении #1577160 писал(а):
Некоторые паттерны с квадратами тоже имеют шаги из этих 27, но большинство — другие.

Для 14-к и 15-к ещё по 23 различных шага встречаются. Для 13-к — ещё больше. Что, впрочем, уже неактуально.

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


20/08/14
11061
Россия, Москва
Yadryara
Про разные шаги я бы сказал так:
1. Для паттернов с двумя и более квадратами величина шагов не актуальна, они проверяются Пеллем очень быстро (доли секунд).
2. Для паттернов с одним квадратом величина шагов тоже не актуальна, их проще проверять квадратичным перебором. Причём не по каждому простому, а там легко накладываются достаточно неплохие ограничения на это простое и потому перебор идёт с большим шагом (от сотен тысяч до миллиардов). Не всегда он укладывается в секунды и часы (для 14 и 15), но нескольких суток вроде хватает. Да и паттернов таких весьма немного. Макарова кажется почти все их уже проверила.
3. Паттерны без квадратов. Вот тут глухо. Перебор ускорителем даже до 2e33 даже для наибольшего шага требует порядка трёх суток и соответственно порядка 4 месяцев до 8e34. Для меньших шагов время растёт пропорционально. Подключение квадратичных переборов требует перебора простых до порога -p, который для 14 составляет примерно 4.3e15, а для 15 примерно 2.7e16 (все qr<106 запрещены или проверены до конца). Это слишком много. Это многовато даже для 13, где порог примерно 2.3e12 (qr<118 запрещены или проверены).

Yadryara в сообщении #1577514 писал(а):
А кто-нибудь занимается понижением этого порога?
Без понятия. Чем занимается Хуго информации в открытом доступе не видел. А остальные похоже даже не в курсе как и чем и зачем можно уменьшать порог (готовую программу Хуго не даёт, только исходник) ...

Я несколько раз порывался запустить счёт, но каждый раз увидев оценку времени понимал что выгоднее поступать по другому: каждое конкретное значение qr будет проверяться примерно сутки (здесь и далее везде для счёта в один поток), разных qr<600 чтобы получить -p1e12 (что всё равно слишком много) примерно 150 штук, т.е. грубо надо 5 месяцев на такое уменьшение порога, но очень многие из этих qr или запрещены, или можно проверить относительно быстро (сильно быстрее суток), но надо для каждого руками проверять какие разрешены (программа выходит слишком сложной) и писать отдельную программу перебора (универсальная опять же выходит слишком сложной).

Пытался подойти к этому вопросу с другой стороны: перебрать на асме быстро все большие простые (которые дают и шаг паттерна и начальное число больше порога, ведь это 99% всего квадратичного перебора), но вычисление обратного элемента в кольце по модулю страшно медленно даже на асме, PARI применяет КТО со скоростью примерно 2e7/c (везде указываю интервал, не штуки), а асм простые генерит почти 1e9/c, но обратный элемент (нужный для КТО по схеме Гарнера) лишь 4e7/c, всего вдвое быстрее PARI, это грустно. К счастью обратный элемент можно вычислить лишь один раз для каждого простого в квадрате и каждого шага (он из этой пары и вычисляется), независимо от паттерна с таким шагом, а дальше или быстрые умножения или даже и без них, но это значит встраивать в цикл перебора простых ещё и перебор шагов паттернов, а потом ещё и перебор самих паттернов и возможных мест в них, что совершенно очевидно заметно замедлит и без того медленный перебор простых с вычислением обратного элемента, т.е. скорость упадёт с 4e7/с до скажем 1e7/с и на перебор простых до 2.3e12 понадобится дня три (хотя скорее неделя-две), плюс проверка не отброшенных простых в PARI. Зато это позволит уменьшить порог практически до 1e9-1e10 (как только доля подходящих простых упадёт до долей процента). Ценой встраивания в асм код двух дополнительных циклов по реальным паттернам (от них нужно как минимум начальное число до подстановки дополнительных простых, а лучше и список допустимых мест). При этом на PARI ровно тот же перебор возможных мест в паттернах с однократным вычислением обратного элемента идёт со скоростью 5e6/c (для 5-ти мест, что довольно часто), так что ускорение от переписывания на асм похоже менее чем двойное, а трудности многократные. На PARI перебрать простые до 2.3e12 потребует порядка недели на каждый из 3000 паттернов ... Возможно на асм снижение скорости будет не таким сильным, но она в любом случае не превысит скорости вычисления обратного элемента 4e7/с, т.е. для вычисления всех обратных элементов для p<2.3e12 и 20 разных шагов надо порядка двух недель, ну и плюс проверка начального числа, в итоге несколько месяцев, в принципе достижимо ...

Есть и другая идея: каждое конкретное qr допустимо не для каждого паттерна, некоторые или попадают на занятые места, или не дают нужных остатков по уже расставленным простым. Конечно это как раз и есть те запреты выше, но возможно проверить конкретное qr по списку конкретных паттернов будет проще чем пытаться запретить qr для любых. Но эта идея пришла только вчера и реализовать пока не успел, прикидочная оценка даёт что для qr=106 для 13-ек из 3408 паттернов подходит около 400, в остальные $106p^2$ не вставляется. Это хорошо, возможно получится написать более-менее универсальную программу перебора для каждого qr только подходящих паттернов, ведь там в каждом можно наложить сильные ограничения на $p$ и перебирать их с большим шагом (как и делал руками, а тут будет автоматически). Насколько это просто и выгодно оценок пока не сделал.

Но всё это практически неприменимо к 14 и 15, слишком велик там порог -p, надо выдумывать что-то ещё. Даже просто генерация простых до 2.7e16 займёт порядка года, а ещё ведь по любому надо делать гораздо более медленные проверки ...
И пока совершенно непонятно куда бы тут эффективно прилепить SSE/AVX (кроме одного места с проверкой мест паттернов после вычисления обратного элемента в кольце по модулю). А без SSE/AVX скорость как-то не сильно от PARI отличается и за что тогда бороться непонятно.

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


11/12/16
13195
уездный город Н
Dmitriy40
Некоторые мысли, на уровне потока сознания :roll: :wink:

Рассмотрим какое-то конкретное место в конкретном паттерне, где нужно поставить $p^2qr$, при этом все три простых числа неизвестны. То есть $p,q,r > 13$

В паттерне обязательно есть и зафиксированы числа:
а) кратные $32$
б) кратные $9$
в) кратные $25$
г) кратные $7$
д) кратные $11$
е) кратные $13$

То есть остатки по этим шести модулям для числа $p^2qr$ зафиксированы и известны.
$qr$ дают все возможные остатки. А вот $p^2$ даёт не все возможные остатки. Поэтому далеко не все $qr$ возможны в данной позиции для данного паттерна.

Считаем.
а) $32$. $p^2$ "разрешает" 4 остатка из 16. То есть из всех $qr$ подходит только четверть.
б) $9$. Остатки $0$ и $3$ запрещены. Всего $7$ остатков, из них $p^2$ "разрешает" только три. То есть из всех $qr$ подходит только $3/7$ вариантов.
в) $25$. Остатки $0$ и $5$ запрещены. Всего $23$ остатков, из них $p^2$ "разрешает" только десять. То есть из всех $qr$ подходит только $10/23$ вариантов.
г) $7$. Остаток $0$ запрещен. Всего $6$ остатков, из них $p^2$ "разрешает" только три. То есть из всех $qr$ подходит только $3/6 = 1/2$ вариантов.
д) $11$. Остаток $0$ запрещен. Всего $10$ остатков, из них $p^2$ "разрешает" только пять. То есть из всех $qr$ подходит только $5/10 = 1/2$ вариантов.
е) $13$. Остаток $0$ запрещен. Всего $12$ остатков, из них $p^2$ "разрешает" только шесть. То есть из всех $qr$ подходит только $6/12 = 1/2$ вариантов.

Перемножаем:
$k = (1/4)(3/7)(10/23)(1/2)^3=0.0058$

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

Если паттерном фиксируются квадраты $7$, $11$, $13$, то доля "подходящих" $qr$ окажется ещё меньше.

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


29/04/13
7126
Богородский
Dmitriy40 в сообщении #1577558 писал(а):
Конечно это как раз и есть те запреты выше, но возможно проверить конкретное qr по списку конкретных паттернов будет проще чем пытаться запретить qr для любых.

Можно попробовать прогнать по модулям.

EUgeneUS в сообщении #1577620 писал(а):
Рассмотрим какое-то конкретное место в конкретном паттерне, где нужно поставить $p^2qr$, при этом все три простых числа неизвестны.

Кстати, вот стата по оставшимся 3062 паттернам:

Код:
p^2qr    Pat
0        190
1       1014
2       1252
3        562
4         44


Ну то есть 190 паттернов таких пустых мест не содержат, а 44 паттерна имеют по 4 пустых места.

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


20/08/14
11061
Россия, Москва
EUgeneUS
В принципе всё верно.
За малыми тонкостями: есть паттерны без свободных мест, например b34 для D12n13, туда $p^2qr$ вообще не поставишь (а вот к примеру $qr=129$ вполне ставится в позицию 32p+1); не во всех паттернах обязано быть $25$, пятёрка может остаться и только в первой степени (UPD: а, нет, не может, квадрат есть всегда). Потому правильнее считать не разрешённые варианты, а точно запрещённые. Но в целом да, всё так и есть.
И ещё момент: да, в конкретное место попадает очень мало вариантов qr, но вот вообще в паттерн, на любое место, уже нет, уже сильно больше, примерно $1-(1-0.0058)^7=0.04$ (для паттернов с 7-ю возможными местами, как например тот же b34), уже 4%. Но вот например для 22<qr<600 есть 171 вариант, из которых реально в 217 паттернах из 3408 встречаются лишь qr=129,253,262,323,362,394,469,473,497,551,566,597 (и 106 который проверил выше 6e26 и дальше не учитываю), причём не более чем три из них. И на пустых местах встречаются лишь по одному (323 или 551), по два и по три только на местах с простыми (т.е. 323 и 551 "не спариваются" с прочими в одном паттерне). И каждое qr только на своём месте (относительно 32p).

Yadryara в сообщении #1577630 писал(а):
Можно попробовать прогнать по модулям.
Да, уже только что сделал:
Dmitriy40 в сообщении #1577558 писал(а):
Есть и другая идея: каждое конкретное qr допустимо не для каждого паттерна, некоторые или попадают на занятые места, или не дают нужных остатков по уже расставленным простым.
...
Насколько это просто и выгодно оценок пока не сделал.
Вот и добавил в программу проверку запрета конкретных qr, оказалось из $171\cdot3408=582768$ встречаются лишь 298 вариантов. Теперь интересно сколько времени займёт перебор простых в квадрате во всех этих 298 вариантах, меньше 170 дней (сколько заняло бы обычное уменьшение порога до 1e12) или нет. ;-) И меньше ли двух недель если порог уменьшать до 1e12 обычным способом только по вот этим найденным qr.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 3216 ]  На страницу Пред.  1 ... 199, 200, 201, 202, 203, 204, 205 ... 215  След.

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



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

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


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

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