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

[Yadryara]

EUgeneUS в сообщении #1571742 писал(а):

Если оценивать машино-часы, а не штуки, то до экватора,

Ну так я же неслучайно написал

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

Приближаемся к своеобразному экватору.

EUgeneUS в сообщении #1571742 писал(а):

По моим оценкам только-только перевалили 10%.

Что-то я подозреваю, что эта оценка основана на предположении, что меньшую 11-ку найти так и не удастся. Нынешний рекорд вроде бы по-прежнему 9.89e21.

[Dmitriy40]

Yadryara
Добил и следующий LCM:

(Оффтоп)

T:\M12minimal\Hugo>for /f "tokens=4 delims=*, " %p in (D12n11-list) do @pcoul.exe -rD12n11-%p.txt -x1e22 -f11 -g12 -p6e7 -v -%p 12 11
path D12n11-b1565.txt
001 pcoul(12 11) -p60000000 -f11 -g12 -x10000000000000000000000 -b1565 *RT*
2 3 2^2.7 5 2.3^2 11.51825743^2 2^5 3 2.5^2 7^5 2^2.3
367 coul(12, 11): recurse 726670593, walk 727109578, walkc 1208440121 (2987.75s)
path D12n11-b1530.txt
001 pcoul(12 11) -p60000000 -f11 -g12 -x10000000000000000000000 -b1530 *RT*
2 3 2^2.11 5 2.3^2 7^5 2^5 3 2.5^2 41^5 2^2.3: 23619 / 32421
367 coul(12, 11): recurse 730234454, walk 730673729, walkc 1213827302 (2921.80s)
path D12n11-b1492.txt
001 pcoul(12 11) -p60000000 -f11 -g12 -x10000000000000000000000 -b1492 *RT*
2 3 2^2.5 29^5 2.3^2 7^5 2^5 3.5^2 2 11 2^2.3: 179721 / 183132
367 coul(12, 11): recurse 730234454, walk 730634017, walkc 1213827596 (2903.96s)
path D12n11-b1488.txt
001 pcoul(12 11) -p60000000 -f11 -g12 -x10000000000000000000000 -b1488 *RT*
2 3 2^2.5 11 2.3^2 7^5 2^5 3.5^2 2 23^5 2^2.3: 414144 / 583600
367 coul(12, 11): recurse 730234454, walk 730634017, walkc 1213827451 (2880.62s)
path D12n11-b1190.txt
001 pcoul(12 11) -p60000000 -f11 -g12 -x10000000000000000000000 -b1190 *RT*
41^5 2^2.3 . 2 3.5^2 2^5 7^5 2.3^2 11 2^2.5 3: 14100 / 32421
367 coul(12, 11): recurse 730489936, walk 730601432, walkc 1214094261 (2934.66s)
path D12n11-b1186.txt
001 pcoul(12 11) -p60000000 -f11 -g12 -x10000000000000000000000 -b1186 *RT*
67^5 2^2.3 11 2 3.5^2 2^5 7^5 2.3^2 . 2^2.5 3: 1867 / 2781
367 coul(12, 11): recurse 730489936, walk 730601432, walkc 1214095374 (2935.02s)
path D12n11-b1182.txt
001 pcoul(12 11) -p60000000 -f11 -g12 -x10000000000000000000000 -b1182 *RT*
11 2^2.3 23^5 2 3.5^2 2^5 7^5 2.3^2 . 2^2.5 3: 383000 / 583600
367 coul(12, 11): recurse 730489936, walk 730601432, walkc 1214094692 (2906.20s)
path D12n11-b1147.txt
001 pcoul(12 11) -p60000000 -f11 -g12 -x10000000000000000000000 -b1147 *RT*
23^5 2^2.3 . 2.5^2 3 2^5 7^5 2.3^2 5 2^2.11 3: 430590 / 583600
367 coul(12, 11): recurse 730489936, walk 730617208, walkc 1214094668 (2936.36s)
path D12n11-b1144.txt
001 pcoul(12 11) -p60000000 -f11 -g12 -x10000000000000000000000 -b1144 *RT*
23^5 2^2.3 11 2.5^2 3 2^5 7^5 2.3^2 5 2^2 3: 489699 / 583599
367 coul(12, 11): recurse 730234454, walk 730622649, walkc 1213826756 (2924.55s)
path D12n11-b1141.txt
001 pcoul(12 11) -p60000000 -f11 -g12 -x10000000000000000000000 -b1141 *RT*
11 2^2.3 23^5 2.5^2 3 2^5 7^5 2.3^2 5 2^2 3: 263294 / 583599
367 coul(12, 11): recurse 730234454, walk 730622649, walkc 1213827150 (2685.17s)
path D12n11-b1103.txt
001 pcoul(12 11) -p60000000 -f11 -g12 -x10000000000000000000000 -b1103 *RT*
19^5 2^2.3 7^5 2.5^2 3 2^5 11 2.3^2 5 2^2.7 3: 1501197 / 1517002
367 coul(12, 11): recurse 730234454, walk 730622649, walkc 1213827794 (2902.02s)
path D12n11-b1086.txt
001 pcoul(12 11) -p60000000 -f11 -g12 -x10000000000000000000000 -b1086 *RT*
3 2^2.7 5 2.3^2 23^5 2^5 3 2.5^2 7^5 2^2.3 11: 356139 / 583599
367 coul(12, 11): recurse 730234454, walk 730622649, walkc 1213826542 (2945.27s)
path D12n11-b1082.txt
001 pcoul(12 11) -p60000000 -f11 -g12 -x10000000000000000000000 -b1082 *RT*
3 2^2.7 5 2.3^2 11 2^5 3 2.5^2 7^5 2^2.3 37^5: 33346 / 54168
367 coul(12, 11): recurse 730234454, walk 730622649, walkc 1213826618 (2939.15s)
path D12n11-b1037.txt
001 pcoul(12 11) -p60000000 -f11 -g12 -x10000000000000000000000 -b1037 *RT*
. 2.5^2 3 2^2 . 2.3^2 5.7^2 2^5 3 2 .
367 coul(12, 11): recurse 730234454, walk 730622649, walkc 1213828381 (2853.30s)
path D12n11-b1028.txt
001 pcoul(12 11) -p60000000 -f11 -g12 -x10000000000000000000000 -b1028 *RT*
3 2^2.11 5 2.3^2 7^5 2^5 3 2.5^2 29^5 2^2.3 .: 69703 / 183131
367 coul(12, 11): recurse 730489936, walk 730617208, walkc 1214094391 (2892.88s)
path D12n11-b985.txt
001 pcoul(12 11) -p60000000 -f11 -g12 -x10000000000000000000000 -b985 *RT*
3 2^2.5 29^5 2.3^2 7^5 2^5 3.5^2 2 . 2^2.3 11: 51245 / 183131
367 coul(12, 11): recurse 730489936, walk 730601432, walkc 1214095397 (2895.05s)
path D12n11-b982.txt
001 pcoul(12 11) -p60000000 -f11 -g12 -x10000000000000000000000 -b982 *RT*
3 2^2.5 29^5 2.3^2 7^5 2^5 3.5^2 2 11 2^2.3 .: 148826 / 183132
367 coul(12, 11): recurse 730489936, walk 730601432, walkc 1214095203 (2894.24s)
path D12n11-b978.txt
001 pcoul(12 11) -p60000000 -f11 -g12 -x10000000000000000000000 -b978 *RT*
3 2^2.5 11 2.3^2 7^5 2^5 3.5^2 2 23^5 2^2.3 .: 240744 / 583600
367 coul(12, 11): recurse 730489936, walk 730601432, walkc 1214094836 (2893.90s)
path D12n11-b637.txt
001 pcoul(12 11) -p60000000 -f11 -g12 -x10000000000000000000000 -b637 *RT*
2^2.3 23^5 2 3.5^2 2^5 7^5 2.3^2 11 2^2.5 3 2: 367009 / 583599
367 coul(12, 11): recurse 730234454, walk 730634017, walkc 1213827417 (2931.04s)
path D12n11-b633.txt
001 pcoul(12 11) -p60000000 -f11 -g12 -x10000000000000000000000 -b633 *RT*
2^2.3 11 2 3.5^2 2^5 7^5 2.3^2 31^5 2^2.5 3 2: 1781 / 131202
367 coul(12, 11): recurse 730234454, walk 730634017, walkc 1213827128 (2910.85s)
path D12n11-b604.txt
001 pcoul(12 11) -p60000000 -f11 -g12 -x10000000000000000000000 -b604 *RT*
2^2.3 23^5 2.5^2 3 2^5 7^5 2.3^2 5 2^2.11 3 2: 362588 / 583599
367 coul(12, 11): recurse 730234454, walk 730673729, walkc 1213827337 (2927.76s)
path D12n11-b601.txt
001 pcoul(12 11) -p60000000 -f11 -g12 -x10000000000000000000000 -b601 *RT*
2^2.3 11.56214617^2 2.5^2 3 2^5 7^5 2.3^2 5 2^2 3 2
367 coul(12, 11): recurse 726670593, walk 727109578, walkc 1208439867 (2897.58s)
path D12n11-b290.txt
001 pcoul(12 11) -p60000000 -f11 -g12 -x10000000000000000000000 -b290 *RT*
19^5 2 3 2^5 5 2.3^2 7^5 2^2 3 2.5^2 11: 1477049 / 1517003
367 coul(12, 11): recurse 730234454, walk 730622649, walkc 1213827132 (2910.90s)
path D12n11-b286.txt
001 pcoul(12 11) -p60000000 -f11 -g12 -x10000000000000000000000 -b286 *RT*
47^5 2 3 2^5 5 2.3^2 7^5 2^2.11 3 2.5^2 .: 586 / 16377
367 coul(12, 11): recurse 730489936, walk 730617208, walkc 1214094419 (2907.78s)
path D12n11-b282.txt
001 pcoul(12 11) -p60000000 -f11 -g12 -x10000000000000000000000 -b282 *RT*
11 2 3 2^5 5 2.3^2 7^5 2^2 3 2.5^2 29^5: 39371 / 183132
367 coul(12, 11): recurse 730234454, walk 730622649, walkc 1213827267 (2659.78s)
path D12n11-b243.txt
001 pcoul(12 11) -p60000000 -f11 -g12 -x10000000000000000000000 -b243 *RT*
7^5 2 3 2^5 5 2.3^2 31^5 2^2.7 3 2.5^2 11: 11768 / 131203
367 coul(12, 11): recurse 730234454, walk 730622649, walkc 1213826915 (2547.92s)
path D12n11-b239.txt
001 pcoul(12 11) -p60000000 -f11 -g12 -x10000000000000000000000 -b239 *RT*
7^5 2 3 2^5 5 2.3^2 11 2^2.7 3 2.5^2 23^5: 410217 / 583599
367 coul(12, 11): recurse 730234454, walk 730622649, walkc 1213826492 (2546.67s)
path D12n11-b73.txt
001 pcoul(12 11) -p60000000 -f11 -g12 -x10000000000000000000000 -b73 *RT*
7^5 2.5^2 3 2^5 23^5 2.3^2 5 2^2.7 3 2 11: 172103 / 583600
367 coul(12, 11): recurse 730234454, walk 730622649, walkc 1213826306 (2544.47s)
path D12n11-b66.txt
001 pcoul(12 11) -p60000000 -f11 -g12 -x10000000000000000000000 -b66 *RT*
7^5 2.5^2 3 2^5 11 2.3^2 5 2^2.7 3 2 23^5: 283145 / 583599
367 coul(12, 11): recurse 730234454, walk 730622649, walkc 1213826879 (2545.03s)
path D12n11-b29.txt
001 pcoul(12 11) -p60000000 -f11 -g12 -x10000000000000000000000 -b29 *RT*
5 2.3^2 23^5 2^5 3 2.5^2 7^5 2^2.3 11 2 3^2.5: 536124 / 583599
367 coul(12, 11): recurse 730234454, walk 730622649, walkc 1213826542 (2234.71s)
path D12n11-b25.txt
001 pcoul(12 11) -p60000000 -f11 -g12 -x10000000000000000000000 -b25 *RT*
5 2.3^2 11 2^5 3 2.5^2 7^5 2^2.3 19^5 2 3^2.5: 1452441 / 1517003
367 coul(12, 11): recurse 730234454, walk 730622649, walkc 1213826618 (2224.74s)

