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

[Huz]

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

Huz
Answer a simple question for a pattern like b1952: how many times will the second level of recursion be run and therefore how many times will it check for prime numbers greater than 1e7 (and up to 1e8)?

For my current run of b1619 with -p5e7 and -g11, the answer turned out to be in the range 4482-4643 (between $\pi(42929)-\pi(11)$ and $\pi(44711)-\pi(11)$). Of course most of those averaged less than 1 linear check each.

Цитата:

Now pay attention: you can check all such prime numbers once by direct substitution in place of the second level of recursion (or for safety - in all possible places of the pattern) and without touching anything else run linear check (after CRT) to see if there are any solutions.

It would need to be at least in the places of the first and the third levels, not sure how many more.

Цитата:

Since we did not substitute a prime number from the first level of recursion, we will of course need to iterate more, but only about 170 times ($13^2$). This is easy to estimate: the number of iterations of the linear search would be $10^{22}/554400/(10^7)^2=180$, a total of 180 for each prime number on the second level of recursion.

So if, for safety, at all positions - that's 6 possible positions for b1619 - it becomes 1080.

Цитата:

And as the substituted prime increases (up to 1e8), the number of iterations will drop even further, down to 2.

The global threshold check is currently below 6e7.

Цитата:

At a 2e5/s linear check speed, checking this entire 1e7-1e8 range for one particular pattern and one place in it will take about half an hour.

I don't know how accurate that calculation is. But I believe we have 66 patterns with LCM=554400, and we can get most of that benefit (and also benefit other patterns) from running sq12 for another 33 hours, for the same runtime cost and with no new code.

So the marginal benefit does not seem to me to justify the additional complexity and all its attendant costs.

[Dmitriy40]

Well, no, then no. You'd think I'd want it more than anyone else.

[Huz]

b1619 completed faster than anticipated: 30.5h with -p5e7 -g11 (mostly).

(Оффтоп)

# start with -p1e8 and -g12
001 pcoul(12 11) -p100000000 -f11 -g12 -x9887353188984012120346 -b1619

# switch to -p5e7 after 5h40
305 2 11.151^2 2^2.3 7.47^2 2.5^2 3 2^5 23^2 2.3^2 5 2^2.7: 307282 / 334673 (20399.57s)
001 recover pcoul(12 11) -p50000000 -f11 -g12 -x9887353188984012120346 -b1619

# switch to -g11 after 26h10
305 2 11.34032347^2 2^2.3 7 2.5^2 3 2^5 38039^2 2.3^2 5 2^2.7 (94199.16s)
001 recover pcoul(12 11) -p50000000 -f11 -g11 -x9887353188984012120346 -b1619

# transition to linear search at approx 26h45, recursion is gaining 1540 per 10 minutes
305 2 11.42940409^2 2^2.3 7 2.5^2 3 2^5 41389^2 2.3^2 5 2^2.7 (95399.16s)
305 2 11.48874589^2 2^2.3 7 2.5^2 3 2^5 42929^2 2.3^2 5 2^2.7 (95999.16s)
305 2 11 2^2.3 7 2.5^2 3 2^5 44711^2 2.3^2 5 2^2.7: 571954 / 4460648 (96599.16s)
305 2 11 2^2.3 7 2.5^2 3 2^5 46771^2 2.3^2 5 2^2.7: 1740522 / 4076368 (97199.15s)

# finish at 30h30
305 2 11 2^2.3 7 2.5^2 3 2^5 1339691^2 2.3^2 5 2^2.7: 3587 / 4967 (109198.92s)
367 coul(12, 11): recurse 1900621787, walk 1901769407, walkc 17507076909 (109798.22s)

But I'm running a bit ahead of myself, the threshold calculation will take about 6h more to reach 5e7.

[Dmitriy40]

Huz
As far as I can see, among the 1044 patterns (without "sq") there is not a single one that lacks single 2 and 3 and 5, always at least one of them necessarily exists. So if a solution exists, it will necessarily include a number of the form $2rp^2$ and/or $3rp^2$ and/or $5rp^2$. So there is no point in sq12.c checking $q>5$ ($q<r$ as you have it), because even with $q\le5$ all solutions will still be found. It is sufficient to set $qmax=5$ instead of $qmax=\sqrt{qrmax}$. And the speed of the sq12.c should still increase.
The variants with the $p^5$ I certainly did not take into account, there $p$ is too small and in any case remains to be checked.

