Решето для мам

[Andrey A]

Извиняюсь за нестрогость изложения. Если тут не обошлось без прокола, нечего и копья ломать. Идея проста:
Выпишем некоторое конечное количество произвольных сравнений по простым модулям $p_1,p_2,p_3,…,p_n.$ Пусть последовательность $A$ образована вычеркиванием из натурального ряда всех членов, удовлетворяющих заданным сравнениям (необязательно сначала, но начиная с некоторой фиксированной точки для каждого сравнения).

Лемма. Если $A$ конечна, то вычеты хотя бы по одному простому модулю образуют полную систему, т.е. $0 \mod p,1 \mod p,2 \mod p,…,p-1 \mod p.$
Доказательство. Исходя из обратного, допустим, что $A$ конечна, и ни по одному простому модулю система вычетов не является полной. Тогда каждому простому модулю можно поставить в соответствие хотя бы одно сравнение отличное от заданных. Запишем их в систему и с помощью китайской теоремы найдем $N$, удовлетворяющее всем новым сравнениям. Члены бесконечной последовательности $N \mod p_1\cdot p_2\cdot p_3\cdot …\cdot p_n$ не удовлетворяют тогда ни одному из первоначальных сравнений и, значит, начиная с некоторого достаточно большого номера принадлежат последовательности $A$, что противоречит предположению о конечности $A$. Доказано.

Частный случай: если по каждому модулю позволено заявить не более $2-$х сравнений, то результатом отсева по нечетным простым всегда останется некая бесконечная последовательность.


Близнецы — наиболее близкие соседние точки в последовательности простых за исключением пары $2,3.$ Каждая пара близнецов выражается формой $2m-1,2m+1$ (для удобства $m$ — мама). Наименьшими в ряду мам будим считать $1,2,3,$ хотя порождаемая ими единица — не простой ребенок. Далее пошагово.
— Из следующих членов натурального ряда вычеркиваем $\pm 2 \mod 3;\ \pm 3 \mod 5,7:$
$1,2,3,\not4,\not5,6,\not7,\not8,9,\not{10},\not{11},\not12,\not{13},\not{14},15,\not{16},\not{17},\not18,\not{19},\not{20},21,\not{22},\not{23},$ $\not24,\not{25},\not{26},\not27,\not{28},\not{29},30,\not{31},\not{32},\not33,\not{34},\not{35},36,\not{37},\not{38},…$
Ближайшее из незачеркнутых $6$ — мама простых $11,13$.
— Из оставшихся $>6$ вычеркиваем $\pm 6 \mod 11,13.$ Ближайшее из незачеркнутых $9$ — мама простых $17,19.$
Ну, и т.д.
— Получив ближайшее незачеркнутое $m$, на очередном этапе вычеркиваем \pm m \mod 2m-1,2m+1.$

Собственно, и всё. Понимаю, что тут требуется доказательство или как минимум обоснование, но предположим пока что алгоритм верный. Исходя из гипотезы о конечном числе близнецов делаем вывод о конечном числе мам и существовании наибольшей из них. Добравшись до нее с помощью алгоритма, имеем результатом либо полное вычеркивание оставшихся членов натурального ряда, либо частичное. Во втором случае находим наименьшее из невычеркнутых и получаем новую маму, что противоречит гипотезе. В первом случае оказывается неверна лемма из начала поста. Значит их бесконечно много.

[mihaild]

Если я не обсчитался, то получается последовательность

6,9,15,21,30,36,51,54,69,75,90,96,99,114,120,135,141,156,174,210,216,231,261,285,300,309,321,330,405,411,414,426

(Оффтоп)

