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

[Jarek]

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

То есть паттерны с разностью больше 300 малоперспективны?

А можно сделать программу поиска кортежей сразу по нескольким заданным паттернам? Например, ввести в программу 10 разных паттернов и пусть она их все проверяет.

No, 10 patterns means 10 separate programs.

[Nataly-Mak]

Jarek
однако есть кортежи в очень широких диапазонах, например:

7318133876391223: 0 6 30 114 138 264 268 298 546 576 580 706 730 814 838 844
584594952562499: 0 32 68 158 170 228 260 350 510 600 632 690 702 792 828 860
3367680536652371: 0 36 168 186 200 212 302 408 440 546 636 648 662 680 812 848
9585616597901077: 0 76 90 130 142 186 364 412 474 522 700 744 756 796 810 886
12572752443521383: 0 54 114 124 364 390 400 406 444 450 460 486 726 736 796 850
19239181762421659: 0 168 252 264 310 384 390 414 448 472 478 552 598 610 694 862
13319464281880157: 0 42 140 272 294 360 372 440 486 554 566 632 654 786 884 926

-- Вс июл 19, 2015 14:50:24 --

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

No, 10 patterns means 10 separate programs.

Но почему?
Разве программа на может проверять одновременно несколько паттернов?
Например, введены два паттерна. Это означает две последовательные ветви программы:
1. проверка первого паттерна;
2. проверка второго паттерна

Конечно, можно сделать и две отдельные программы.

[Jarek]

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

Jarek

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

No, 10 patterns means 10 separate programs.

Но почему?
Разве программа на может проверять одновременно несколько паттернов?
Например, введены два паттерна. Это означает две последовательные ветви программы:
1. проверка первого паттерна;
2. проверка второго паттерна

Конечно, можно сделать и две отдельные программы.

Of course, you can always put 10 separate programs in one code and create one executable, but I find it more convenient to have a separate program for each pattern.

[Nataly-Mak]

Если мы имеем 10 отдельных программ, тогда нам нужен такой компьютер, на котором можно запускать одновременно 10 программ, а это не у всех имеется.
А если сделать проверку 10 паттернов в одной программе, тогда мы запускаем всего одну программу, что всем возможно сделать.

[Nataly-Mak]

Попробовала составить паттерн с разностью 252:

{0 12 30 42 60 72 90 102 126 150 162 180 192 210 222 240 252}

На странице проверки паттерн забраковали.
Конечно, я с потолка составила, алгоритма-то не знаю
Там и подкорректировали паттерн:

{0 12 30 42 60 72 90 102 126 150 164 182 192 210 222 240 254}

Но теперь нарушена симметричность

[Begemot82]

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

Begemot82
если можно, расскажите, пожалуйста, как вы составляли паттерны, по какому алгоритму. Ваши паттерны оказались хорошими

Второй вопрос на засыпку
вы можете написать программу поиска реальных наборов по заданным паттернам

Брал пятнашки
5348080416833681: 0 18 30 48 60 66 90 108 126 150 156 168 186 198 216
5531524424792777: 0 12 36 66 102 162 180 186 192 210 270 306 336 360 372
добавлял с краев числа кратные 6, проверял на остатки.
Из первой получилось с добавлением 12 и 24, из второй 18.
Очень удачно получилась минимальная с диаметром 240.
На втором вопросе засыпался.

[Nataly-Mak]

Begemot82
спасибо за алгоритм.
А я вот пытаюсь подбором сделать из паттернов с диаметром 240 паттерн с диаметром 252.
И нифига не получается

Почему на втором вопросе засыпались? Потому что он на засыпку?
Надо взять исходник whitefox и модифицировать в нём проверку, генерация простых остаётся.

-- Вс июл 19, 2015 17:16:58 --

Например, такой сочинила:

{0 18 36 48 66 78 84 108 126 144 168 174 186 204 216 234 252}

Проверка бракует последний элемент и заменяет его на 254

[Begemot82]

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

Проверка бракует последний элемент и заменяет его на 254