[Yadryara]

Объединённая таблица по данным на сегодня.

$\tikz[scale=.08]{ \fill[green!90!blue!50] (110,160) rectangle (125,210); \fill[green!90!blue!50] (85,170) rectangle (95,180); \fill[green!90!blue!50] (0,140) rectangle (140,170); \fill[green!70!blue!80] (0,120) rectangle (140,140); \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 (118,205){\text{4}}; \node at (133,205){\text{5 ?}}; \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{26}}; \node at (133,195){\text{9 ?}}; \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{31}}; \node at (133,185){\text{2 ?}}; \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{56}}; \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{66}}; \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{58}}; \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}}; }$

Всего полностью обсчитаны хотя бы однократно $ 4 + 26 + 31 + 56 + 66 + 58 + 152 + 96 + 58 = 547 $ паттернов из $1044$ основных. Количество таких паттернов возросло на 40 по сравнению с предыдущей таблицей.

Конкретика по всем 4 ещё не полностью обсчитанным шагам:

(554400-4(66))

 1. b111 :LCM554400-175545-4
 2. b1619:LCM554400-283545-7
 3. b1624:LCM554400-434745-7
 4. b1952:LCM554400-81049-8

(3880800-26(142))

  1. b133 :LCM3880800-3674745-4
  2. b141 :LCM3880800-1816569-4
  3. b143 :LCM3880800-3580569-4
  4. b521 :LCM3880800-1509241-5
  5. b528 :LCM3880800-3626041-5
  6. b532 :LCM3880800-2567641-5
  7. b537 :LCM3880800-2337241-5
  8. b542 :LCM3880800-3042841-5
  9. b553 :LCM3880800-2697241-5
 10. b559 :LCM3880800-933241-5
 11. b563 :LCM3880800-3755641-5
 12. b564 :LCM3880800-3660345-5
 13. b568 :LCM3880800-1543545-5
 14. b592 :LCM3880800-729945-5
 15. b594 :LCM3880800-2493945-5
 16. b596 :LCM3880800-2846745-5
 17. b1600:LCM3880800-837945-7
 18. b1601:LCM3880800-3660345-7
 19. b1605:LCM3880800-1543545-7
 20. b1629:LCM3880800-1313145-7
 21. b1632:LCM3880800-254745-7
 22. b1635:LCM3880800-2018745-7
 23. b1928:LCM3880800-1744249-8
 24. b2102:LCM3880800-681241-8
 25. b1637:LCM3880800-2371545-7
 26. b2002:LCM3880800-1589017-8