mom 6
mom 9
Skip 12 because of prime 5 with mom 3
mom 15
Skip 18 because of prime 5 with mom 3
mom 21
Skip 24 because of prime 7 with mom 3
Skip 27 because of prime 5 with mom 3
mom 30
Skip 33 because of prime 5 with mom 3
mom 36
Skip 39 because of prime 7 with mom 3
Skip 42 because of prime 5 with mom 3
Skip 45 because of prime 7 with mom 3
Skip 48 because of prime 5 with mom 3
mom 51
mom 54
Skip 57 because of prime 5 with mom 3
Skip 60 because of prime 7 with mom 3
Skip 63 because of prime 5 with mom 3
Skip 66 because of prime 7 with mom 3
mom 69
Skip 72 because of prime 5 with mom 3
mom 75
Skip 78 because of prime 5 with mom 3
Skip 81 because of prime 7 with mom 3
Skip 84 because of prime 13 with mom 6
Skip 87 because of prime 5 with mom 3
mom 90
Skip 93 because of prime 5 with mom 3
mom 96
mom 99
Skip 102 because of prime 5 with mom 3
Skip 105 because of prime 11 with mom 6
Skip 108 because of prime 5 with mom 3
Skip 111 because of prime 13 with mom 6
mom 114
Skip 117 because of prime 5 with mom 3
mom 120
Skip 123 because of prime 5 with mom 3
Skip 126 because of prime 11 with mom 6
Skip 129 because of prime 7 with mom 3
Skip 132 because of prime 5 with mom 3
mom 135
Skip 138 because of prime 5 with mom 3
mom 141
Skip 144 because of prime 7 with mom 3
Skip 147 because of prime 5 with mom 3
Skip 150 because of prime 7 with mom 3
Skip 153 because of prime 5 with mom 3
mom 156
Skip 159 because of prime 11 with mom 6
Skip 162 because of prime 5 with mom 3
Skip 165 because of prime 7 with mom 3
Skip 168 because of prime 5 with mom 3
Skip 171 because of prime 7 with mom 3
mom 174
Skip 177 because of prime 5 with mom 3
Skip 180 because of prime 19 with mom 9
Skip 183 because of prime 5 with mom 3
Skip 186 because of prime 7 with mom 3
Skip 189 because of prime 13 with mom 6
Skip 192 because of prime 5 with mom 3
Skip 195 because of prime 17 with mom 9
Skip 198 because of prime 5 with mom 3
Skip 201 because of prime 13 with mom 6
Skip 204 because of prime 11 with mom 6
Skip 207 because of prime 5 with mom 3
mom 210
Skip 213 because of prime 5 with mom 3
mom 216
Skip 219 because of prime 19 with mom 9
Skip 222 because of prime 5 with mom 3
Skip 225 because of prime 11 with mom 6
Skip 228 because of prime 5 with mom 3
mom 231
Skip 234 because of prime 7 with mom 3
Skip 237 because of prime 5 with mom 3
Skip 240 because of prime 13 with mom 6
Skip 243 because of prime 5 with mom 3
Skip 246 because of prime 17 with mom 9
Skip 249 because of prime 7 with mom 3
Skip 252 because of prime 5 with mom 3
Skip 255 because of prime 7 with mom 3
Skip 258 because of prime 5 with mom 3
mom 261
Skip 264 because of prime 17 with mom 9
Skip 267 because of prime 5 with mom 3
Skip 270 because of prime 7 with mom 3
Skip 273 because of prime 5 with mom 3
Skip 276 because of prime 7 with mom 3
Skip 279 because of prime 13 with mom 6
Skip 282 because of prime 5 with mom 3
mom 285
Skip 288 because of prime 5 with mom 3
Skip 291 because of prime 7 with mom 3
Skip 294 because of prime 19 with mom 9
Skip 297 because of prime 5 with mom 3
mom 300
Skip 303 because of prime 5 with mom 3
Skip 306 because of prime 13 with mom 6
mom 309
Skip 312 because of prime 5 with mom 3
Skip 315 because of prime 17 with mom 9
Skip 318 because of prime 5 with mom 3
mom 321
Skip 324 because of prime 11 with mom 6
Skip 327 because of prime 5 with mom 3
mom 330
Skip 333 because of prime 5 with mom 3
Skip 336 because of prime 11 with mom 6
Skip 339 because of prime 7 with mom 3
Skip 342 because of prime 5 with mom 3
Skip 345 because of prime 13 with mom 6
Skip 348 because of prime 5 with mom 3
Skip 351 because of prime 19 with mom 9
Skip 354 because of prime 7 with mom 3
Skip 357 because of prime 5 with mom 3
Skip 360 because of prime 7 with mom 3
Skip 363 because of prime 5 with mom 3
Skip 366 because of prime 17 with mom 9
Skip 369 because of prime 11 with mom 6
Skip 372 because of prime 5 with mom 3
Skip 375 because of prime 7 with mom 3
Skip 378 because of prime 5 with mom 3
Skip 381 because of prime 7 with mom 3
Skip 384 because of prime 13 with mom 6
Skip 387 because of prime 5 with mom 3
Skip 390 because of prime 11 with mom 6
Skip 393 because of prime 5 with mom 3
Skip 396 because of prime 7 with mom 3
Skip 399 because of prime 17 with mom 9
Skip 402 because of prime 5 with mom 3
mom 405
Skip 408 because of prime 5 with mom 3
mom 411
mom 414
Skip 417 because of prime 5 with mom 3
Skip 420 because of prime 29 with mom 15
Skip 423 because of prime 5 with mom 3
mom 426

И $426 \cdot 2 - 1 = 851 = 23 \cdot 37$.

[Andrey A]

mihaild в сообщении #1566147 писал(а):

Если я не обсчитался...

Спасибо. Не думаю что Вы ошиблись, даже проверять не буду. $851=23 \cdot 37$ — произведение двух наименьших простых "не близнецов". Их алгоритм принимает за простое, поскольку о таких числах ему ничего не известно. Кто бы мог подумать. Прокол. Меньше только $23^2.$ Вы бы его засекли раньше, если бы в паре с ним было простое, но $23^2-2=17 \cdot 31,\ 23^2+2=3\cdot 3\cdot 59.$ Все множители из близнецов. А $37^2$ думаю сработает. Вообще, с ростом чисел количество таких проколов хоть и возрастет, но не очень быстро. $1081=23 \cdot 47,$ к примеру, отсеется по модулям $3,19$ или $13.$