Конечно, потому что полный букет для остатков на 5. Двойка в последнем остатке единственная, заменяем на присутствующую уже четверку и оп-ля. Про симметричность проверка не знает.
+
Выложил в облако результаты поиска КПППЧ длиной 16
https://cloud.mail.ru/public/GMPY/4XTn3AEJi

[Nataly-Mak]

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

Конечно, потому что полный букет для остатков на 5. Двойка в последнем остатке единственная, заменяем на присутствующую уже четверку и оп-ля. Про симметричность проверка не знает.

Это всё понятно. Как сделать хороший паттерн(ы) с разностью 252

[Dmitriy40]

Вам перечислить ВСЕ паттерны для КПППЧ длиной 17 и разницей 252? Их есть у меня.
Вот три основных:
0 12 30 36 42 90 96 120 126 132 156 162 210 216 222 240 252
0 6 12 42 72 90 96 120 126 132 156 162 180 210 240 246 252
0 6 12 30 42 90 96 120 126 132 156 162 210 222 240 246 252
И плюс из вот этой КПППЧ длиной 19 можно получить ещё 6 разных паттернов удалением симметричной пары внутренних чисел:
0 6 12 30 42 72 90 96 120 126 132 156 162 180 210 222 240 246 252

Итого будет всего 9 разных паттернов для КПППЧ длиной 17 и разницей 252.

-- 19.07.2015, 18:39 --

Паттерны с большей разницей чем минимальная более вероятно найдутся раньше последней. Это было и с 13, и с 15 (которая с минимальной разницей не найдена вообще), и с 16, и с 20, и с 22. Не вижу причин для 17-ки изменить этому эмпирическому правилу.

С другой стороны, чем больше разница, тем больше возможных паттернов, в частности из-за увеличения количества паттернов, получаемых из КПППЧ большей длины. А для разницы в 408 уже возможны и КПППЧ длиной 25, из каждой из которых можно наделать до 7920 разных паттернов для КПППЧ длиной 17. На самом деле разных паттернов будет конечно сильно меньше, но всё равно сотни (могу и точно подсчитать, но лень).

-- 19.07.2015, 18:48 --

Использовать primesieve и искать не все КПППЧ, а лишь проверять на паттерны - будет сильно медленее. Primesieve за секунду генерит все простые числа в интервале до миллиарда, паттерны же будут встречаться никак не реже одного на каждый миллион. Сейчас проверка на КПППЧ занимает не больше 10% общего времени, если даже с паттернами она будет мгновенной (чего точно не будет), общее ускорение работы не превысит тех самых 10%.

А запускать primesieve для получения простых чисел только в районах возможного нахождения паттернов тем более лишено смысла: 2000 запусков даже для просеивания интервала длиной 400 будет в сотни раз (!) медленнее одного запуска для просеивания интервала 2млрд, как сейчас сделано. Можете убедиться в этом лично: запустите программу whitefox-а с фактором f2000 (для уменьшения размера интервала до 1млн) и посмотрите на скорость ...

[Dmitriy40]

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

Выложил в облако результаты поиска КПППЧ длиной 16
https://cloud.mail.ru/public/GMPY/4XTn3AEJi

Спасибо!
Перепроверил их на реальную длину КПППЧ, оказалось 742шт имеют длину 18, 42шт имеют длину 20, одна длину 22 и одна длину 24 (её приводил сам Begemot82). Покажу здесь 20-ки и 22-ки (18-ки выложу по запросу, файл 63К):

(КПППЧ длиной 20)

