2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Покрытие простых разностями
Сообщение01.08.2019, 06:30 
Аватара пользователя


24/01/19

265
По мотивам поста "Покрытие простых арифметическими прогрессиями из простых" https://dxdy.ru/topic135734.html.
Набор (0, 2, 5) покрывает все подряд простые в количестве n=3 штук:
2=2-0, 3=5-2, 5=5-0.
Это минимальный набор. Три числа покрывают n=3 простых.
Далее:
$n= 4 ;  0 ,  3 ,  5 ,  7 
  
n= 6 ;  0 ,  7 ,  15 ,  18 ,  20 

n= 10 ;  0 ,  6 ,  17 ,  19 ,  22 ,  29

n= 12 ;  0 ,  8 ,  15 ,  18 ,  20 ,  31 ,  37
 
n= 15 ;  0 ,  18 ,  24 ,  35 ,  37 ,  40 ,  47 ,  78

n= 19 ;  0 ,  8 ,  15 ,  18 ,  20 ,  31 ,  37 ,  61 ,  67

n= 22 ;  0 ,  6 ,  49 ,  59 ,  67 ,  74 ,  77 ,  79 ,  90 ,  96

n= 25 ;  0 ,  8 ,  15 ,  18 ,  20 ,  31 ,  37 ,  61 ,  67 ,  91 ,  97

n= 30 ;  0 ,  6 ,  7 ,  20 ,  36 ,  67 ,  79 ,  90 ,  104 ,  107 ,  109 ,  120

n= 35 ;  0 ,  22 ,  29 ,  31 ,  34 ,  48 ,  90 ,  101 ,  131 ,  137 ,  161 ,  174 ,  197

n= 38 ;  0 ,  22 ,  29 ,  31 ,  34 ,  48 ,  90 ,  101 ,  131 ,  137 ,  161 ,  174 ,  197 ,  288

n= 42 ;  0 ,  2 ,  12 ,  43 ,  49 ,  103 ,  109 ,  163 ,  169 ,  180 ,  182 ,  185 ,  192 ,  222 ,  230
  
n= 48 ;  0 ,  2 ,  12 ,  19 ,  20 ,  30 ,  32 ,  73 ,  79 ,  133 ,  139 ,  193 ,  199 ,  222 ,  225 ,  230

n= 53 ;  0 ,  8 ,  15 ,  18 ,  20 ,  31 ,  37 ,  67 ,  121 ,  127 ,  181 ,  187 ,  217 ,  258 ,  260 ,  270 ,  278

n= 59 ;  0 ,  8 ,  20 ,  30 ,  38 ,  45 ,  48 ,  50 ,  67 ,  78 ,  91 ,  151 ,  157 ,  188 ,  211 ,  217 ,  271 ,  277

n= 62 ;  0 ,  8 ,  20 ,  30 ,  38 ,  45 ,  48 ,  50 ,  67 ,  78 ,  91 ,  151 ,  157 ,  188 ,  211 ,  217 ,  271 ,  277 ,  331

n= 68 ;  0 ,  22 ,  37 ,  40 ,  42 ,  52 ,  59 ,  90 ,  113 ,  119 ,  173 ,  179 ,  233 ,  239 ,  293 ,  299 ,  340 ,  342 ,  353 ,  359 $
Впрочем, за максимальность покрытия простых чисел для больших $n$ я не ручаюсь. Просто не знаю эффективных методов поиска оптимальных последовательностей по такому сложному критерию. Последние последовательности формировались на основе предыдущих. Но это может быть неоптимальным путём.
Я привёл наборы до 20 членов. Можно ли улучшить эти результаты - ну и поделиться своим методом их получения.

 Профиль  
                  
 
 Re: Покрытие простых разностями
Сообщение03.08.2019, 16:25 
Аватара пользователя


01/06/12
974
Adelaide, Australia
podih, отличная идея! Попробую написать программку для поиска таких решений. Надо ли минимизировать самое большое число? Интересно что оно не всегда простое. Всегда ли есть 0?

Кстати можно еще покрывать суммами. Например $(1,2,5)$ покрывает первые 4 простые: $2=2, 3=1+2, 5=5, 7=2+5$. А можно даже объединить ваши разности с суммами. Таким образом ваш набор $(0,2,5)$ еще покрывает 7.

 Профиль  
                  
 
 Re: Покрытие простых разностями
Сообщение07.08.2019, 14:36 
Аватара пользователя


