В данной статье описывается «решето Вдовина» для поиска составных и простых чисел для рядов А(а) = 2а+1, B(b) = 6b-1 и С(с) = 6с+1. Через выборку решетом раскрывается тайна распределения простых чисел-близнецов.
Идея работы решета Вдовина – выбрать составные числа в последовательности заданного ряда - через идентификаторы или порядковые номера их расположения в ряду по формуле распределения составных чисел. Затем через исключение найденных идентификаторов из множества натуральных чисел, получить нахождение простых чисел.
Исследуем ряд нечетных чисел, которые образовываются формулой вида А(а) = 2а+1:
а | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 |
А(а) = 2а+1 | 3 | 5 | 7 | 9 | 11 | 13 | 15 | 17 | 19 | 21 | 23 | 25 | 27 | 29 | 31 | 33 | 35 |
Делители |
|
|
| 3*3 |
|
| 3*5 |
|
| 3*7 |
| 5*5 | 3*9 |
|
| 3*11 | 5*7 |
Возьмем первое нечетное число ряда А(а) = 2а +1, А(1) = 2*1 + 1 = 3, если к идентификатору а = 1 данного числа, прибавим значение самого числа А(1) = 3, получим идентификатор первого составного числа А(а) + а = А(1) + 1 = 3 +1 = 4, если посмотрим на таблицу то под порядковым номером четыре будет находиться А(4) = 2*4+1 = 9, которое делится на А(1) = 3.
И если к найденному идентификатору а = 4 повторно прибавить значение А(1), получим второй идентификатор А(а) + А(а) + а = 2*А(а) + а = 2*А(1) + 1 = 2*3 + 1 = 7, делящегося на три А(7) = 2*7+1 = 15.
Таким образом можем получить позиции всех чисел, делящиеся на три через формулу k*А(а) + а, получая 4, 7, 10, 13, 16…, путем перебора в формуле коэффициента k = 1, 2, 3, 4 …, при а = 1. А через формулу последовательности нечетных чисел А(а) = 2а+1, получить значения всех чисел делящиеся на три. В нашей таблице эти числа будут А(4) = 9, А(7) = 15, А(10) = 21, А(13) = 27, А(16) = 33 и т.д.
Если обобщить распределение составных чисел для данного ряда, то мы получили каждое третье число – составное и оно делиться на три, каждое пятое число будет делиться на пять, и каждое седьмое число делиться на семь и т.д. И положение данных составных определяется по формуле решета Вдовина k * А(а) + а, где s – идентификатор составных чисел, k – количество повторов числа А(а) = 2а+1.
Формулу решета для ряда нечетных чисел, можно получить из формулы решета Сундарама (i + j + 2ij), если выделим общий множитель в первом и третьем слагаемом получаем i*(2j+1) + j и если обозначить k = i - как повторы числа А(j) = 2j+1, получим распределение составных чисел k*A(j) + j или формулу решета Вдовина для нечетных чисел .
Алгоритм решета Вдовина предусматривает исключение из ряда натуральных чисел от 1 до N идентификаторы составных чисел:
Шаг 1. Создаем список целых чисел от 1 до N.
Шаг 2. Из этого списка вычеркиваем все числа вида k А(а) + а, где А(а) = 2а+1, k и а – натуральные числа, а > 0, k > 0, k А(а) + а ≤ N.
Перебор:
а = 1, 2, …, ⌊(√(2N+1) − 1)/2⌋;
k = 1, 2, …, ⌊(N − а)/(2а + 1)⌋.
Шаг 3. Каждое оставшиеся число умножаем на 2 и прибавляем 1.
Решето Вдовина (k * А(а) + а) в отличие от решета Сундарама (a + 2ak + k), позволяет проводить выборку идентификаторов с определенными свойствами, при заданном идентификаторе – а, через перебор k, с получением идентификаторов чисел делящиеся на А(а) = 2а+1., что упрощает понимание распределения составных чисел в ряду. Данное решето не является заменой решета Сундарама и служит для анализа распределение простых чисел в исследуемом ряду через местоположение составных чисел.
Перейдем к ряду чисел B(b) = 6b-1:
b | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 |
B(b) = 6b-1 | 5 | 11 | 17 | 23 | 29 | 35 | 41 | 47 | 53 | 59 | 65 | 71 | 77 | 83 | 89 | 95 | 101 |
Делители |
|
|
|
|
| 5*7 |
|
|
|
| 5*13 |
| 7*11 |
|
| 5*19 |
|
По аналогии для ряда нечётных чисел, мы можем наблюдать зависимость расположения составных чисел от идентификаторов делителей составного числа. Например, для чисел делящиеся на пять будут идентификаторы 6, 11, 16 …, что соответствует числам 35, 65, 95… которые можно получить через k * В(b) + b, где b = 1, k – количество повторов В(b) = 6b-1.
Аналогично для чисел делящиеся на 11 можем получить номера расположения составных чисел делящиеся на 11 перебирая k, при b = 2 в формуле k B(b) + b = k 11 + 2 = 13, 24, 35, 46…. Продолжая выборку, мы можем выбрать идентификаторы всех составных чисел, а оставшиеся идентификаторы будут определять простые числа, что указано в таблице, как числа без делителей.
Необходимо отметить, что данная зависимость вытекает из свойств чисел вида 6n-1 и 6n+1, где любое число при делении на шесть может давать один из шести остатков: 0, 1, 2, 3, 4, 5. Это значит, что любое число можно представить в одном из видов:
6m – данные числа делятся на 2 и 3.
6m+1
6m+2 = 2(3m+1) – данные числа делятся на 2
6m+3 = 3(2m+1) – данные числа делятся на 3
6m+4 = 2(3m+2) – данные числа делятся на 2
6m+5 = 6(m+1) – 1
Из этого следует, что любое простое число (большее 2 и 3) имеет вид 6n-1 или 6n+1. В свою очередь любое составное число ряда 6n+1 и 6n-1 можно представить как произведением простых чисел вида (6i +1) и (6j - 1). Но для нашего ряда 6b-1 подходят составные полученные как (6i +1)(6j - 1), иначе при (6i +1)(6j + 1) и (6i - 1)(6j - 1) получим составные для ряда 6b+1.
При этом один из делителей составного числа 6j - 1, находиться в нашем исследуемом ряду 6b-1. И если для ряда B(b) = 6b-1, все составные числа будут определяться как произведением чисел вида (6i +1)(6j - 1), тогда можем получить (6i +1)(6j - 1) = 36ij - 6i + 6j - 1 = 6 (6ij - i + j) +1 = 6s -1, где s - определяет расположение составных чисел c идентификатором 6ij - i +j = i (6j - 1) + j и если обозначить b = j, k = i получим k*B(b) + b или формулу распределения составных чисел для решета Вдовина.
Алгоритм решета Вдовина для данного ряда, аналогичен для ряда нечетных чисел, также предусматривает исключение из ряда натуральных чисел от 1 до N идентификаторов составных чисел:
Шаг 1. Создаем список целых чисел от 1 до N.
Шаг 2. Из этого списка вычеркиваем все числа вида k В(b) + b, где В(b) = 6b-1, k и b – натуральные числа, b > 0, k > 0, k B(b) + b ≤ N.
Перебор:
b = 1, 2, …, ⌊(√(6N-1) + 1)/6⌋;
k = 1, 2, …, ⌊(N − b)/(6b - 1)⌋.
Шаг 3. Каждое оставшиеся число умножаем на 6 и вычитаем 1.
Перейдем к ряду чисел С(с) = 6с+1:
с | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 |
С(с) = 6с+1 | 7 | 13 | 19 | 25 | 31 | 37 | 43 | 49 | 55 | 61 | 67 | 73 | 79 | 85 | 91 | 97 | 103 |
Делители |
|
|
| 5*5 |
|
|
| 7*7 | 5*11 |
|
|
|
| 5*17 | 7*13 |
|
|
Этот ряд уже посложнее, кроме составных чисел, которые получены от идентификаторов чисел данного ряда 6с+1 (жирный шрифт), есть еще и другие делители (подчеркнутый шрифт), но всё по порядку.
Сначала делители которые мы можем получить, как и в предыдущих рядах через формулу решета вида k * С(с) + с и перебирая коэффициент k, получаем для чисел делящиеся на С(1) = 7 следующие позиционные обозначения — 8, 15, 22…, для чисел делящиеся на С(2) = 13 получим идентификаторы — 15, 28, 41… Таким образом мы выбрали часть составных чисел, в нашей таблице — они обозначены жирным шрифтом.
Перейдем к другим идентификаторам составных чисел, обозначенные подчеркнутым шрифтом, такие как С(4) = 25 = 5*5, С(9) = 55 = 5*11, С(14) = 85 = 5*17, они уже будут находиться через выражение k В(b) - b, где B(b) = 6b-1. Например числа делящиеся на пять — имеют идентификаторы 4, 9, 14, 19 …
Данное свойство распределение составных чисел, как и обозначено при исследование ряда B(b) = 6b-1, определяется из свойств чисел вида 6n-1 и 6n+1. Где каждое составное число можно представить как (6i +1)(6j + 1) или (6i - 1)(6j - 1) для нашего ряда С(с) = 6с+1.
Получаем (6i + 1)(6j + 1) = 36ij + 6i + 6j +1 = 6 (6ij + i + j) +1 = 6s1 + 1, где s1 - определяет расположение составных чисел c идентификатором 6ij + i + j = i (6j+1) + j и, если обозначить c = j, k = i, получим k*С(с) + с первую формулу для ряда С(с) = 6с+1.
Также (6i - 1)(6j - 1) = 36ij - 6i - 6j +1 = 6 (6ij - i - j) +1 = 6s2 + 1, где s2 - определяет расположение составных чисел c идентификатором 6ij - i - j = i (6j-1) - j и, если обозначить b = j, k = i, В(b) = 6j-1, получим k*В(b) - b вторую формулу для ряда С(с) = 6с+1.
Объединим наши изыскания по распределению составных чисел в ряду С(с) = 6с+1, получаем, что идентификаторы составных чисел определяются формулами k1 С(с) + с и k2 В(b) - b, где С(c) = 6с+1, B(b) = 6b-1 и k1, k2 = 1, 2, 3, 4, 5 … независимые друг от друга коэффициенты.
Алгоритм решета Вдовина для данного ряда, будет оперировать двумя формулами, также предусматривает исключение из ряда натуральных чисел от 1 до N идентификаторов составных чисел:
Шаг 1. Создаем список целых чисел от 1 до N.
Шаг 2. Из этого списка вычеркиваем все числа вида k1 С(с) + с, где С(с) = 6с+1, k1 и с – натуральные числа, с > 0, k1 > 0, k1 С(с) + с ≤ N.
Перебор:
с = 1, 2, …, ⌊(√(6N+1) − 1)/6⌋;
k1 = 1, 2, …, ⌊(N − с)/(6с + 1)⌋.
Шаг 3. Из списка оставшихся чисел вычеркиваем все числа вида k2 В(b) - b, где B(b) = 6b-1, k2 и b – натуральные числа, b > 0, k2 > 0, k2 B(b) - b ≤ N.
Перебор:
b = 1, 2, …, ⌊(√(6N+1) − 1)/6⌋;
k2 = 1, 2, …, ⌊(N − b)/(6b - 1)⌋.
Шаг 4. Каждое оставшиеся число умножаем на 6 и увеличиваем на 1.
Можно заметить, что решето Вдовина является универсальным инструментом анализа распределение чисел в заданных рядах и позволяет выбирать составные числа с заданными свойствами.
Тайна чисел-близнецов:
Числа-близнецы (или простые близнецы) — это пары простых чисел, которые отличаются друг от друга ровно на 2. Например, (3, 5), (5, 7), (11, 13), (17, 19), (29, 31) и так далее.
Воспользуемся одним из свойств данных чисел – формой представления, где все пары чисел-близнецов, кроме (3,5), имеют вид (6n-1, 6n+1). Для этого рассмотрим таблицу:
n | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 |
6n-1 | 5 | 11 | 17 | 23 | 29 | 35 | 41 | 47 | 53 | 59 | 65 | 71 | 77 | 83 | 89 | 95 | 101 |
6n+1 | 7 | 13 | 19 | 25 | 31 | 37 | 43 | 49 | 55 | 61 | 67 | 73 | 79 | 85 | 91 | 97 | 103 |
Делители |
|
|
| 5*5 |
| 5*7 |
| 7*7 | 5*11 |
| 5*13 |
| 7*11 | 5*17 | 7*13 | 5*19 |
|
Из таблицы видно, что числа-близнецы образуются, где нет составных чисел в одном из рядов 6n-1 и 6n+1 (обозначено жирным шрифтом). А данное распределение составных чисел соответствует ранее исследованным свойствам рядов B(b) = 6b-1 и С(с) = 6с+1, поэтому если мы объединим формулы определения идентификаторов составных чисел для рядов B(b), С(с) мы получим распределение идентификаторов в которых числа-близнецы не существуют и соответственно исключая их из заданного ряда натуральных чисел от 1 до N получим идентификаторы в которых образуются числа-близнецы, тем самым мы создадим формулу распределения составных чисел-близнецов для решета Вдовина или формулу Yk2ru:
Пример работы нашего решета, для начала найдем значения идентификаторов при n = 1, перебором коэффициента k1 в первой формуле k1 (6n-1) – n, получим 4, 9, 14, 19 …, теперь для n=2, получим 9, 20, 31, 42…, и т.д. Аналогично получим идентификаторы для второй формулы k2 (6n-1) + n = 6, 11, 16, 21…, теперь для n=2, получим 13, 24, 35, 46…, и т.д. Также получим идентификаторы при n = 1 в третье формуле k3 (6n+1) + n = 8, 15, 22, 29…, для n=2, получим 15, 28, 41, 54…, и т.д.
Если взять значения n = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16 для нахождения чисел-близнецов до 100, и если из данного ряда исключить ранее найденные идентификаторы составных чисел 4, 6, 8, 9, 11, 13, 14, 15, 16, получим порядковые номера n = 1, 2, 3, 5, 7, 10, 12, где находятся наши числа-близнецы (6n-1, 6n+1) = (5, 7), (11, 13), (17, 19), (29, 31), (41, 43), (59, 61), (71, 73).
Алгоритм решета Вдовина для чисел близнецов, будет оперировать уже тремя формулами, и также предусматривает исключение из ряда натуральных чисел от 1 до N идентификаторов составных чисел:
Шаг 1. Создаем список целых чисел от 1 до N.
Шаг 2. Из этого списка вычеркиваем все числа вида k В(b) + b, где В(b) = 6b-1, k и b – натуральные числа, b > 0, k > 0, k B(b) + b ≤ N.
Перебор:
b = 1, 2, …, ⌊(√(6N-1) + 1)/6⌋;
k = 1, 2, …, ⌊(N − b)/(6b - 1)⌋.
Шаг 3. Из этого списка вычеркиваем все числа вида k1 С(с) + с, где С(с) = 6с+1, k1 и с – натуральные числа, с > 0, k1 > 0, k1 С(с) + с ≤ N.
Перебор:
с = 1, 2, …, ⌊(√(6N+1) − 1)/6⌋;
k1 = 1, 2, …, ⌊(N − с)/(6с + 1)⌋.
Шаг 4. Из списка оставшихся чисел вычеркиваем все числа вида k2 В(b) - b, где B(b) = 6b-1, k2 и b – натуральные числа, b > 0, k2 > 0, k2 B(b) - b ≤ N.
Перебор:
b = 1, 2, …, ⌊(√(6N+1) − 1)/6⌋;
k2 = 1, 2, …, ⌊(N − b)/(6b - 1)⌋.
Шаг 4. Каждое оставшиеся число умножаем на 6 и увеличиваем на 1 и уменьшаем на 1, получаем два числа-близнеца.
Заключение:
1. Решето Вдовина является универсальным инструментом для анализа распределения составных чисел и служит для исследования закономерностей появления простых чисел в изучаемом ряду.
2. Закономерность расположения составных чисел в рядах B(b) = 6b-1 и С(с) = 6с+1 позволяет создать решето для изучения распределения чисел-близнецов.
Спасибо за интерес к теме!