20050265892293369: 0 54 74 122 150 204 222 258 302 314 348 360 404 440 458 512 540 588 608 662
20139682230851213: 0 38 56 98 104 116 120 150 206 216 218 228 284 314 318 330 336 378 396 434
20173798578216929: 0 2 44 50 60 62 78 84 132 158 174 200 248 254 270 272 282 288 330 332
20228298726003691: 0 10 12 58 66 96 112 120 138 192 196 250 268 276 292 322 330 376 378 388
20293057997458229: 0 14 20 44 74 84 98 114 120 128 144 152 158 174 188 198 228 252 258 272
20460596704470443: 0 36 48 50 78 80 104 120 164 170 174 180 224 240 264 266 294 296 308 344
20536681582396741: 0 40 66 82 90 130 168 172 178 192 196 210 216 220 258 298 306 322 348 388
20536850814354731: 0 108 126 150 176 216 240 260 278 288 308 318 336 356 380 420 446 470 488 596
20635045302174557: 0 2 24 42 104 114 134 156 176 234 272 330 350 372 392 402 464 482 504 506
21048654278196509: 0 2 18 60 90 108 110 150 170 174 248 252 272 312 314 332 362 404 420 422
21170862378717757: 0 6 10 34 46 52 66 94 96 132 214 250 252 280 294 300 312 336 340 346
21361701238704523: 0 6 28 100 138 160 196 204 208 210 244 246 250 258 294 316 354 426 448 454
21576971429526361: 0 30 46 88 112 120 136 156 162 172 216 226 232 252 268 276 300 342 358 388
21629627915874617: 0 6 62 92 116 122 150 170 174 176 240 242 246 266 294 300 324 354 410 416
21631499322824383: 0 6 28 100 108 160 178 198 220 226 270 276 298 318 336 388 396 468 490 496
21793508675661241: 0 22 36 52 58 70 88 96 138 150 268 280 322 330 348 360 366 382 396 418
21828456758733509: 0 2 42 54 92 110 114 122 152 164 180 192 222 230 234 252 290 302 342 344
21902631804002863: 0 18 28 34 58 84 88 114 148 160 168 180 214 240 244 270 294 300 310 328
22026409453892593: 0 94 96 120 124 138 166 204 208 228 256 276 280 318 346 360 364 388 390 484
22033246171685251: 0 6 18 28 40 42 66 88 90 126 142 178 180 202 226 228 240 250 262 268
22113591701702353: 0 30 54 58 76 88 124 154 186 196 228 238 270 300 336 348 366 370 394 424
22147585019333629: 0 10 22 34 72 114 120 144 190 232 240 282 328 352 358 400 438 450 462 472
22153342686887497: 0 96 100 112 120 186 192 196 226 232 270 276 306 310 316 382 390 402 406 502
22231237014492587: 0 12 14 50 60 74 92 132 144 146 300 302 314 354 372 386 396 432 434 446
22320345415548629: 0 18 54 74 168 198 210 228 282 290 312 320 374 392 404 434 528 548 584 602
22422946576245113: 0 6 30 38 78 114 140 156 170 176 288 294 308 324 350 386 426 434 458 464
22460992263747139: 0 42 70 72 90 100 120 144 160 204 238 282 298 322 342 352 370 372 400 442
22545401717360051: 0 12 38 48 78 98 122 140 158 168 200 210 228 246 270 290 320 330 356 368
22703948497542329: 0 14 20 42 98 128 132 168 180 218 294 332 344 380 384 414 470 492 498 512
22760075994361837: 0 10 24 52 66 76 132 150 172 190 216 234 256 274 330 340 354 382 396 406
22829621675874917: 0 2 26 72 134 156 176 182 186 192 254 260 264 270 290 312 374 420 444 446
22855484623076527: 0 10 22 24 64 66 102 112 120 126 130 136 144 154 190 192 232 234 246 256
22962575708458427: 0 6 12 90 156 174 192 194 200 224 282 306 312 314 332 350 416 494 500 506
23055443650873301: 0 42 66 68 78 122 126 176 180 188 240 248 252 302 306 350 360 362 386 428
23108207887877221: 0 6 30 76 90 142 168 222 228 238 300 310 316 370 396 448 462 508 532 538
23153339001452171: 0 42 50 68 80 96 182 206 228 240 248 260 282 306 392 408 420 438 446 488
23184741606995923: 0 30 40 84 136 166 190 208 226 234 250 258 276 294 318 348 400 444 454 484
23277349778365091: 0 6 62 90 110 156 180 182 192 212 216 236 246 248 272 318 338 366 422 428
23308307954556913: 0 36 40 58 96 106 138 148 208 210 226 228 288 298 330 340 378 396 400 436
23485607611797833: 0 8 38 90 140 146 176 186 218 248 288 318 350 360 390 396 446 498 528 536
23662050259308023: 0 8 24 38 56 84 110 114 180 260 324 404 470 474 500 528 546 560 576 584
23666296989588271: 0 22 36 40 58 78 100 102 106 118 210 222 226 228 250 270 288 292 306 328