01/06/12
974
Adelaide, Australia
У меня получилось улучшить ваши результаты начиная с 10 членов:

Код:
size=10
n=23
0 12 23 26 42 66 71 73 79 83

size=11
n=26
0 4 10 12 17 41 57 60 71 83 101

size=12
n=31
0 6 13 24 29 30 32 66 72 103 113 133

size=13
n=36
0 3 13 15 32 56 74 79 86 116 152 163 183

size=14
n=40
0 31 67 104 109 151 157 168 170 173 180 194 198 277

size=15
n=46
0 6 30 47 49 59 62 67 133 156 163 167 198 240 246

size=16
n=50
0 30 49 67 120 150 193 206 209 211 229 240 247 343 347 360

size=17
n=56
0 6 19 49 79 109 139 169 199 206 229 246 252 258 260 263 270

size=18
n=61
0 30 90 120 150 257 259 263 266 269 271 277 281 300 313 330 360 468

size=19
n=65
0 22 29 40 42 45 59 173 203 233 239 263 269 299 310 330 342 352 370

size=20
n=70
0 30 36 60 103 180 203 259 266 269 271 293 300 311 313 330 367 420 450 452


Я уверен что эти результаты можно еще улучшить. Как всегда я использовал метод отжига.

-- 07.08.2019, 20:23 --

dimkadimon в сообщении #1408507 писал(а):
Всегда ли есть 0?

Ответ да. Допустим что мы нашли решение где меньшее число x не 0. Тогда можно вычесть x от всех чисел и получить такое же решение с наименьшим числом 0.

 Профиль  
                  
 
 Re: Покрытие простых разностями
Сообщение29.09.2019, 03:24 
Аватара пользователя


24/01/19