(6098400-31(180))

  1. b112 :LCM6098400-1334745-4
  2. b113 :LCM6098400-3048345-4
  3. b114 :LCM6098400-4761945-4
  4. b116 :LCM6098400-377145-4
  5. b117 :LCM6098400-1233945-4
  6. b118 :LCM6098400-2090745-4
  7. b167 :LCM6098400-2673369-4
  8. b168 :LCM6098400-5243769-4
  9. b169 :LCM6098400-858969-4
 10. b172 :LCM6098400-2572569-4
 11. b173 :LCM6098400-3429369-4
 12. b174 :LCM6098400-4286169-4
 13. b511 :LCM6098400-3950041-5
 14. b512 :LCM6098400-5663641-5
 15. b517 :LCM6098400-4706041-5
 16. b520 :LCM6098400-5562841-5
 17. b581 :LCM6098400-3105945-5
 18. b582 :LCM6098400-4819545-5
 19. b583 :LCM6098400-434745-5
 20. b586 :LCM6098400-2148345-5
 21. b587 :LCM6098400-3861945-5
 22. b588 :LCM6098400-4718745-5
 23. b1616:LCM6098400-535545-7
 24. b1617:LCM6098400-1392345-7
 25. b1620:LCM6098400-3105945-7
 26. b1621:LCM6098400-4819545-7
 27. b1622:LCM6098400-434745-7
 28. b1625:LCM6098400-2148345-7
 29. b1940:LCM6098400-383449-8
 30. b2134:LCM6098400-378841-8
 31. b2015:LCM6098400-3554617-8