-- 27.11.2022, 05:24 --

There are no such patterns without "sq" and without $q=2$ and without $q=3$ and without $q=5$ among $D(12,12),D(12,13),D(12,14),D(12,15)$, so this method is universal for 12 divisors.

-- 27.11.2022, 05:27 --

Видимо да, именно мне и больше всех надо ... Душа программиста не выдерживает что программу счёта на несколько недель (суммарно) можно ещё ускорить в пару-тройку раз ...

[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,160); \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{1}}; \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{18}}; \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{17}}; \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{42}}; \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{35}}; \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}}; }$

Всего полностью обсчитаны хотя бы однократно $ 1 + 18 + 17 + 42 + 35 + 58 + 152 + 96 + 58 = 477 $ паттернов из $1044$ основных. Количество таких паттернов возросло на 23 по сравнению с предыдущей таблицей.

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

(554400-1(66))

1. b1952:LCM554400-81049-8

(3880800-18(142))

  1. b133 :LCM3880800-3674745-4
  2. b141 :LCM3880800-1816569-4
  3. b521 :LCM3880800-1509241-5
  4. b532 :LCM3880800-2567641-5
  5. b542 :LCM3880800-3042841-5
  6. b553 :LCM3880800-2697241-5
  7. b563 :LCM3880800-3755641-5
  8. b592 :LCM3880800-729945-5
  9. b1600:LCM3880800-837945-7
 10. b1601:LCM3880800-3660345-7
 11. b1605:LCM3880800-1543545-7
 12. b1629:LCM3880800-1313145-7
 13. b1632:LCM3880800-254745-7
 14. b1635:LCM3880800-2018745-7
 15. b1928:LCM3880800-1744249-8
 16. b2102:LCM3880800-681241-8
 17. b1637:LCM3880800-2371545-7
 18. b2002:LCM3880800-1589017-8