265
Последние результаты до 43:
Здесь $qP$ - количество членов последовательности, $sMax$ - количество простых ими покрываемое, $pMax $- сама последовательность.
Неожиданно вылезла удивительная вещь: число членов, отличающихся на $30$, превосходит все мыслимые пределы.
Данная тенденция начинается с $qP=19$, я выделил несколько серий.
Подозреваю, что это проявление "интерференции" периодов $2, 3, 5$, - но механизм этого проявления мне абсолютно непонятен.
qP= 3 sMax= 3
0 2 5
qP= 4 sMax= 4
0 4 5 7
qP= 5 sMax= 6
0 2 5 7 13
qP= 6 sMax= 10
0 6 17 19 22 29
qP= 7 sMax= 12
0 5 12 28 29 31 42
qP= 8 sMax= 15
0 1 5 8 29 31 42 48
qP= 9 sMax= 19
0 6 30 36 47 49 52 59 67
qP= 10 sMax= 23
0 4 10 12 17 41 57 60 71 83
qP= 11 sMax= 26
0 4 10 12 17 41 57 60 71 83 101
qP= 12 sMax= 31
0 6 13 24 29 30 32 66 72 103 113 133
qP= 13 sMax= 36
0 3 13 15 32 56 74 79 86 116 152 163 183
qP= 14 sMax= 41
0 22 53 89 132 136 173 179 190 192 195 202 263 299
qP= 15 sMax= 46
0 6 30 47 49 59 62 67 133 156 163 167 198 240 246
qP= 16 sMax= 50
0 30 49 67 120 150 193 206 209 211 229 240 247 343 347 360
qP= 17 sMax= 56
0 3 5 11 17 34 53 64 94 124 154 184 214 244 251 257 263
qP= 18 sMax= 61
0 30 60 90 120 150 257 259 263 266 271 277 281 299 300 313 330 360
qP= 19 sMax= 66
0 10 12 22 53 83 89 113 119 149 179 293 307 310 312 323 330 352 370
qP= 20 sMax= 72
0 1 11 13 23 54 84 90 114 120 150 180 294 308 311 313 331 353 360 371
qP= 21 sMax= 75
0 66 96 126 156 186 216 323 325 329 332 337 343 347 365 366 379 396 426 636 696
qP= 22 sMax= 80
0 18 246 276 293 306 325 329 335 337 340 343 347 349 456 486 516 546 576 606 702 726
qP= 23 sMax= 86
0 18 246 276 293 306 325 329 335 337 340 343 347 349 456 486 516 546 576 606 702 726 768
qP= 24 sMax= 95
0 6 8 12 17 18 20 26 32 199 229 259 289 319 336 349 350 356 368 379 409 439 469 499
qP= 25 sMax= 101
0 5 6 8 18 20 32 199 229 259 289 319 336 349 350 356 368 379 409 439 469 499 541 702 746
qP= 26 sMax= 109
0 6 12 22 28 40 46 78 239 269 299 329 359 389 418 419 421 426 436 449 460 479 509 539 569 599
qP= 27 sMax= 116
0 10 22 24 28 34 42 48 251 281 311 341 371 401 430 431 433 438 442 448 461 491 521 551 581 611 641
qP= 28 sMax= 122
0 12 14 20 26 32 36 54 253 283 313 343 373 403 432 433 435 440 450 463 474 493 523 553 583 613 643 673
qP= 29 sMax= 129
0 12 26 289 319 349 379 409 439 469 480 499 516 528 529 559 582 589 619 649 679 709 739 966 980 987 990 992 1008
qP= 30 sMax= 134
0 12 14 24 38 48 50 53 62 301 331 361 391 421 451 481 510 511 541 558 571 590 601 624 631 661 691 721 751 781
qP= 31 sMax= 141
0 12 24 48 50 53 62 331 361 391 421 451 481 510 511 541 558 571 590 601 624 631 661 691 721 751 781 809 835 1008 1074
qP= 32 sMax= 146
0 12 52 66 70 76 78 81 88 329 359 389 419 449 479 509 539 540 569 582 599 618 629 659 666 689 719 749 779 809 839 899
qP= 33 sMax= 155
0 30 60 120 150 180 210 223 240 270 300 307 330 349 360 389 390 420 450 480 510 540 570 600 811 878 881 883 889 893 907 1007 1019
qP= 34 sMax= 159
0 299 329 359 389 449 479 509 539 552 569 599 629 636 659 678 689 718 719 749 779 809 839 869 899 929 1140 1207 1210 1212 1218 1222 1236 1336
qP= 35 sMax= 166
0 54 353 383 413 443 503 533 563 593 606 623 653 683 690 713 732 743 772 773 803 833 863 893 923 953 983 1194 1261 1264 1266 1272 1320 1390 1504
qP= 36 sMax= 168
0 54 275 353 383 413 443 503 533 563 593 606 623 653 683 690 713 732 743 772 773 803 833 863 893 923 953 983 1194 1261 1264 1266 1272 1320 1390 1504
qP= 37 sMax= 188
0 4 18 58 70 72 144 232 341 480 508 514 520 522 523 528 534 761 821 840 881 911 941 971 1001 1024 1031 1044 1061 1091 1092 1121 1151 1181 1241 1301 1380
qP= 38 sMax= 194
0 2 6 20 72 146 234 343 482 510 516 522 524 527 530 536 763 823 842 883 913 943 973 1003 1026 1033 1046 1063 1093 1094 1123 1153 1183 1243 1303 1363 1382 2112
qP= 39 sMax= 203
0 2 6 20 72 146 234 343 482 510 516 522 524 527 530 536 763 823 842 883 913 943 973 1003 1026 1033 1046 1063 1093 1094 1123 1153 1183 1243 1303 1363 1382 1723 1992
qP= 40 sMax= 214
0 110 242 450 559 900 919 979 1039 1099 1129 1159 1188 1189 1219 1236 1249 1256 1279 1309 1339 1369 1399 1440 1459 1519 1746 1752 1757 1758 1760 1766 1772 1800 1939 2210 2262 2276 2280 2282
qP= 41 sMax= 219
0 42 413 449 790 809 869 929 989 1019 1049 1078 1079 1109 1126 1139 1146 1169 1199 1229 1259 1289 1330 1349 1409 1636 1642 1647 1648 1650 1656 1662 1690 1829 1938 2100 2152 2166 2170 2172 2969
qP= 42 sMax= 224
0 96 110 242 385 439 559 900 919 979 1039 1099 1129 1159 1188 1189 1219 1236 1249 1256 1279 1309 1339 1369 1399 1440 1459 1519 1746 1752 1757 1758 1760 1766 1772 1800 1939 2048 2210 2262 2276 2280
qP= 43 sMax= 232
0 246 260 392 469 535 589 638 709 1050 1069 1129 1189 1249 1279 1309 1338 1339 1369 1386 1399 1406 1429 1459 1489 1519 1549 1590 1609 1669 1896 1902 1907 1908 1910 1916 1922 2089 2198 2360 2412 2426 2430

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 4 ] 

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



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

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


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

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