(42688800-56(226))

  1. b0   :LCM42688800-30086041-4
  2. b11  :LCM42688800-19502041-4
  3. b41  :LCM42688800-19631641-4
  4. b42  :LCM42688800-3050041-4
  5. b43  :LCM42688800-29157241-4

  6. b121 :LCM42688800-28370745-4
  7. b124 :LCM42688800-11789145-4
  8. b125 :LCM42688800-37896345-4
  9. b129 :LCM42688800-4733145-4
 10. b130 :LCM42688800-17786745-4
 11. b131 :LCM42688800-30840345-4
 12. b139 :LCM42688800-1816569-4   
 13. b142 :LCM42688800-14870169-4  
 14. b144 :LCM42688800-37449369-4  
 15. b147 :LCM42688800-20867769-4
 16. b177 :LCM42688800-6172569-4

 17. b522 :LCM42688800-30086041-5
 18. b523 :LCM42688800-13504441-5
 19. b526 :LCM42688800-23030041-5
 20. b530 :LCM42688800-6448441-5
 21. b533 :LCM42688800-19502041-5
 22. b534 :LCM42688800-34442041-5

 23. b535: LCM42688800-17860441-5
 24. b540 :LCM42688800-10804441-5
 25. b543 :LCM42688800-23858041-5
 26. b554 :LCM42688800-19631641-5
 27. b555 :LCM42688800-3050041-5
 28. b556 :LCM42688800-29157241-5
 29. b557 :LCM42688800-12575641-5
 30. b561 :LCM42688800-38682841-5
 31. b565 :LCM42688800-41409945-5
 32. b566 :LCM42688800-24828345-5
 33. b569 :LCM42688800-8246745-5
 34. b570 :LCM42688800-34353945-5
 35. b571 :LCM42688800-4718745-5
 36. b590 :LCM42688800-24014745-5
 37. b593 :LCM42688800-7433145-5
 38. b597 :LCM42688800-377145-5
 39. b598 :LCM42688800-13430745-5

 40. b1602:LCM42688800-41409945-7
 41. b1603:LCM42688800-24828345-7
 42. b1606:LCM42688800-8246745-7
 43. b1626:LCM42688800-23186745-7
 44. b1627:LCM42688800-36240345-7
 45. b1630:LCM42688800-19658745-7
 46. b1633:LCM42688800-29184345-7
 47. b1636:LCM42688800-12602745-7

 48. b1836:LCM42688800-4005945-8
 49. b1839:LCM42688800-30113145-8
 50. b1842:LCM42688800-13531545-8    *
 51. b1843:LCM42688800-39638745-8
 52. b1844:LCM42688800-23057145-8
 53. b1874:LCM42688800-23186745-8
 54. b1884:LCM42688800-12602745-8
 55. b1926:LCM42688800-21148249-8
 56. b1999:LCM42688800-23462617-8

Далеко не все сообщают о том, какие паттерны в работе. Блог недоступен, но я вроде разобрался:

(Work)

b115 :LCM554400-74745-4
b120 :LCM554400-427545-4
b166 :LCM554400-153369-4
b171 :LCM554400-304569-4
b176 :LCM554400-405369-4

b123 :LCM3880800-1205145-4
b127 :LCM3880800-2969145-4
b128 :LCM3880800-3321945-4
b146 :LCM3880800-2522169-4
b151 :LCM3880800-405369-4
b179 :LCM3880800-2291769-4
b183 :LCM3880800-174969-4
b184 :LCM3880800-2997369-4
b189 :LCM3880800-880569-4

b109 :LCM6098400-5719545-4
b164 :LCM6098400-1816569-4

b148 :LCM42688800-33921369-4
b149 :LCM42688800-4286169-4
b180 :LCM42688800-19226169-4
b181 :LCM42688800-15698169-4
b185 :LCM42688800-25223769-4
b186 :LCM42688800-38277369-4
b187 :LCM42688800-8642169-4

[Dmitriy40]

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

pcoul will allocate to an empty spot first. If a solution exists with $p^2qr$ at that empty spot and $2s^2t$ at another spot, we will skip it if $p > Z$ because $p$ "has been checked by sq12".

You're right, the idea doesn't work when placed in empty spaces. Alas.

[Huz]