(КПППЧ длиной 22)

23122811970297833: 0 6 36 44 50 68 80 84 114 140 146 198 204 230 260 264 276 294 300 308 338 344

-- 19.07.2015, 20:06 --

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

Если мы имеем 10 отдельных программ, тогда нам нужен такой компьютер, на котором можно запускать одновременно 10 программ, а это не у всех имеется.

Такой компьютер имеется у ВСЕХ уже лет так 30. У Вас тоже такой. Уже Windows 1.0 в 1985-м году имела поддержку многозадачности и соответственно могла запускать одновременно хоть 10 программ, хоть 10000 (если памяти у компьютера хватило бы). Все последующие версии Windows лишь улучшали поддержку многозадачности.

Другое дело, что на однопроцессорных одноядерных однопотоковых системах (а много ли таких осталось на руках? не думаю, уже даже телефоны все многоядерные ) запуск одновременно нескольких вычислительных программ не приводит к ускорению всей работы (т.е. уменьшению времени выполнения всего задания) (кроме некоторых исключительных случаев). Но запускать всё равно МОЖНО! Не вводите людей в заблуждение.

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

-- 19.07.2015, 20:20 --

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

А для разницы в 408 уже возможны и КПППЧ длиной 25, из каждой из которых можно наделать до 7920 разных паттернов для КПППЧ длиной 17. На самом деле разных паттернов будет конечно сильно меньше, но всё равно сотни (могу и точно подсчитать, но лень).

Ошибся, подсчитал точно, из двух возможных КПППЧ длиной 25 с разницей 408 всего можно получить 11880 уникальных паттерна для КПППЧ длиной 17 и разницей 408. Не сотни, а почти 12 тысяч однако.

[Begemot82]

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

Вот три основных:
0 12 30 36 42 90 96 120 126 132 156 162 210 216 222 240 252
0 6 12 42 72 90 96 120 126 132 156 162 180 210 240 246 252
0 6 12 30 42 90 96 120 126 132 156 162 210 222 240 246 252

Почему эти основные? Вторая и третья тоже получаются из КПППЧ длиной 19. Уточните, пожалуйста.

[Dmitriy40]

Begemot82
Да, это моя неверная терминология, плюс недостаток в программе, она сначала выдала эти три КПППЧ длиной 17, а потом уже КПППЧ длиной 19. Из которой получаются 8 разных паттернов, два из которых совпадают с этими двумя КПППЧ длиной 17.
На самом деле "основная" КПППЧ тут получается одна первая, не получаемая из КПППЧ большей длины с той же разницой, Вы правы. Но возможно она входит в какую-то КПППЧ большей длины и с большей разницой, это проверить трудно.

-- 19.07.2015, 20:45 --

Да, можно не трудиться проверять вычеты моих паттернов по 2, 3, 5, 7, 11, 13 - все такие числа из паттернов исключены самим принципом построения паттернов. Вот делимость на 17 и 19 я проверял сам руками/глазами. Делимость (вычеты) на бОльшие числа для КПППЧ 17 и 19 проверять нет необходимости вообще (надеюсь понятно почему).

-- 19.07.2015, 21:11 --

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

Нашла из английской Википедии выход на страницу, где паттерны проверяются на допустимость.
http://primes.utm.edu/glossary/includes/ktuple.php