(6098400-17(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. b511 :LCM6098400-3950041-5
  8. b512 :LCM6098400-5663641-5
  9. b520 :LCM6098400-5562841-5
 10. b581 :LCM6098400-3105945-5
 11. b1616:LCM6098400-535545-7
 12. b1617:LCM6098400-1392345-7
 13. b1620:LCM6098400-3105945-7
 14. b1621:LCM6098400-4819545-7
 15. b1940:LCM6098400-383449-8
 16. b2134:LCM6098400-378841-8
 17. b2015:LCM6098400-3554617-8

(42688800-42(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. b530 :LCM42688800-6448441-5
 16. b533 :LCM42688800-19502041-5
 17. b534 :LCM42688800-34442041-5
 18. b540 :LCM42688800-10804441-5
 19. b543 :LCM42688800-23858041-5
 20. b554 :LCM42688800-19631641-5
 21. b555 :LCM42688800-3050041-5
 22. b556 :LCM42688800-29157241-5
 23. b561 :LCM42688800-38682841-5
 24. b570 :LCM42688800-34353945-5
 25. b571 :LCM42688800-4718745-5
 26. b590 :LCM42688800-24014745-5

 27. b1602:LCM42688800-41409945-7
 28. b1603:LCM42688800-24828345-7
 29. b1606:LCM42688800-8246745-7
 30. b1626:LCM42688800-23186745-7
 31. b1627:LCM42688800-36240345-7
 32. b1630:LCM42688800-19658745-7
 33. b1633:LCM42688800-29184345-7
 34. b1636:LCM42688800-12602745-7

 35. b1836:LCM42688800-4005945-8
 36. b1842:LCM42688800-13531545-8    *
 37. b1843:LCM42688800-39638745-8
 38. b1844:LCM42688800-23057145-8
 39. b1874:LCM42688800-23186745-8
 40. b1884:LCM42688800-12602745-8
 41. b1926:LCM42688800-21148249-8
 42. b1999:LCM42688800-23462617-8

(1331114400-35(66))

 1. b100 :LCM1331114400-582849945-4
 2. b103 :LCM1331114400-945881145-4
 3. b108 :LCM1331114400-340829145-4
 4. b154 :LCM1331114400-529605369-4
 5. b158 :LCM1331114400-650615769-4
 6. b163 :LCM1331114400-287584569-4
 7. b192 :LCM1331114400-863829369-4
 8. b196 :LCM1331114400-500798169-4
 9. b201 :LCM1331114400-621808569-4
10. b547 :LCM1331114400-448629241-5
11. b551 :LCM1331114400-569639641-5
12. b576 :LCM1331114400-882485145-5
13. b1033:LCM1331114400-748264441-6
14. b1099:LCM1331114400-761474745-6
15. b1535:LCM1331114400-748264441-7
16. b1610:LCM1331114400-761474745-7
17. b1614:LCM1331114400-882485145-7
18. b1858:LCM1331114400-761474745-8
19. b1862:LCM1331114400-882485145-8
20. b1931:LCM1331114400-1082017849-8
21. b1933:LCM1331114400-476965849-8
22. b1939:LCM1331114400-839997049-8
23. b1981:LCM1331114400-753575449-8    *
24. b1985:LCM1331114400-390544249-8
25. b2005:LCM1331114400-709305817-8    *
26. b2010:LCM1331114400-830316217-8
27. b2014:LCM1331114400-467285017-8
28. b2043:LCM1331114400-1043529817-8
29. b2048:LCM1331114400-680498617-8
30. b2052:LCM1331114400-801509017-8
31. b2115:LCM1331114400-990285241-8
32. b2118:LCM1331114400-385233241-8
33. b2123:LCM1331114400-748264441-8    *
34. b2159:LCM1331114400-327618841-8
35. b2165:LCM1331114400-448629241-8

[EUgeneUS]

Huz
Here Dmitry gave a primer code on PARI / GP to lower the threshold individually for the pattern.Dmitry gave a primer code on PARI / GP to lower the threshold individually for the pattern.

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

b1619 completed faster than anticipated: 30.5h with -p5e7 -g11 (mostly).

I checked b1952 with -p4e6. It ended at 33 hours (120 thousand seconds)
I can run the b1952 calculation with the threshold you expect to reach. This will test the calculation speed on my side.
If the calculation time is few days (less than a week, f.e.), then the problem with $LCM=554400$ patterns will be removed.

However, when moving to $D(12,12)$ and beyond, most likely you will have to use all the methods to speed up the calculations. Including this one.

[Dmitriy40]

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

There are no such patterns without "sq" and without $q=2$ and without $q=3$ and without $q=5$ among $D(12,12),D(12,13),D(12,14),D(12,15)$, so this method is universal for 12 divisors.

А вот для $D(12,10)$ встретились два таких взаимно симметричных паттерна, в них вообще ни одного отдельного простого нет. Впрочем полезности идеи это не умаляет: все десятки уже и так проверены; два паттерна проверить проще чем все; можно индивидуально для них опустить порог простых насколько получится.

-- 27.11.2022, 13:26 --

b1619 можно посчитать за часов 10-12, часа за полтора опустив порог простых до 2e6-3e6 конкретно для него. Вместо 30ч. Но конечно если три месяца счёта (на 1 поток) устраивают и двух-трёх-кратное ускорение не интересует ...

[Huz]

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

Huz
As far as I can see, among the 1044 patterns (without "sq") there is not a single one that lacks single 2 and 3 and 5, always at least one of them necessarily exists. So if a solution exists, it will necessarily include a number of the form $2rp^2$ and/or $3rp^2$ and/or $5rp^2$. So there is no point in sq12.c checking $q>5$ ($q<r$ as you have it), because even with $q\le5$ all solutions will still be found. It is sufficient to set $qmax=5$ instead of $qmax=\sqrt{qrmax}$. And the speed of the sq12.c should still increase.

I don't think I see the logic here. 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". But in this case we should be skipping it only if $s > Z$.

So I think for this to be valid, the sq12 check has to be the only check - such that we would run it all the way down to $13^2$ - or we would need to change the order that pcoul chooses positions to allocate to (which is something we discussed before).

-- 27.11.2022, 15:22 --

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

Huz
Here Dmitry gave a primer code on PARI / GP to lower the threshold individually for the pattern.

Thanks, I don't understand all the PARI code, but I think the logic required is straightforward.

Цитата:

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

b1619 completed faster than anticipated: 30.5h with -p5e7 -g11 (mostly).

I checked b1952 with -p4e6. It ended at 33 hours (120 thousand seconds)
I can run the b1952 calculation with the threshold you expect to reach. This will test the calculation speed on my side.
If the calculation time is few days (less than a week, f.e.), then the problem with $LCM=554400$ patterns will be removed.

Please send me the log file for that run - 33h is rather slower than I would have expected. b1952 must somehow be a harder pattern than b1619, but even given that it seems like the improvement from replacing -p5e7 with -p4e6 is less than I would have expected.

Threshold calculation has currently reached 4.3e7. I think it is likely it will be able to reach 1e7, but I'm not sure: I need more work on extrapolating the rate of calculation, which has not proven to be as simple as I expected.

Цитата:

However, when moving to $D(12,12)$ and beyond, most likely you will have to use all the methods to speed up the calculations. Including this one.

Agreed.

If I could work out a way to do it, I think there would also be benefits to having pcoul spend some time at the start working out the optimal gain for itself.

[Dmitriy40]

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

Thanks, I don't understand all the PARI code,

PARi code is so similar to C code that it is translated practically "in mind". With a couple of exceptions, which do not affect the logic of the work and are easily replaced by C code. In addition, I was ready to translate the algorithm (but not the fully working code) into C.

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

I think it is likely it will be able to reach 1e7, but I'm not sure: I need more work on extrapolating the rate of calculation, which has not proven to be as simple as I expected.

The usual quadratic dependence: each halving of the threshold takes twice as long as the previous one.

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

If I could work out a way to do it, I think there would also be benefits to having pcoul spend some time at the start working out the optimal gain for itself.

All this mess with -g is not really needed at all: at start it is possible to measure real speed of search at approximate expected (plus or minus several times) point of mode change and then measure time of recursive search, as soon as it becomes more than estimated time required for linear search - to stop recursion and to finish by counting linearly. That's all there is to it. And don't suffer defining the perfect -g.

[EUgeneUS]

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

Please send me the log file for that run - 33h is rather slower than I would have expected. b1952 must somehow be a harder pattern than b1619, but even given that it seems like the improvement from replacing -p5e7 with -p4e6 is less than I would have expected.

Sent by email.
Keep in mind that my computer may be two or more times slower than yours.
I will run the b1952 calculation with the 5e7 threshold since it has already been reached. And in two days we'll see how quickly it will be calculated.

[Huz]

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

PARi code is so similar to C code that it is translated practically "in mind". With a couple of exceptions, which do not affect the logic of the work and are easily replaced by C code.

Agreed, but it is the exceptions that are the issue. I don't know any of the vector commands from when I used to use PARI some 15 years ago, and I see an occasional comment from you (such as about "p++") that suggest that there are "false friends" - constructs that look identical but are not.
But as I said, it is obvious enough what the logic should be, and much of the detail already exists in useful forms within pcoul.

Цитата:

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

I think it is likely it will be able to reach 1e7, but I'm not sure: I need more work on extrapolating the rate of calculation, which has not proven to be as simple as I expected.

The usual quadratic dependence: each halving of the threshold takes twice as long as the previous one.

That is what I had assumed, but it turns out not to be as simple as that. I think changing density of primes for each of $p, q, r$ probably also affect the rate.

I tried putting data from my logs into an online curve-fitting program, and it proposed the following (which looks nonsensical to me):

y = -449219.45 + x / (-142.48 - .000002635 x + 0.0511 sqrt(x))

.. where $x$ is the starting prime, and $y$ is how far that should be reduced in 10 minutes of work.
If I believe that, it should take 5 days to reach 1e7.

Цитата:

All this mess with -g is not really needed at all: at start it is possible to measure real speed of search at approximate expected (plus or minus several times) point of mode change and then measure time of recursive search, as soon as it becomes more than estimated time required for linear search - to stop recursion and to finish by counting linearly. That's all there is to it. And don't suffer defining the perfect -g.

Deciding what is the "approximate expected point of mode change" is itself not trivial; if we get it wrong then the step "measure real speed of search" may take days instead of seconds. We also do not want to test this repeatedly at every level of recursion, but a decision when to change mode must be made at every level - imperfect as it is, that is the role that g plays.

[Dmitriy40]

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

Deciding what is the "approximate expected point of mode change" is itself not trivial; if we get it wrong then the step "measure real speed of search" may take days instead of seconds.

Trivial enough, that's why you need to measure the actual speed before assessments. And it is easy to measure it: 1e4 iterations in any case will not take days (and if there is a computer which will take days, there is no reason to run computational problems on it!), so start 1e4 iterations and check time, if less than 0.2s, then start 1e5 iterations, if again less - 1e6 iterations, then 1e7, then 1e8 ... This way we are guaranteed not to exceed a few seconds, which is acceptable. And once we know the real speed of the enumeration, it is quite easy to estimate the moment of mode change to a couple of tens of percent. And no errors to the days of counting. But it's not half an hour to write the code.
The search speed does not depend too much (or not at all) on the recursion level, so there is no need to re-measure it. Re-estimate, of course, because the effective LCM changes, but it is no more complicated than the top estimate, they are all the same, regardless of the level of recursion.
And in my opinion it's all simple enough for conceptual understanding. The code is not so easy to write, but at the level of idea and algorithm - simple.

[Huz]

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

I tried putting data from my logs into an online curve-fitting program [...] If I believe that, it should take 5 days to reach 1e7.

If I pretend that it is simply quadratic, the estimate is 11 days to reach 1e7. So I'm confident enough that I will reach that, at one time or another, and so I think it is fine to run with "-p1e7".

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

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

Please send me the log file for that run - 33h is rather slower than I would have expected. b1952 must somehow be a harder pattern than b1619, but even given that it seems like the improvement from replacing -p5e7 with -p4e6 is less than I would have expected.

Sent by email.
Keep in mind that my computer may be two or more times slower than yours.

Thanks, I think you lost some time using -g16 (maybe 3 hours compared to -g11 or -g12), but the main difference is the checked primes: for b1619 there are 5 values that can be checked with isprime(), but for b1952 there are only 3. I don't see any other problem here.

-- 28.11.2022, 02:11 --

Thanks to DemIS, there is now a 64-bit Windows build for the latest code.

Main changes are a) recovery on restart works more reliably; b) a new option "-X" is available.

See v20221123 for full details, and for the Windows build (pcoul_24112022.zip).

[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,160); \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{3}}; \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{20}}; \node at (133,195){\text{4 ?}}; \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{30}}; \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{55}}; \node at (133,175){\text{1 ?}}; \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{35}}; \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}}; }$