Dmitriy40 I really don't fully understand why, but implementing (my understanding of) your "two-stage booster" approach so far seems to give very good results - I think even better than you had predicted.

I still have some work to do: first, to prove that it checks everything that it should; second, to modify progress reports and update the recovery process to take the new process into account.

The approach I have used is to add a new parameter "-W<walk_prime>"; it is currently supported only when running for a single pattern, and only with "-p<pmax>". The semantics are: if walk_prime is set, then we first locate the required pattern; then we iterate over each prime $p$ between walk_prime and pmax; for each p, we try allocating $p^2$ at each possible location, and whenever the allocation is successful we directly invoke a linear search (the function walk_v()). Once all $p$ have been tried, we continue with the normal process as if walk_prime was actually the requested pmax.

(For now, it is up to the caller to make sure of other requirements, such as that the number of divisors is a multiple of 3, and that $p^5 > \max$.)

I have tested it only on simpler patterns so far:

./pcoul -x:9887353188984012120346 -f11 -b1490 -p1e7 -g11 12 11
Without -W: 226.80s
-W5e6: 173.33s
-W1e6: 91.07s
# Note: p^5 < max for the remaining tests
-W1e5: 42.18s
-W1e4: 32.97s
-W1e3: 145.05s
-W9e3: 32.97s
-W9500: 32.74s

./pcoul -x:9887353188984012120346 -f11 -b1481 -p1e7 -g11 12 11
Without -W: 5234.00s
-W1e6: 1980.47s
-W5e5: 1529.46s
-W25e4: 1234.86s
# Note: p^5 < max for the remaining tests
-W12e4: 1081.17s
-W1e5: 1049.12s

Next will be tests with b1619 (LCM 554400), but they will take rather longer.

[Dmitriy40]

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

I really don't fully understand why, but implementing (my understanding of) your "two-stage booster" approach so far seems to give very good results

It works because we are replacing repeatedly called code with once, albeit with a large amount of iterations. Not the code itself of course, but the interval of its execution. Accordingly it will be useful only on the second and deeper levels of recursion (the first is always called only once) and only if they are called a sufficient number of times (more than 200-400). And the more times they are called, the greater the gain.
And yes, I don't think it makes sense to lower the threshold below 22e3, where the fifth degrees come into play.

[Yadryara]

Объединённая таблица по данным на сегодня.

$\tikz[scale=.08]{ \fill[green!90!blue!50] (110,160) rectangle (125,210); \fill[green!90!blue!50] (85,170) rectangle (95,180); \fill[green!90!blue!50] (0,140) rectangle (140,170); \fill[green!70!blue!80] (0,120) rectangle (140,140); \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 (118,205){\text{6}}; \node at (133,205){\text{5 ?}}; \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{42}}; \node at (133,195){\text{2 ?}}; \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{36}}; \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{75}}; \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{66}}; \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{58}}; \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}}; }$

Всего полностью обсчитаны хотя бы однократно $ 6 + 42 + 36 + 75 + 66 + 58 + 152 + 96 + 58 = 589 $ паттернов из $1044$ основных. Количество таких паттернов возросло на 42 по сравнению с предыдущей таблицей.

Некоторые сомнения вызывает паттерн b628, который не помечен красным. Неужто так быстро был полностью обсчитан?

Конкретика по всем 4 ещё не полностью обсчитанным шагам:

(554400-6(66))

 1. b111 :LCM554400-175545-4
 2. b519 :LCM554400-270841-5
 3. b1619:LCM554400-283545-7
 4. b1624:LCM554400-434745-7
 5. b1942:LCM554400-383449-8
 6. b1952:LCM554400-81049-8

(3880800-42(142))

  1. b123 :LCM3880800-1205145-4
  2. b128 :LCM3880800-3321945-4
  3. b133 :LCM3880800-3674745-4
  4. b141 :LCM3880800-1816569-4
  5. b143 :LCM3880800-3580569-4
  6. b151 :LCM3880800-405369-4
  7. b179 :LCM3880800-2291769-4
  8. b183 :LCM3880800-174969-4
  9. b184 :LCM3880800-2997369-4
 10. b189 :LCM3880800-880569-4
 11. b521 :LCM3880800-1509241-5
 12. b525 :LCM3880800-1862041-5
 13. b528 :LCM3880800-3626041-5
 14. b532 :LCM3880800-2567641-5
 15. b537 :LCM3880800-2337241-5
 16. b542 :LCM3880800-3042841-5
 17. b553 :LCM3880800-2697241-5
 18. b559 :LCM3880800-933241-5
 19. b563 :LCM3880800-3755641-5
 20. b564 :LCM3880800-3660345-5
 21. b568 :LCM3880800-1543545-5
 22. b592 :LCM3880800-729945-5
 23. b594 :LCM3880800-2493945-5
 24. b596 :LCM3880800-2846745-5
 25. b628 :LCM3880800-2522169-5
 26. b1600:LCM3880800-837945-7
 27. b1601:LCM3880800-3660345-7
 28. b1605:LCM3880800-1543545-7
 29. b1629:LCM3880800-1313145-7
 30. b1632:LCM3880800-254745-7
 31. b1635:LCM3880800-2018745-7
 32. b1637:LCM3880800-2371545-7
 33. b1838:LCM3880800-125145-8
 34. b1841:LCM3880800-2947545-8
 35. b1928:LCM3880800-1744249-8
 36. b1960:LCM3880800-1513849-8
 37. b1998:LCM3880800-3705817-8
 38. b2002:LCM3880800-1589017-8
 39. b2040:LCM3880800-2064217-8
 40. b2102:LCM3880800-681241-8
 41. b2111:LCM3880800-3150841-8
 42. b2156:LCM3880800-220441-8

