Новое решето для простых чисел

За 2 тысячелетия, отделяющие нас от Эратосфена, техника «отсеивания» простых чисел развилась от примитивного «решета» до применения электронных машин, выполняющих вычисления с быстротой распространения электричества.

Но для «мелких надобностей» неплохо иметь под руками и обыкновенное «решето». Постепенно появились некоторые усовершенствования и в этой «ручной технике» отсеивания простых чисел. Например, немногим более двадцати лет назад одно из новых «решет» придумал студент-математик

С. П. Сундарам (Индия):

4 7 10 13 16 19 …
7 12 17 22 27 32 …
10 17 24 31 38 45 …
13 22 31 40 49 58 …
16 27 38 49 60 71 …

Это «решето» представляет собой таблицу, состоящую из бесконечного количества бесконечных арифметических прогрессий, причем каждый член первой прогрессии

4, 7, 10, 13, 16, 19, …

начинает новую прогрессию. Разностями прогрессий являются все нечетные числа, начиная с 3:

d1=3, d2 = 5, d3=7, d4 = 9 и т. д.

Если какое-либо число N встречается в этой таблице, то 2N 1 —непременно число составное. Если же числа N в этой таблице нет, то 2N-{-1 — число простое.

Примеры. I) В таблице нет числа N—3, следовательно, 2N + 1 =7 — число простое.

2) В таблице нет числа N— 5, следовательно, 2N+1 = 11 — число простое.

3) Числа N=6 также нет в таблице, следовательно, 2N +1 = 13 — число простое.

4) Число N=7 есть в таблице, следовательно, 2N + 1 = 15 — число составное и т. д.

Заменяя N в формуле 2N+1 по порядку всеми числами, которых нет в таблице (которые как бы просеяны сквозь данное «решето»), можно получить все простые числа, кроме числа 2.

Как доказать, что 2N+1 — число составное для чисел, «задержавшихся в решете», и простое для «просеявшихся чисел»?



Это не спам.

 

На нашем сайте собраны задачи занимательной арифметики, математики, геометрии;
задачи на смекалку и логику, головоломки, логические загадки, игры, ребусы и многое другое
2017 © Самый умный - математическая смекалка