Модифицировать программу (практическая помощь)

[Jarek]

I confirm your findings about 18-patterns.

Nataly-Mak в сообщении #1047969 писал(а):

Ну, начать поиск можно с диаметра 100, а лучше сразу с минимального - 82.

I have started a search for an 82. Data gathered so far indicate that I should eventually find it, but it may take long time.

[Nataly-Mak]

Да, весьма любопытно, насколько большие простые числа будут в 18-ке с минимальным диаметром.
Участники проекта нашли достаточно много 18-ок (несколько сотен), но все они с довольно большими диаметрами.
Несколько найденных мной последних 18-ок:

100029140302806229: 0 30 34 54 58 84 100 114 118 120 124 138 154 180 184 204 208 238
100030951688501657: 0 20 42 90 140 146 222 230 266 270 306 314 390 396 446 494 516 536
100038606908220619: 0 64 150 172 238 262 288 304 322 360 378 394 420 444 510 532 618 682
100043697145736159: 0 8 54 84 92 110 140 162 180 212 230 252 282 300 308 338 384 392
100044769662564703: 0 28 54 58 60 78 120 160 204 334 378 418 460 478 480 484 510 538
100047343201996357: 0 6 94 100 114 136 142 172 192 244 264 294 300 322 336 342 430 436
100047784461608317: 0 12 46 52 76 96 112 126 166 180 220 234 250 270 294 300 334 346
100049818247289899: 0 24 32 48 50 62 74 132 140 192 200 258 270 282 284 300 308 332
100050613444022513: 0 20 44 56 60 74 104 140 174 320 354 390 420 434 438 450 474 494
100051651043082031: 0 10 16 46 76 88 126 138 216 262 340 352 390 402 432 462 468 478
100060998185443501: 0 22 70 100 232 238 250 252 282 328 358 360 372 378 510 540 588 610
100073020969673069: 0 24 54 80 90 104 132 138 170 192 224 230 258 272 282 308 338 362
100073742072779323: 0 4 34 46 70 114 120 148 150 154 156 184 190 234 258 270 300 304
100078625776230991: 0 10 18 22 36 52 70 82 88 120 126 138 156 172 186 190 198 208
100081347676805773: 0 46 66 78 94 148 154 186 208 276 298 330 336 390 406 418 438 484

Почему-то они все расползаются
Самый маленький здесь диаметр 208.

[Jarek]

Those are about $10^{17}$. I think that the smallest 82 has 24-25 digits.

[Nataly-Mak]

Наблюдается тенденция: более компактные симметричные кортежи состоят из бОльших простых чисел.

[Begemot82]

Jarek

Jarek в сообщении #1047975 писал(а):

Those are about $10^{17}$. I think that the smallest 82 has 24-25 digits.

Получается огромный скачок по сравнению с другими КПППЧ ( для n=16 18 цифр )

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

Решения для Task 2, все минимальные и по величине чисел, и по диаметру:

n=10, 51435506383: 0 4 6 10 16 18 24 28 30 34
n=12, 41280160361347: 0 4 6 10 12 22 24 34 36 40 42 46
n=14, 10421030292115097: 0 2 6 12 14 20 26 30 36 42 44 50 54 56
n=16, 996689250471604163: 0 6 8 14 18 24 26 36 38 48 50 56 60 66 68 74

Какие соображения в пользу оценки 24-25 digits ?

[Nataly-Mak]

Begemot82 в сообщении #1047986 писал(а):

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

n=16, 996689250471604163: 0 6 8 14 18 24 26 36 38 48 50 56 60 66 68 74

Кстати, паттерн для КПППЧ 16 с диаметром 74 получается из паттерна для КПППЧ 18 с диаметром 82.
Казалось бы: КПППЧ длины 18 с диаметром 82 должна быть где-то не так далеко от КПППЧ длины 16 с диаметром 74.
Всего-то добавить два числа - одно слева, второе справа
Если будут найдены КПППЧ длины 18 с минимальным диаметром 82, из них автоматом получатся новые КПППЧ длины 16 с диаметром 74. Конечно, они могут состоять и из 24-значных простых чисел. Ничто им этого не запрещает