(6098400-36(180))

  1. b112 :LCM6098400-1334745-4
  2. b113 :LCM6098400-3048345-4
  3. b114 :LCM6098400-4761945-4
  4. b116 :LCM6098400-377145-4
  5. b117 :LCM6098400-1233945-4
  6. b118 :LCM6098400-2090745-4
  7. b164 :LCM6098400-1816569-4
  8. b167 :LCM6098400-2673369-4
  9. b168 :LCM6098400-5243769-4
 10. b169 :LCM6098400-858969-4
 11. b172 :LCM6098400-2572569-4
 12. b173 :LCM6098400-3429369-4
 13. b174 :LCM6098400-4286169-4
 14. b511 :LCM6098400-3950041-5
 15. b512 :LCM6098400-5663641-5
 16. b517 :LCM6098400-4706041-5
 17. b520 :LCM6098400-5562841-5
 18. b581 :LCM6098400-3105945-5
 19. b582 :LCM6098400-4819545-5
 20. b583 :LCM6098400-434745-5
 21. b586 :LCM6098400-2148345-5
 22. b587 :LCM6098400-3861945-5
 23. b588 :LCM6098400-4718745-5
 24. b1616:LCM6098400-535545-7
 25. b1617:LCM6098400-1392345-7
 26. b1620:LCM6098400-3105945-7
 27. b1621:LCM6098400-4819545-7
 28. b1622:LCM6098400-434745-7
 29. b1625:LCM6098400-2148345-7
 30. b1864:LCM6098400-535545-8
 31. b1865:LCM6098400-1392345-8
 32. b1940:LCM6098400-383449-8
 33. b2015:LCM6098400-3554617-8
 34. b2053:LCM6098400-1812217-8
 35. b2125:LCM6098400-4007641-8
 36. b2134:LCM6098400-378841-8

(42688800-75(226))

  1. b0   :LCM42688800-30086041-4
  2. b11  :LCM42688800-19502041-4
  3. b41  :LCM42688800-19631641-4
  4. b42  :LCM42688800-3050041-4
  5. b43  :LCM42688800-29157241-4

  6. b121 :LCM42688800-28370745-4
  7. b124 :LCM42688800-11789145-4
  8. b125 :LCM42688800-37896345-4
  9. b129 :LCM42688800-4733145-4
 10. b130 :LCM42688800-17786745-4
 11. b131 :LCM42688800-30840345-4
 12. b139 :LCM42688800-1816569-4   
 13. b142 :LCM42688800-14870169-4  
 14. b144 :LCM42688800-37449369-4  
 15. b147 :LCM42688800-20867769-4
 16. b148 :LCM42688800-33921369-4
 17. b149 :LCM42688800-4286169-4
 18. b177 :LCM42688800-6172569-4
 19. b180 :LCM42688800-19226169-4
 20. b181 :LCM42688800-15698169-4
 21. b185 :LCM42688800-25223769-4
 22. b186 :LCM42688800-38277369-4
 23. b187 :LCM42688800-8642169-4

 24. b522 :LCM42688800-30086041-5
 25. b523 :LCM42688800-13504441-5
 26. b526 :LCM42688800-23030041-5
 27. b530 :LCM42688800-6448441-5
 28. b533 :LCM42688800-19502041-5
 29. b534 :LCM42688800-34442041-5
 30. b535: LCM42688800-17860441-5
 31. b538 :LCM42688800-1278841-5
 32. b540 :LCM42688800-10804441-5
 33. b543 :LCM42688800-23858041-5
 34. b554 :LCM42688800-19631641-5
 35. b555 :LCM42688800-3050041-5
 36. b556 :LCM42688800-29157241-5
 37. b557 :LCM42688800-12575641-5
 38. b561 :LCM42688800-38682841-5
 39. b565 :LCM42688800-41409945-5
 40. b566 :LCM42688800-24828345-5
 41. b569 :LCM42688800-8246745-5
 42. b570 :LCM42688800-34353945-5
 43. b571 :LCM42688800-4718745-5
 44. b590 :LCM42688800-24014745-5
 45. b593 :LCM42688800-7433145-5
 46. b595 :LCM42688800-16958745-5
 47. b597 :LCM42688800-377145-5
 48. b598 :LCM42688800-13430745-5

 49. b1602:LCM42688800-41409945-7
 50. b1603:LCM42688800-24828345-7
 51. b1606:LCM42688800-8246745-7
 52. b1626:LCM42688800-23186745-7
 53. b1627:LCM42688800-36240345-7
 54. b1630:LCM42688800-19658745-7
 55. b1633:LCM42688800-29184345-7
 56. b1636:LCM42688800-12602745-7

 57. b1836:LCM42688800-4005945-8
 58. b1839:LCM42688800-30113145-8
 59. b1842:LCM42688800-13531545-8    *
 60. b1843:LCM42688800-39638745-8
 61. b1844:LCM42688800-23057145-8
 62. b1845:LCM42688800-18830745-8
 63. b1846:LCM42688800-31884345-8
 64. b1850:LCM42688800-41409945-8
 65. b1851:LCM42688800-24828345-8
 66. b1874:LCM42688800-23186745-8
 67. b1884:LCM42688800-12602745-8
 68. b1925:LCM42688800-8094649-8
 69. b1926:LCM42688800-21148249-8
 70. b1976:LCM42688800-8109049-8
 71. b1977:LCM42688800-21162649-8
 72. b1993:LCM42688800-4411417-8
 73. b1994:LCM42688800-17465017-8
 74. b1996:LCM42688800-26990617-8
 75. b1999:LCM42688800-23462617-8