Всего полностью обсчитаны хотя бы однократно $ 3 + 20 + 30 + 55 + 35 + 58 + 152 + 96 + 58 = 507 $ паттернов из $1044$ основных. Количество таких паттернов возросло на 30 по сравнению с предыдущей таблицей. Приближаемся к своеобразному экватору.

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

(554400-3(66))

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

(3880800-20(142))

  1. b133 :LCM3880800-3674745-4
  2. b141 :LCM3880800-1816569-4
  3. b143 :LCM3880800-3580569-4
  4. b521 :LCM3880800-1509241-5
  5. b532 :LCM3880800-2567641-5
  6. b542 :LCM3880800-3042841-5
  7. b553 :LCM3880800-2697241-5
  8. b563 :LCM3880800-3755641-5
  9. b564 :LCM3880800-3660345-5
 10. b592 :LCM3880800-729945-5
 11. b1600:LCM3880800-837945-7
 12. b1601:LCM3880800-3660345-7
 13. b1605:LCM3880800-1543545-7
 14. b1629:LCM3880800-1313145-7
 15. b1632:LCM3880800-254745-7
 16. b1635:LCM3880800-2018745-7
 17. b1928:LCM3880800-1744249-8
 18. b2102:LCM3880800-681241-8
 19. b1637:LCM3880800-2371545-7
 20. b2002:LCM3880800-1589017-8