[Jarek]

Begemot82 в сообщении #1047986 писал(а):

Какие соображения в пользу оценки 24-25 digits ?

The first segment of my search has the range about $8\cdot10^{23}$. I have covered over half of it (not the smallest half, just half of the numbers distributed more or less uniformly over that range). I have no 18 so far. From the data gathered (number of some 12's, 14's and 16's) I conclude that I should have expected one 18 by now, but I am being unlucky. By the time I finish that range I may or may not get an 18. Since the search is exhaustive, if I get no 18 in a certain range it would mean there is none. Therefore there may or may not be an 18 below $10^{24}$ - hard to tell which is more likely.

The smallest solution is always subject to a random fluctuations. The size of third or tenth smallest solution should be more stable. Also some tuplets of the same length are more likely to appear than the other. This may also influence size of the smallest tuplet.

[Begemot82]

Jarek
Понятно, что минимальное решение можно ожидать в больших пределах. Но почему поиск начат с $8\cdot10^{23}$? Возможно оно состоит из 21-22 цифр или даже из 20 цифр?

[Nataly-Mak]

Оказывается, крепким орешком будут КПППЧ чётных длин с минимальным диаметром.
Думаю, что одна из причин: у КПППЧ чётных длин слишком маленькие минимальные диаметры.
Например, у 16-ки минимальный диаметр 74, у 18-ки минимальный диаметр 82.
Тогда как у 17-ки минимальный диаметр 240, у 19-ки минимальный диаметр 252:

0  6  12  30  42  72  90  96  120  126  132  156  162  180  210  222  240  246  252

[Dmitriy40]

Самая компактная 18-ка из найденных:

12553323285596767: 0 6 10 22 34 36 42 60 64 72 76 94 100 102 114 126 130 136

[Jarek]

Begemot82 в сообщении #1048000 писал(а):

Jarek
Понятно, что минимальное решение можно ожидать в больших пределах. Но почему поиск начат с $8\cdot10^{23}$? Возможно оно состоит из 21-22 цифр или даже из 20 цифр?

The larger the search range of a single search segment, the faster my program is. Therefore I select the search range according to a reasonable runtime of the program. With 19 cores I have available at the moment, the above range (form 0 to $8\cdot10^{23}$) is going to take about 3 days, which is fine for a single search segment. Given that finding an 18-tuplet is not an easy task, I didn't bother searching smaller ranges first.

[Begemot82]

Не даром меня насторожило

Jarek в сообщении #1047975 писал(а):

I think that the smallest 82 has 24-25 digits.

Возможно даже наименьшая компактная (d=82) КПППЧ 18 состоит из простых из 18 цифр. Но по моим оценкам наиболее вероятно 21-22 цифры.
Спасибо за пояснения.

[Nataly-Mak]

Jarek в сообщении #1048025 писал(а):

The larger the search range of a single search segment, the faster my program is.

Весьма интересная закономерность! Прямо противоположная тому, что мы наблюдаем с генератором primesieve. Я попробовала проверять конец интервала, скорость снизилась более чем в 5 раз.
Сейчас проверяю интервал с $10^{17}$; скорость тоже снизилась по сравнению с предыдущим (меньшим) интервалом - с 1315 до 1015 млрд/час.
Получается, что чем больше простые числа, тем нерасторопнее делается генератор primesieve. Или генератор тут ни при чём? Тогда какая же причина падения скорости?

[Dmitriy40]

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

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

[Nataly-Mak]

Между тем преодолела интервал длиной в 100 триллионов



17-ка по-прежнему не найдена. Ни одного квадрата тоже не получено. Все 18-ки с большими диаметрами. 20-ки очень редко попадаются, всего 3 штуки:

100000039879452287: 0 12 14 26 150 152 186 194 200 210 266 276 282 290 324 326 450 462 464 476
100044769662564691: 0 12 40 66 70 72 90 132 172 216 346 390 430 472 490 492 496 522 550 562
100047784461608309: 0 8 20 54 60 84 104 120 134 174 188 228 242 258 278 302 308 342 354 362

В общем, ничего интересного пока нет.