Далеко не все сообщают о том, какие паттерны в работе. Поэтому инфа всего лишь о 8 паттернах:

(Work 8)

b115 :LCM554400-74745-4
b120 :LCM554400-427545-4
b166 :LCM554400-153369-4
b171 :LCM554400-304569-4
b176 :LCM554400-405369-4

b127 :LCM3880800-2969145-4
b146 :LCM3880800-2522169-4

b109 :LCM6098400-5719545-4

[Huz]

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

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

I really don't fully understand why, but implementing (my understanding of) your "two-stage booster" approach so far seems to give very good results

It works because we are replacing repeatedly called code with once, albeit with a large amount of iterations. Not the code itself of course, but the interval of its execution. Accordingly it will be useful only on the second and deeper levels of recursion (the first is always called only once) and only if they are called a sufficient number of times (more than 200-400). And the more times they are called, the greater the gain.
And yes, I don't think it makes sense to lower the threshold below 22e3, where the fifth degrees come into play.

I believe the original code tests only those numbers that need to be tested. So if this approach is faster, I think there are two possibilities: either there is something wrong with the logic, and we are not testing everything that should be tested; or we are managing to test the same things with less overhead.

Proving that the logic is correct is not trivial, but I can display every value tested, and compare similar runs with and without the new option. That may not be practical to do for a complete LCM=554400 run, but shorter runs should be sufficient to decide how much confidence we should have.

If the logic is correct, it implies the overhead in the original code is a higher proportion of the total time than I had anticipated. There are two main areas where this can occur: in the recursion, where we already saved a lot of time with the prime iterators, but maybe there is more that could be saved; and in the linear search, where there is a lot of unavoidable preparation in each call for searches that may only end up testing a small number of values (often 0 or 1).

But if the overhead is so large, there may be more general savings to be made.

When I optimize perl code, I take advantage of a wonderful profiler (Devel::NYTProf) that lets me see very precisely how often each line of code is reached, including the call stack, and how much time has been spent on it. As far as I know the state of the art in profilers for other languages is much more primitive, but something like this would be really helpful to analyse where time is being spent.

-- 30.11.2022, 14:06 --

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

Некоторые сомнения вызывает паттерн b628, который не помечен красным.

Thanks, that was my error. I have also rearranged how the information is shown (it is all now collected below the main list).

[Dmitriy40]

Huz
It's not overhead, it's multiple checks on about the same thing.
And the speed comes from the difference in the methods of checking: in sq12.c for each $p$ all variants of $qr$ are checked, while here for each particular pattern only a linear search is performed, which is very, very often much shorter. This is because the $qr$ search in sq12.c does not depend on the current LCM, but the linear search very much depends on it.

[Huz]

Dmitriy40
I do not believe that the existing code ever checks the same thing twice. (At least, not for 12 divisors.)

It may check both $n$ and $n+1$, which the sq12 test avoids by finding the nearest multiple of 32. But the two-stage process does not do this, it would check both $n$ and $n+1$ if both were valid to check. Indeed, because it tries $p^2$ in each possible position, it may end up duplicating checks when $p_1^2$ in one position and $p_2^2$ in another position coincide - the one-stage code would never duplicate those.

I will know more when I manage to complete the testing I described.

[Huz]

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

I do not believe that the existing code ever checks the same thing twice. (At least, not for 12 divisors.)

Apparently I was wrong, I'll need to check that separately (see below) - without the new parameter, testing b1490 with -p1e7 tests 60,793,890 values of which 60,416,363 are unique. If I add -W21818 it tests 5,373,610 values of which 5,349,326 are unique.

Examining the first [1] example of a number tested in the first case but not in the second case (100000018389638352218 [2]), I find that it would have been generated by allocating $73^2$ in the fourth position, then $71^2$ in the second position. Stepping through the two cases, the difference becomes clear: in the second case the number of recursions (which is capped to the maximum prime) is far lower, so in this case it goes through an additional level of recursion (now in the first position), so it never attempts to test the value $100000018389638352218 = 2 \cdot 50000009194819176109$ in the first position since it contains no squared prime. Without -W we find the number of recursions would be higher, so we choose a linear search at this point.

Thus the huge difference in speed is caused largely by making it cheaper to recurse an extra level, coupled with existing logic that takes advantage of that.

Unfortunately that means I cannot verify the logic using this data, I'll need to think of something else.