Мне кажется тут проверяют на k-tuple, а не на КПППЧ, это очень разные вещи. И получить КПППЧ из k-tuple возможно лишь для тех k-tuples (для k от 16 до 50 включительно), что я указывал выше:

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

КПППЧ длиной 16 возможны вообще лишь для k-tuplets размером 33, 34, 39, 40, 42, 47. Для первых двух разница в КПППЧ будет 74 (6 разных вариантов), для остальных 82 (10 разных вариантов). Ни из одной из этих КПППЧ нужный квадрат не собирается.

Нечётной длины КПППЧ из них получаются лишь длиной не более 3, об этом тоже писал выше.

-- 19.07.2015, 21:18 --

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

Я понимаю так, что с разностью 300-400 практически невозможно сочинить подходящий паттерн для нашей задачи;

Вполне возможно и даже совсем не трудно, из КПППЧ длины 25 с разницей 396 можно сочинить 7920 паттернов для КПППЧ длиной 17 (с той же разницей 396). А из второй КПППЧ длиной 25 с разницей 396 можно добавить ещё несколько тысяч паттернов. Выбирайте любой (любые).
Плюс можно рассмотреть и КПППЧ меньшей длины, с меньшей разницей, не получаемые из этих двух КПППЧ длиной 25.
В общем десяток тысяч допустимых паттернов получить вполне легко.

-- 19.07.2015, 21:28 --

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

Но возможно она входит в какую-то КПППЧ большей длины и с большей разницей, это проверить трудно.

А, нет, не трудно: она входит в КПППЧ длиной 33 с разницей 588. Соответственно и во все КПППЧ меньшей длины (с отрезанными краями).
КПППЧ длиной более 33 я просто не выводил в файл, т.к. малоинтересны.

[Nataly-Mak]

Эксперимент

Беру два паттерна для КПППЧ длины 17, найденные Begemot82:

{0 12 30 42 60 72 78 102 120 138 162 168 180 198 210 228 240}
{0 24 42 54 72 84 90 114 132 150 174 180 192 210 222 240 264}

Генерирую простые числа в интервале [1000000, 2000000].
Сгенерировался массив из 70435 простых чисел.
Организую проверку чисел данного массива на наличие КПППЧ, соответствующих заданным паттернам.
Если не напортачила в программе (чем проще программа, тем легче наделать в ней ошибок ), для первого паттерна максимум соответствия - 5 элементов КПППЧ:

1204669  1204681  1204699  1204711  1204729

для второго - всего 4 элемента:

1506317  1506341  1506359  1506371

Конечно, выведено только по одному решению, решений с таким количеством соответствий, думаю, будет много; у меня программа работает до первого решения.
И это всё!
Как выполняется процедура проверки, всем понятно. Выше я немного писала об этом.
Алгоритм совершенно прозрачен.
Но вот генератор primesieve я прикрутить не умею

-- Пн июл 20, 2015 08:28:02 --

Продолжила выданный программой набор из 5 элементов для первого паттерна:

1204669 1204681 1204699 1204711 1204729 1204741 1204747 1204771 1204789 1204807 1204831 1204837 1204849 1204867 1204879 1204897 1204909

Решение с дырками сколько дырок (не простых чисел), не проверяла.

Вполне себе симметричная 17-ка, только... не все числа в ней простые.

[Nataly-Mak]

Повторила эксперимент в интервале [2000000, 5000000].
Сгенерировался массив из 199580 простых чисел.
Паттерны те же. Для обоих паттернов максимум соответствий - 5 элементов (первые решения):

3695539  3695551  3695569  3695581  3695599
2429899  2429923  2429941  2429953  2429971

Ну, а сколько будет соответствий в массиве, например, из миллиона простых чисел

Конечно, напасть на КПППЧ, соответствующую заданному паттерну, непросто.
Но что-то надо пытаться делать.
По программе whitefox тоже ведь непросто. Сколько уже крутим и... ни одной 17-ки не найдено!
К тому же, известен опыт Jarek, он ищет кортежи по заданному паттерну и находит их.