(6098400-30(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. b520 :LCM6098400-5562841-5
 16. b581 :LCM6098400-3105945-5
 17. b582 :LCM6098400-4819545-5
 18. b583 :LCM6098400-434745-5
 19. b586 :LCM6098400-2148345-5
 20. b587 :LCM6098400-3861945-5
 21. b588 :LCM6098400-4718745-5
 22. b1616:LCM6098400-535545-7
 23. b1617:LCM6098400-1392345-7
 24. b1620:LCM6098400-3105945-7
 25. b1621:LCM6098400-4819545-7
 26. b1622:LCM6098400-434745-7
 27. b1625:LCM6098400-2148345-7
 28. b1940:LCM6098400-383449-8
 29. b2134:LCM6098400-378841-8
 30. b2015:LCM6098400-3554617-8

(42688800-55(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. b177 :LCM42688800-6172569-4

 16. b522 :LCM42688800-30086041-5
 17. b523 :LCM42688800-13504441-5
 18. b526 :LCM42688800-23030041-5
 19. b530 :LCM42688800-6448441-5
 20. b533 :LCM42688800-19502041-5
 21. b534 :LCM42688800-34442041-5
 22. b535: LCM42688800-17860441-5
 23. b540 :LCM42688800-10804441-5
 24. b543 :LCM42688800-23858041-5
 25. b554 :LCM42688800-19631641-5
 26. b555 :LCM42688800-3050041-5
 27. b556 :LCM42688800-29157241-5
 28. b557 :LCM42688800-12575641-5
 29. b561 :LCM42688800-38682841-5
 30. b565 :LCM42688800-41409945-5
 31. b566 :LCM42688800-24828345-5
 32. b569 :LCM42688800-8246745-5
 33. b570 :LCM42688800-34353945-5
 34. b571 :LCM42688800-4718745-5
 35. b590 :LCM42688800-24014745-5
 36. b593 :LCM42688800-7433145-5
 37. b597 :LCM42688800-377145-5
 38. b598 :LCM42688800-13430745-5

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

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

(1331114400-35(66))

 1. b100 :LCM1331114400-582849945-4
 2. b103 :LCM1331114400-945881145-4
 3. b108 :LCM1331114400-340829145-4
 4. b154 :LCM1331114400-529605369-4
 5. b158 :LCM1331114400-650615769-4
 6. b163 :LCM1331114400-287584569-4
 7. b192 :LCM1331114400-863829369-4
 8. b196 :LCM1331114400-500798169-4
 9. b201 :LCM1331114400-621808569-4
10. b547 :LCM1331114400-448629241-5
11. b551 :LCM1331114400-569639641-5
12. b576 :LCM1331114400-882485145-5
13. b1033:LCM1331114400-748264441-6
14. b1099:LCM1331114400-761474745-6
15. b1535:LCM1331114400-748264441-7
16. b1610:LCM1331114400-761474745-7
17. b1614:LCM1331114400-882485145-7
18. b1858:LCM1331114400-761474745-8
19. b1862:LCM1331114400-882485145-8
20. b1931:LCM1331114400-1082017849-8
21. b1933:LCM1331114400-476965849-8
22. b1939:LCM1331114400-839997049-8
23. b1981:LCM1331114400-753575449-8    *
24. b1985:LCM1331114400-390544249-8
25. b2005:LCM1331114400-709305817-8    *
26. b2010:LCM1331114400-830316217-8
27. b2014:LCM1331114400-467285017-8
28. b2043:LCM1331114400-1043529817-8
29. b2048:LCM1331114400-680498617-8
30. b2052:LCM1331114400-801509017-8
31. b2115:LCM1331114400-990285241-8
32. b2118:LCM1331114400-385233241-8
33. b2123:LCM1331114400-748264441-8    *
34. b2159:LCM1331114400-327618841-8
35. b2165:LCM1331114400-448629241-8

[EUgeneUS]

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

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

Если оценивать машино-часы, а не штуки, то до экватора, как до Китая пешком.
По моим оценкам только-только перевалили 10%.