The duplications, it turns out, are caused by something similar. The first example here is 1000069913781905952218, which is found by allocating $53^2$ in the fourth position. The second position is then $1000069913781905952219 = 3 \cdot 13^2 \cdot 163 \cdot 263^2 \cdot 563 \cdot 310752697$, and when we recurse over the second position we try allocating both $13^2$ and $263^2$ at different times. But as we can see from the numbers at the top, those duplications are less than 1% of the total work.

[1] by ASCII sort
[2] this is the value of the first number in the (possible) chain.

[Dmitriy40]

Huz
That's why I said that you do not need to edit pcoul, and make a check separately, for starters. After all, you have already agreed with the reduction of -pZ, and how exactly we reduce it (and for all patterns or for one particular pattern) does not matter.
That almost all checked chains are unique is of course fine, but you have not counted everything: iterator of prime numbers and CRT work not only for checked chains, but for all searched chains as well, which are supposedly more. And this also takes time, after all CRT is not just two or three divisions.
And in general, it is clear that with decreasing -pZ the number of checked chains decreases, much more interesting is where the speed gain comes from sq12.c, not from pcoul with different -pZ, why it can not decrease threshold as fast. And here I think it has to do with a different checking method: sq12.c tries many variants of qr, while pcoul -W tries linearly (i.e. without requiring calling CRT for each iteration), which turns out to be faster in itself. But apart from that, the linear search also depends on the current accumulated LCM (after substitution of simple non-upper levels of recursion), which does not affect sq12.c in any way, but very much affects the linear search.
So I think it's not just about the number of chains checked, even with the same number the gain will still be, although of course less.

[EUgeneUS]

Некоторые комментарии по текущему процессу.

1. Ещё вчера было выполнено $1/4$ работы, а сегодня уже $1/3$ (это в условных машино-часах).
2. Оптимистичные оценки показывают, что такими темпами всё будет завершено через 8 дней (как раз к 9 декабря ).
3. Но это сильно оптимистичные оценки. Паттерны с $LCM=554400$ считаются (на моей стороне, у других может быть несколько быстрее) за 3-4 дня. И если в один поток попадёт 2 таких паттерна (а у меня точно попадут, так как их осталось больше, чем потоков), то это уже 6-8 дней. А если паттерны с $LCM=554400$ начнутся считаться где-то через неделю, то эти потоки и будут задерживать общий результат.

Вывод: в данный момент хорошо бы считать паттерны с $LCM=554400$, а остальное - досчитывать позже, уравнивая время работы потоков.
UPD: к "остальному" относятся паттерны с $LCM \in \left\lbrace 3880800, 6098400, 42688800 \right\rbrace$
Паттерны с $LCM \geqslant 1331114400$ в этом контексте значния не имеют, они считаются слишком быстро, чтобы учитывать это время.

Я планирую к выходным \ на выходных (по завершению текущих заданий) направить 90% мощностей (10-11 потоков из 12) на расчет паттернов $LCM=554400$.

[Huz]

EUgeneUS в сообщении #1572107 писал(а):

Вывод: в данный момент хорошо бы считать паттерны с $LCM=554400$, а остальное - досчитывать позже, уравнивая время работы потоков.

I suggest to wait just a little longer before doing that.

I'm about to release a new version with -W. This will make the patterns with LCM=554400 much faster - but you cannot add -W to a process that has already started, you would need to start it from the beginning again.

So better not to start the longest processes immediately, please wait for the new version.

-- 01.12.2022, 14:02 --

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

Huz
That's why I said that you do not need to edit pcoul, and make a check separately, for starters. After all, you have already agreed with the reduction of -pZ, and how exactly we reduce it (and for all patterns or for one particular pattern) does not matter.

It would have been much harder to do a separate check, within pcoul I have all the information already available. Almost all the effort went into updating the progress reporting and recovery process, the core loop is very simple:

(Оффтоп)

    while (1) {
        p = prime_iterator_prev(&cur->piter);
        if (p <= midp)  /* this is the -W threshold */
            break;
        for (nai = 0; nai < nac; ++nai) {
            uint vi = need_alloc[nai];  /* this is a list of locations we can allocate */
            if (apply_single(prev, cur, vi, p, 3))
                walk_v(cur, Z(zero));
            --value[vi].vlevel;  /* unallocate */
        }
    }

Цитата:

That almost all checked chains are unique is of course fine, but you have not counted everything: iterator of prime numbers and CRT work not only for checked chains, but for all searched chains as well, which are supposedly more. And this also takes time, after all CRT is not just two or three divisions.

Yes, this is the overhead I was speaking of. There is a third element, calculating the inverses of allocated prime powers as part of the linear search. I think there are opportunities for further optimization in all three of these areas.

[EUgeneUS]

Huz
Well.
And what are the forecasts for the release of the new version?
If it’s a week or more, then I’ll have time to count a pack of such patterns.

-- 01.12.2022, 17:13 --

FYI. I tried to analyze this code, and did not find any logical errors in it. However, this does not mean that it cannot be.

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

Unfortunately that means I cannot verify the logic using this data, I'll need to think of something else.

I can suggest this way:
1. Let's by using -W we reduce the prime threshold from 1e7 to 1e6
2. Let's choose some prime number in this range.
3. Output sets of candidates that were processed with the -W option and the "usual way" that contain the selected prime number
4. and compare them