Аннотация и ключевые слова
Аннотация (русский):
На базе множества чисел вида Θ = {6 k ± 1 / kN }, где N - множество всех натуральных чисел, являющихся полугруппой относительно операции умножения, приводятся методы определения и распределения простых чисел, составных чисел, простых чисел близнецов и составных чисел близнецов, не имеющих делителей 2 и 3 в N . Дано вычисление точного числа простых чисел в заданном интервале. Предложен способ получения простых чисел по их порядковым номерам n во множестве простых чисел p ≥ 5, а также новый алгоритм нахождения и распределения простых чисел на базе замкнутости множества Θ. Показано, что любое составное число n Θ представимо в виде произведения (6 x ± 1) (6 y ± 1), где x , yN являются натуральными решениями одного из четырех диофантовых уравнений: P ( x , y , λ) = 0: 6 xy ± x ± y - λ = 0. Доказано, что если λ есть параметр простых чисел близнецов, то ни одно из диофантовых уравнений P ( x , y , λ) = 0 не имеет решения. Приводится новый универсальный, детерминированный, полиномиальный и независимый тест, позволяющий проверить, являются ли числа вида 6 × k ± 1 простыми. Приведены алгоритмы распределения параметров простых чисел близнецов и параметров составных чисел близнецов, не делящихся на 2 и 3, даны варианты доказательств их бесконечного количества.

Ключевые слова:
простые и составные числа, параметры простых чисел, диофантовы уравнения, простые числа близнецы, тест на простоту, алгоритм распределения параметров
Текст
Введение В последние десятилетия интерес к законам распределения простых чисел [1] из теоретической сферы все больше смещается в практическую. Особо важным примером является их использование в криптографии [2], и именно поэтому любые результаты, уточняющие отдельные особенности законов распределения простых чисел, немедленно становятся предметом изучения специалистов в области криптографии. Особый интерес применительно к криптографии в системе с открытыми ключами (в частности, в системе шифрования RSA) вызывает вопрос о том, является ли данное конкретное (большое) число простым или нет. Цель работы - исследование законов распределения простых чисел , составных чисел , простых чисел близнецов и составных чисел близнецов не имеющих делителей 2 и 3 в N [3]. 1. Метод выделения простых чисел При поиске простых чисел в натуральном ряду большая потеря времени приходится на числа, делящиеся на 2 и 3. Если произвести факторизацию множества N по основанию 6, то можно упростить поиск простых чисел и исследование их свойств. Разобьем множество натуральных чисел на 2 непересекающихся подмножества Η и Θ, т. е. Пусть Η включает 1 и натуральные числа, которые при делении на 6 дают остатки 0, 2, 3, 4. Очевидно, что множество Η включает два простых числа - 2 и 3. Множество Θ содержит числа, которые при делении на 6 дают остатки 1 и 5, т. е. числа вида , т. к. выражение . Числа с остатками 0, 2, 3, 4 являются составными, т. к. делятся на 2 или на 3. Следовательно, Непосредственной проверкой нетрудно убедиться, что множество - полугруппа относительно бинарной операции умножения. При этом выполняются следующие соотношения: (1) т. е. произведения чисел вида и выражаются числами вида Определение 1. Для числа n значения числовых функций , , представленные в (1), назовём параметрами числа . Отметим, что проблема однозначного соответствия между числами n и их параметрами λ(x, y) остается открытой, т. е. одному и тому же числу n могут соответствовать несколько различных параметрических функций λ(x, y). Однако, с точки зрения последующих исследований, данный факт не является существенным. Заметим, что форма при умножении может перейти в другую форму (см. (1)). Так как множество Θ есть полугруппа относительно бинарной операции умножения, то все его составные элементы будут . (2) Во множестве Θ есть элементы у которых число множителей в (2) равно 1, т. е. они не разлагаются в произведения других чисел из Θ, эти числа являются примитивными элементами Θ, т. е. простыми числами во множестве натуральных чисел. Для каждого из выражений (1) введем свой параметр . Тогда из (1) имеем (3) т. е. получаем диофантовы уравнения связывающие числа x, y и λ: (4) Если хотя бы одно из уравнений в (4) имеет одно решение, то число n составное, если ни одно из уравнений в (1) не имеет решений, число n является простым. 2. Распределение составных чисел множества Θ Нетрудно заметить, что составные числа множества Θ формируются значениями из нижеследующих функций : (5) Составные числа множества Θ вида (обозначим их ) в силу (1) порождаются значениями не взаимно однозначных функций): и , ибо при неравных значениях аргументов значения функций могут быть равными: и . Заметим, с учетом (1), что числа вида и составные и .Составные числа множества Θ вида (обозначим их ), в силу (1), порождаются значениями функций) и . Из (1) также следует, что числа вида и составные и . Так как числа - составные, то значения переменных (x, y) являются решениями соответствующих диофантовых уравнений или . И точно так же для составных чисел значения переменных являются решениями диофантовых уравнений или . Таким образом, множество всех составных чисел множества Θ состоит из объединения . Заметим также, что для факторизации составного числа наиболее результативный и наилучший способ - воспользоваться выражением (2), т. е. число поделить на числа вида где [4]. Из (4) нетрудно вывести, что множество параметров всех четырех типов чисел (простых и составных) Θ в натуральном ряду чисел бесконечно. Действительно, например, если функция из (5) определена как множество то для любого натурального n, при число . Аналогично рассматриваются и другие функции , приведенные в (5). Таким образом, множества во всех функциях (5) являются бесконечными как объединения бесконечных множеств. Введем обозначения для множества параметров составных чисел Θ вида и множества параметров составных чисел вида . Тогда множество всех параметров составных чисел Θ будет представлять собой объединение . Очевидно, что множества бесконечны как объединения бесконечных множеств. Для определения и исследования параметров простых и составных чисел множества Θ нужно будет найти все параметрические решения диофантовых уравнений (4). Однако решения диофантовых уравнений - проблема сложная, поэтому для решения уравнений (4) можно построить таблицу значений функции или функций (5). Тогда числу λ в таблице соответствует число n составное, иначе число n простое. Для исследования параметров простых и составных чисел множества Θ зададим любые значения для значений функций (5) от 1 до , где s - заданный размер таблицы. Построим таблицу (табл. 1) с размерностью , со структурой . Заметим, что при одних и тех же значениях в каждой строке (x, y) табл. 1 имеем возрастающую последовательность функций: (6) Формирование строк и поиск значений функций (5) осуществляются по принципу Выберем для демонстрации описываемых ниже алгоритмов значение s = 10, но описываемые ниже построения могут быть реализованы для любого s. Найдем значения функций где и - составные числа, ибо значения переменных x и y известны как заранее заданные решения диофантовых уравнений (4). Пусть тогда значения функций (5) в последующей строке отличаются от значений предыдущей строки на следующие величины: для f11(x, y) - на 6x - 1; для f12(x, y) - на 6x +1; для f21(x, y) - на 6x +1; для f22(x, y) - на 6x - 1. Таблица 1 Формирование параметров составных чисел во множестве Θ x y f 11 (x, y) f12 (x, y) f21 (x, y) f22 (x, y) x y f 11 (x, y) f12 (x, y) f21 (x, y) f22 (x, y) 1 1 4 8 6 6 4 4 88 104 96 96 2 9 15 13 11 5 111 129 121 119 3 14 22 20 16 6 134 154 146 142 4 19 29 27 21 7 157 179 171 165 5 24 36 34 26 8 180 204 196 188 6 29 43 41 31 9 203 229 221 211 7 34 50 48 36 10 226 254 246 234 8 39 57 55 41 5 5 140 160 150 150 9 44 64 62 46 6 169 191 181 179 10 49 71 69 51 7 198 222 212 208 2 2 20 28 24 8 227 253 243 237 3 31 41 37 35 9 256 284 274 266 4 42 54 50 46 10 285 315 305 295 5 53 67 63 57 6 6 204 228 216 216 6 64 80 76 68 7 239 265 253 251 7 75 93 89 79 8 274 302 290 286 8 86 106 102 90 9 309 339 327 321 9 97 119 115 101 10 344 376 364 356 10 108 132 128 112 7 7 280 308 294 294 3 3 48 60 54 54 8 321 351 337 335 4 65 79 73 71 9 362 394 380 376 5 82 98 92 88 10 403 437 423 417 6 99 117 111 105 8 8 368 400 384 384 7 116 136 130 122 9 415 449 433 431 8 133 155 149 139 10 462 498 482 478 9 150 174 168 156 9 9 468 504 486 486 10 167 193 187 173 10 521 559 541 539 10 10 580 620 600 600 Пример 1. Найти составные числа множества Θ в интервале от 1 до . Вычислим в заданном интервале максимальный параметр: и из табл. 1 выпишем параметры составных чисел В результате имеем: Опираясь на определение параметров составных чисел множества Θ, найдём их значения: . Значит, полная последовательность составных чисел множества Θ в интервале будет 3. Распределение параметров простых и составных чисел Θ в N Распределение параметров простых и составных чисел множества Θ есть проаналог распределения простых чисел и составных чисел, не имеющих делителей 2 и 3 в N. Нужно будет найти все простые и составные числа Θ вида . Опишем алгоритмы построения этих чисел. Пусть в интервале от 1 до n даны записи в файле по следующей структуре: где параметры (реквизиты) id - серийные номера записей и поля F1 и F2 принимают значения «+» или «-». Перед началом алгоритмов 3.1 и 3.2 (см. ниже) в интервале построчно в поля F1 и F2 вводятся символы «+». 3.1. Алгоритм распределения простых чисел множества Θ вида 6λ - 1 Пусть меняются по принципу табл. 1. Тогда по значениям параметров и составных чисел вида из файла по прямому доступу достаются записи и в поле F1 знак «+» меняется на знак «-». Оставшиеся записи в конце алгоритма в поле F1 = «+» говорят о наличии простых чисел типа . Введем обозначения: . Тогда . 3.2. Алгоритм распределения простых чисел множества Θ вида 6λ + 1 Пусть меняются по принципу табл. 1, тогда по значениям параметров и составных чисел вида из файла по прямому доступу достаются записи с номерами и в поле F2 знак «+» меняется на знак «-». Оставшиеся записи в конце алгоритма в поле F2 = «+» говорят о наличии простых чисел типа . Пусть , . Тогда . Итак, простые числа состоят из объединения двух множеств: . Таким образом, получено распределение параметров простых и составных чисел Θ в N. Объединив алгоритмы 3.1 и 3.2 в один, получим алгоритм PrNb - алгоритм распределения параметров простых и составных чисел Θ в N. Параметры id с приписанными полями F1 и F2 со значением «+», согласно 3.1 и 3.2, являются параметрами простых чисел, а со значением «-» - параметрами составных чисел. Теорема 1. Диофантовы уравнения (4) имеют решения тогда, когда числа вида 6 × λ ± 1 - составные. Необходимость. Пусть числа вида составные, значит, они являются произведениями по крайней мере двух элементов: и . Согласно (1), число n может быть представлено одним из произведений - и может быть сопоставлено с одним из диофантовых уравнений , где т. к. . Тогда найдутся тройки чисел, , которые являются решениями хотя бы одного из диофантовых уравнений (4). Если числа вида являются простыми числами, то решений не будет, ибо из единственности представления простых чисел имеем , откуда следует, что элемент . Достаточность. Пусть одно из диофантовых уравнений (4) имеет решение, т. е. существует тройка чисел таких, что справедливо Тогда, с учетом (3), имеем: откуда n - составное число. Пример 2. Пусть - решение уравнения . Тогда С учетом (3) имеем или , и из (1) следует, что , т. е. - составное число. При решении диофантовых уравнений (4) нужно проверить числа вида и на простоту. При простых значениях n1 и n2 диофантовы уравнения и соответственно не имеют решений. Приведем примеры. I. Пусть , тогда число - простое, значит, уравнения и не имеют решений. Если , то число - простое и уравнения и не имеют решений. II. Пусть тогда число - составное и диофантовы уравнения имеют натуральные решения, т. е.: 1. Решения следуют из выражения (см. (1)). . Решения: и . 2. Решения следуют из выражения (см. (1)). , если y Î N стремится к решению (7589, 1, 1084). III. Пусть , тогда - составное число. , и имеют следующие решения: 3. , ; если y Î N стремится к решению (63, 2, 5). 4. , ; если y Î N стремится к решению (63, 5. 2). Следствие 1. Для любого простого не существует никакой тройки чисел которые были бы решением диофантовых уравнений и . Следствие 2. Для любого простого не существует никакой тройки чисел которые были бы решением диофантовых уравнений и . Рассмотрим взаимосвязь диофантовых уравнений (4) с простыми числами близнецами. Из определения чисел близнецов известно, что это числа и . Заметим, что разность чисел , и если при одном и том же значении параметра λ числа и простые, то числа вида будут простыми числами близнецами. Теорема 2. Для того чтобы lÎ N было параметром простых чисел близнецов, необходимо и достаточно, чтобы ни одно из диофантовых уравнений (4) при одном и том же l не имело решений. Необходимость. Пусть при одном и том же все диофантовы уравнения (4) не имеют решений. Тогда, по Теореме 1, из и следует, что - простое число, и из уравнений и - что - простое число. Так как разность чисел , то по определению простых чисел близнецов , где Tw - множество пар простых чисел близнецов. А это значит, что есть параметр простых чисел близнецов. Достаточность. Пусть есть параметр простых чисел близнецов, т. е. и - простые числа в силу определения чисел близнецов и . Значит, из Следствия 1, для простого числа следует, что диофантовы уравнения и не имеют решений, и, точно так же, из Следствия 2, не имеют решений диофантовы уравнения и для простого . Итак, ни одно из диофантовых уравнений (4) не имеет решений. Приписывая к серийным номерам записей знаки «+» или «-», в полях F1 и F2 можно сформировать таблицу знаков (табл. 2), и с помощью алгоритмов 3.1 и 3.2 натуральный ряд чисел разбивается на подмножества чисел согласно сочетаниям знаков «+» и «-». Таблица 2 Распределение параметров простых и составных чисел Θ в N Id F1 F2 1 + + 41 - - 81 - + 121 - + 161 - + 2 + + 42 + - 82 + - 122 - + 162 + - 3 + + 43 + - 83 - + 123 - + 163 + - 4 + - 44 + - 84 + - 124 + - 164 + - 5 + + 45 + + 85 + - 125 - + 165 - + 6 - + 46 - + 86 - - 126 - + 166 - + 7 + + 47 + + 87 + + 127 + - 167 - - 8 + - 48 - - 88 - - 128 - + 168 - + 9 + - 49 + - 89 - - 129 + - 169 + - 10 + + 50 - - 90 - + 130 - - 170 + + 11 - + 51 - + 91 - + 131 - + 171 - - 12 + + 52 + + 92 - - 132 - - 172 + + 13 - + 53 + - 93 +100 - 133 + - 173 - + 14 + - 54 - - 94 + - 134 - - 174 - - 15 + - 55 - + 95 + + 135 + + 175 + + 16 - + 56 - + 96 - + 136 - - 176 - - 17 + + 57 - - 97 - - 137 + + 177 + + 18 + + 58 + + 98 + - 138 + + 178 - + 19 + - 59 + - 99 + - 139 - - 179 - - 20 - - 60 + - 100 + + 140 + - 180 - - 21 - + 61 - + 101 - + 141 - - 181 - + 22 + - 62 - + 102 - + 142 - + 182 + + 23 + + 63 - + 103 + + 143 + + 183 + - 24 - - 64 + - 104 - - 144 + - 184 + - 25 + + 65 + - 105 - + 145 - - 185 + - 26 - + 66 - + 106 - - 146 - + 186 - + 27 - + 67 + - 107 + + 147 +150 + 187 - + 28 + - 68 - + 108 + - 148 + - 188 - + 29 + - 69 - - 109 + - 149 - - 189 - - 30 + + 70 + + 110 + + 150 - - 190 - - 31 - - 71 - - 111 - - 151 - + 191 - - 32 + + 72 + + 112 - + 152 + - 192 + + 33 + + 73 - + 113 + - 153 - + 193 - - 34 - - 74 + - 114 + - 154 - - 194 + - 35 - + 75 + - 115 - + 155 + - 195 - + 36 - - 76 - + 116 - - 156 - + 196 - - 37 - + 77 + + 117 + - 157 + - 197 + - 38 + + 78 + - 118 - + 158 + - 198 + - 39 + - 79 - - 119 - - 159 + - 199 + - 40 +50 + 80 + - 120 + - 160 - - 200 - + Очевидно, что эти подмножества чисел в натуральном ряду являются параметрами соответствующих подмножеств множества Θ: Множество составных чисел , где - множество значений параметров, представимо в виде ; (8) где - множество значений параметров , Составные числа близнецы , , (9) параметры PTwCN лежат на непустых пересечениях значений функций (4). Параметрами простых чисел (часть 1) (10) будут т. к. множество параметров не являются решениями диофантовых уравнений и и множество параметров не являются решениями диофантовых уравнений и . Параметрами простых чисел близнецов (часть 2) (11) будут . Тогда параметры всех простых чисел - . 4. Определение простых чисел по их порядковым номерам во множестве простых чисел . Формула нахождения π(x) в интервале от 1 до N Из таблицы распределения параметров простых и составных чисел Θ в Ν (табл. 2) нетрудно заметить, что между порядковыми номерами n простых чисел в табл. 3 и параметрами (id) простых чисел , приведенными в табл. 2, существуют зависимости. Таблица 3 Множество простых чисел P (р ≥ 5) 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541 547 557 563 569 571 577 587 593 599 601 607 613 617 619 631 641 643 647 653 659 661 673 677 683 691 701 709 719 727 733 739 743 751 757 761 769 773 787 797 809 811 821 823 827 829 839 853 857 859 863 877 881 883 887 907 911 919 929 937 941 947 953 967 971 977 983 991 997 . . . Пусть n - порядковый номер числа во множестве простых чисел P. Соответствующий параметр к простому числу в табл. 2 будет: , где . Подсчет знаков «+» ведётся по следующему принципу просмотра строк: (12) индекс поля , где заканчивается счет. Для достоверности полученное простое число можно сверить с числом, которое лежит над порядковым номером n в любой таблице простых чисел. Пример 3. Пусть - порядковый номер простого числа, тогда из табл. 2 имеем: 1. При 2. При Число простых чисел в интервале найдём на основе табл. 2 по типу где верхняя граница Подсчет знаков «+» в табл. 2 в полях F1 и F2 ведется аналогично (12). Пример 4. Определить количество простых чисел в интервале 1. 2. 5. Алгоритм распределения простых чисел p ≥ 5 в интервале 1 ÷ n Так как множество простых чисел то очевидно, что поиск простых чисел будет идти быстрее во множестве Θ, чем в натуральном ряду чисел N. Наиболее естественный способ удаления составных чисел множества Θ в интервале - это использование свойства замкнутости по умножению. Именно поэтому, умножая числа вида поэлементно на элементы множества Θ, где , можно легко и просто достичь поставленной цели. Вначале построчно вводятся натуральные числа в файл однако места чисел, делящихся на 2 и 3, заполняются символом «» - символом пустоты. Затем, на основе следующего алгоритма - RasPrm (рис. 1), удаляются все те элементы файла , которые являются поэлементными произведениями чисел на числа вида и, аналогично, для чисел вида где i = 1, 2, 3, … (см. ниже пример 5). Каждый последующий новый элемент θi возводится в квадрат, чтобы избежать повторения операции умножения, и затем поэлементно перемножается на последующие числа файла . Рис. 1. Окно программы, реализующей алгоритм RasPrm Процесс удаления продолжается до тех пор, пока . Если произведения чисел θi на последующие числа больше, чем n, то осуществляется переход к следующему элементу и повторяется вышеописанная процедура. Описанный метод отсеивания составных чисел из множества Θ с числами вида θi = 6·i ± 1 прост в использовании, алгоритм работает эффективнее и быстрее таких известных алгоритмов, как решето Эратосфена, решето Сунтарами и решето Аткина, поскольку во всех этих алгоритмах областью функционирования является множество натуральных чисел. Метод отсеивания составных чисел из множества Θ числами вида позволяет получить те же результаты, что и вышеперечисленные алгоритмы, но при существенно меньшем числе операций умножения. Пример 5. Найти все простые числа множества Θ в интервале C помощью чисел вида где сформируем элементы файла : 1. Удаление составных чисел файла , имеющих вид . Пусть тогда Возведём θ1 в квадрат как новый элемент: и если то из файла по прямому доступу достаётся номер записи и удаляется значение поля Затем θ1 поэлементно умножается на последующие числа файла и также удаляются числа с номерами записей . Так как осуществляется переход на следующий шаг, ибо т. е. - новый элемент, , и удаляется запись id = 121 из поля [N]. Когда вновь осуществляется переход на следующий шаг, т. к. т. е. - новый элемент, , и прекращается удаление при появлении чисел вида . 2. Удаление составных чисел файла , имеющих вид . Пусть θ1 - новый элемент; возводится в квадрат и удаляется аналогично, как и в предыдущих примерах. По прямому доступу достаются номера записей и удаляются числа. Так как то осуществляется переход на шаг . Тогда поскольку Конец алгоритма. 6. Простые числа близнецы Область определения простых чисел близнецов. Так как простые числа множества P есть объединение множеств просто простых чисел (PN) и простых чисел близнецов (Tw), то этот факт рассмотрим на уровне их параметров Обозначим и исследуем разности между функциями (5): и Заметим, что и при т. к. и Значит, между значениями функций (4) в строках (x, y) табл. 1 существуют интервальные последовательности чисел число элементов в которых соответственно равно: Κδj x, y = (δ1x,y: 2x - 1, δ2x,y: 2(y - x) - 1, δ3x,y: 2x - 1). Определение 2. Объединение σx,y = {σ1x,y}{σ2x,y}{σ3x,y} интервальных последовательностей в строке (x, y) назовём -последовательностью. Число элементов в -последовательности равно: Число элементов в приводимых далее последовательностях стремится к бесконечности: ({δ1x,y, δ2x,y}, {δ3x,y}), и потому стремятся к бесконечности интервальные последовательности ({σ1x,y}, {σ2x,y}, {σ3x,y}) Пусть множество тогда В силу (6) -последовательности являются упорядоченными и возрастающими. Итак, табл. 1 состоит из двух частей: из множеств параметров составных чисел и , которые являются параметрами составных чисел и, параллельно, - простых чисел вида (8)-(11)), и из явно невидимого множества Δ, которое содержит параметры простых чисел близнецов PTw ϵ Δ как 2-ю часть параметров всех простых чисел Pp. Так как часть параметров множества простых чисел и то элементами σx,y -последовательностей будут α - параметры простых чисел близнецов и β - параметры составных чисел множества Θ, т. е. (13) Пример 6. Найти обычную построчную σx,y-последовательность чисел в строке (1, 5), табл. 1. Значит, и число элементов Κσ1, 5 = 9. Заметим, что в построчных σ1,y-последовательностях начальная граница , а конечная . Рассмотрим представление элементов σx, y-последовательности (табл. 4): Таблица 4 Представление элементов σx,y-последовательности λ(x, y)/σ1,5 25 27 28 29 30 31 32 33 35 6xy - x - y - - 6-1 - 3-2 - - - 6xy + x + y - - 2-2 4-1 - - - - - 6xy - x + y - 1-4 - - - 6-1 - - 3-2 6xy + x - y - - - - - 1-6 - - 2-3 Числа 25, 30, 32, 33 не представимы ни одним из уравнений (4), т. е. являются параметрами простых чисел близнецов. Остальные числа представимы, например: 27 = 6xy - x + y = 6·1·4 - - 1 + 4, 29 = 6xy - x - y = 6·6·1 - 6 - 1, 28 = 6xy + x + y = 6·2·2 + 2 + 2, 35 = 6xy + x - y = = 6·2·3 + 2 - 3. С увеличением значений id (см. табл. 2) рост параметров простых чисел близнецов заметно уменьшается, поэтому с обычными σ1,y-последовательностями табл. 1 строгого доказательства проблемы о бесконечности простых чисел близнецов не найти. Очевидно, в σ1,y-последовательностях начальной границей будет 1, а конечную необходимо непрерывно расширять, связав со строкой y. Число элементов в построчных σ1,y-последовательностях находится по типу Kσ1,y = 2 (1 + y) - 3 = 2y - 1. Тогда конечная граница σ1,y-последовательности будет равна: M1, y = 7y + y(2y - 1) = 2y2 + 6y = 2y(y + 3). (13’) При таком характере роста параметров в последующих σ1,y-последовательностях будут присутствовать и параметры простых чисел близнецов предыдущих σ1,y-последовательностей. Алгоритм простых чисел близнецов: Α. Описание программы N. В поле файла T = PrmNub1 (id.[prm1].[prm2]) построчно вводятся натуральные числа от 1 до n. Β. Описание программы Tws. Для того чтобы извлечь параметры простых чисел близнецов из множества в интервале , нужно будет удалять из него параметры составных чисел, т. е. Определяется максимальный интервал для пробега переменных . Программа стартует с и параметры составных чисел удаляются с помощью значений функций (5) где Если то по прямому доступу из T достаются записи с номерами и удаляются числа в поле Если увеличиваем значение шага , и повторяем процедуру. Процесс удаления продолжается, пока не будет Непустые значения поля [N] говорят о наличии параметров чисел близнецов вида Если значит, алгоритмом были удалены числа как параметры составных чисел. Например, параметр не удаляется из файла, ибо и - простые числа. Если параметр то имеем и и тогда параметр удаляется как параметр составного числа. Значит, когда имеем простые числа и значения полей и в паре образуют множество простых чисел близнецов: Пример 7. Пусть тогда интервал параметров чисел близнецов Из табл. 1 выпишем параметры составных чисел имеем: Теорема 3. В последующих σ1,y-последовательностях всегда существуют параметры простых чисел близнецов, отличные от параметров простых чисел близнецов предыдущих σ1,y-последовательностей. Пусть M1,y - число элементов в σ1,y-последовательности, определенное типом (13’). Обозначим в σ1, y-последовательностях число параметров составных чисел как KPCN1, y и число параметров простых чисел близнецов как KPTW1, y, тогда число KPTW1, y = M1, y - KPCN1, y в силу (13). Если KPCN1,y < M1,y, то очевидно, что σx,y-последовательность содержит параметры простых чисел близнецов. Так как в табл. 1 формируются параметры составных чисел множества Θ и в каждой ее строке по четыре KPCN1,y, то, чтобы сосчитать число параметров составных чисел KPCN1,y в σ1,y-последовательности, нужно найти по значениям M1,y, где у - номер строки в табл. 1. Так как в строке (1, y) функция f12(1, y) наибольшая в силу (6) и со значением то соответствующая строка y 1 / 7* M1,y. Тогда, в σ1,y-последовательности число параметров составных чисел равно KPCN1, y 4 / 7 * M1, y, откуда следует, что KPCN1, y < M1, y. Значит, σ1,y-последовательности всегда содержат параметры простых чисел близнецов, число которых равно KPTW1, y = M1, y - 4 / 7 * M1, y 3 / 7 * M1, y. Для того чтобы убедиться в достоверности распределения параметров простых чисел близнецов, рассмотрим несколько примеров. Так как каждой M1, y соответствует своя σ1,y-последовательность, то очевидно, что при удалении в строках (1, y) табл. 1 параметров составных чисел в ней, в силу (13), останутся параметры простых чисел близнецов: 1. тогда и пусть 2. тогда 3. Пусть *KPTW1, y - число параметров простых чисел близнецов в последующей σ1,y-последовательности. Тогда разность с числом параметров простых чисел близнецов в предыдущей σ1,y-последовательности *KPTW1, y - KPTW1, y = [3 / 7(*M1, y - M1, y)], что показывает число новых параметров простых чисел близнецов. Так как *M1, y - M1, y = 2(y + 1) * *((y + 1) + 3) - 2y (y + 3) = 4y + 8 и всегда > 7 при любом y ∈ N, то в последующих σ1, y-последовательностях всегда имеются параметры простых чисел близнецов, отличные от параметров простых чисел близнецов предыдущих σ1,y-последовательностей. Теорема 4. Множество простых чисел близнецов бесконечно. Функции (5) бесконечные и возрастающие, т. к. разности где и зависят от двух переменных. Тогда их значения могут быть и равными, хотя это не влияет на процесс роста параметров простых чисел близнецов, ибо в объединениях FN1,y-последователь ностей одинаковые элементы отсеиваются, а сами элементы занимают свои места в них, не нарушая рост параметров простых чисел близнецов Ch1, y = M1,y \ FN1,y. Параметры простых чисел близнецов в последовательностях A1, y = Ch1, y+1 \ Ch1, y всегда останутся различными, потому что элементы σ1,y-последовательностей упорядоченные и различные. Пусть процесс получения параметров простых чисел близнецов применим и к числам с номером A1, n. И пусть на шаге процесс получения параметров простых чисел близнецов разрывается, т. е. Но по Теореме 3 в последующих σ1,y-последовательностях всегда существуют параметры чисел близнецов, отличные от параметров чисел близнецов предыдущих σ1,y-последовательностей, что противоречит допущению. Значит, Таким образом, построено счетное множество последовательностей параметров простых чисел близнецов И т. к. счетное множество равномощно к N, то бесконечны и параметры, и сами простые числа близнецы. Таблица 5 Параметры простых чисел близнецов (PTw = Ch) от 1 до 6300 1, 2, 3, 5, 7, 10, 12, 17, 18, 23, 25, 30, 32, 33, 38, 40, 45, 47, 52, 58, 70, 72, 77, 87, 95, 100, 103, 107, 110, 135, 137, 138, 143, 147, 170, 172, 175, 177, 182, 192, 205, 213, 215, 217, 220, 238, 242, 247, 248, 268. 270, 278, 283, 287, 298, 312, 313, 322, 325, 333, 338, 347, 348, 352, 355, 357, 373, 378, 385, 390, 397, 425, 432, 443, 448, 452, 455, 465, 467, 495, 500, 520, 528, 542, 543, 550, 555, 560, 562, 565, 577, 578, 588, 590, 593, 597, 612, 628, 637, 642, 653, 655, 667, 670, 675, 682, 688, 693, 703, 705, 707, 710, 712, 723, 737, 747, 753, 758, 773, 775, 787, 798, 800, 822, 828, 835, 837, 850, 872, 880, 903, 907, 913, 917, 920, 940, 942, 943, 957, 975, 978, 980,1015, 1022,1033,1045, ... Рис. 2. Диаграмма роста количества простых чисел близнецов в интервале 1 - M1,y: CN - составных чисел фактических; Tw - простых чисел близнецов фактических; cn - составных чисел теоретических, tw - простых чисел близнецов теоретических 7. Составные числа близнецы Из табл. 1 легко заметить, что параметры составных чисел близнецов лежат на пересечениях значений функций (5). Рассмотрим несколько параметров составных чисел близнецов, лежащих на пересечениях значений функций (5): Тогда соответствующие им составные числа близнецы: TwCN36 = (215, 217), TwCN41 = (245, 247), TwCN54 = (323, 325), TwCN57 = (341, 343), TwCNn = {6n ± 1 / n ∈ PTwCN}. Алгоритм составных чисел близнецов: А. Описание программы N. Так же, как и в параграфе 6 A. В. Описание программы TwCN. Проверяются на простоту числа вида и где - номера записей в файле Τ. Если хоть одно из чисел θ1 или θ2 простое, то удаляется соответствующее значение поля . С. Описание программы Если то значения полей и в паре образуют множество. Теорема 5. Составные числа близнецы во множестве Θ бесконечны. Рассмотрим множества и , состоящие из объединений и пересечений параметров . 1. и пусть 2. 3. Пусть утверждение верно и с номером βn. Докажем, что вышеизложенный процесс получения параметров составных чисел близнецов не разрывается со следующим шагом Допустим, что процесс разрывается, т. е. тогда элементы откуда следует, что функции (5) ограниченные. Это приводит к противоречию, ибо ранее было доказано, что функции (5) бесконечные. Тогда из противоречия следует, что Таким образом, построено счетное множество последовательностей параметров составных чисел близнецов. Пусть B = , где Так как параметры составных чисел близнецов при формировании множеств и являются различными (в силу операции объединения), то различными будут и сами составные числа близнецы Так как счетное множество с различными элементами - бесконечное множество, то параметры составных чисел близнецов PTwCN бесконечны, а значит, бесконечны и сами числа (табл. 6). Теорема доказана. Таблица 6 Параметры составных чисел близнецов множества Θ от 1 до 2 500 20, 24, 31, 34, 36, 41, 48, 50, 54, 57, 69, 71, 79, 86, 88, 89, 92, 97, 104, 106, 111, 116, 119, 130, 132, 134, 136, 139, 141, 145, 149, 150, 154, 160, 167, 171, 174, 176, 179, 180, 189, 190, 191, 193, 196, 201, 207, 209, 211, 212, 219, 222, 223, 224, 225, 226, 231, 232, 234, 236, 244, 246, 251, 253, 256, 265, 272, 274, 275, 279, 280, 281, 284, 286, 288, 294, 295, 299, 301, 303, 306, 307, 309, 314, 316, 320, 321, 323, 324, 326, 327, 328, 337, 339, 341, 343, 345, 349, 351, 353, 354, 358, 361, 362, 364, 365, 366, 371, 372, 376, 377, 384, 386, 387, 388, 394, 401, 405, 409, 414, 415, 416, 418, ... 8. Тест Primality - проверка чисел вида 6k ± 1 на простоту Существуют 2 вида проверок (тестов) чисел на простоту: истинные и вероятностные. Одним из истинных является тест Люка - Лемера. Недостаток этого теста заключается в том, что его можно применять только к рядам определенного вида. Вычислительная сложность Ограничения имеет и тест Пепина, использующийся для проверки на простоту чисел Ферма. Тест Агравала - Каяла - Саксены (тест AKS) считается универсальным, полиномиальным и детерминированным: если и , и выполняется то n либо простое число, либо степень простого числа. Вычислительная сложность теста если предположения верности гипотезы Артина верны, иначе При проверке на простоту натуральных чисел вида исследуются их параметры λ. Определяются типы множеств, к которым принадлежат параметры λ. Тогда с точностью устанавливается тип числа (составное или простое). Тест является независимым, универсальным, детерминированным и полиномиальным. Вычислительная сложность Пусть число n = 557 = 6 · 93 - 1. Тогда параметр , и, по методу определения простых чисел по их порядковым номерам, имеем: и, значит, . Однако этот же результат можно получить и по тесту Primality , т. к. параметр может быть представлен в виде функции и, значит, . Пусть n = 4 294 967 297 = 6 715 827 883 - 1. Тогда параметр λ = 715827883. Из-за ограниченного размера табл. 2 трудно определить методом вычисления простых чисел по их порядковым номерам соответствующий знак, поэтому воспользуемся тестом Primality При значениях х = 107, у = 116 736 параметр т. е. значит, по (8) число составное и n = 641 · 6700417. Пусть число n = 197297 = 6 32883 - - 1. Тогда параметр , т. е. не представим ни одной из функций (5), значит, Примеры с использованием больших чисел: n = 18 446744073709551617 = = 6 · 3074457345618258603 - 1 → λ = 3074457345618258603 при т. е. по (8) является составным: Пусть число тогда параметр не представим ни одной из функций (5), т. е. по (11) является параметром простых чисел близнецов, поэтому . Пусть число тогда параметр , т. е. , следовательно, по (10) число . Число тогда параметр по тесту Primality найдём соответствующую функцию (5). При числовых значениях параметр т. е. значит, по (8), число составное: Ниже приводится исходный текст использованной программы: Private Sub Primality_Click() Dim i, m, m1, m2, m3, m4, t1, t2 As String ora 1 = Time() ora 2 = "" t1 = 0 t2 = 0 m = sl4 m3 = dln(m, 6, ss) If IsNull(m) Or m = "" Or m = " " Or m = 0 Then Π4 = " Вводите число или сделайте клик над числом " Else ππ = 6 * m - 1, πχ = 6 * m + 1, pol6 = sl4 πχ 1 = "FN - : 6xy - x + y :" πχ 2 ="FN + : 6xy - x - y : " πχ 3 = "FN - : 6xy + x - y :" πχ 4 = "FN + : 6xy + x + y : " For i = 1 To m3 m1 = slg(m, i, ss) m2 = vich(umn(i, 6, ss), 1, ss) If OST(m1, m2, ss) = 0 Then t1 = i t2 = dln(m1, m2, ss) m4 = vich(vich(umn(umn(t1, t2, ss), 6, ss), t1, ss), t2, ss) If m = m4 Then πχ 2 = πχ 2 & " x= " & t1 & " y= " & t2 Else End If m1 = vich(m, i, ss) m2 = slg(umn(i, 6, ss), 1, ss) If OST(m1, m2, ss) = 0 Then t1 = i t2 = dln(m1, m2, ss) m4 = slg(slg(umn(umn(t1, t2, ss), 6, ss), t1, ss), t2, ss) If m = m4 Then πχ 4 = πχ 4 & " x= " & t1 & " y= " & t2 Else End If m1 = slg(m, i, ss) m2 = slg(umn(i, 6, ss), 1, ss) If OST(m1, m2, ss) = 0 Then t1 = i t2 = dln(m1, m2, ss) m4 = slg(vich(umn(umn(t1, t÷2, ss), 6, ss), t1, ss), t2, ss) If m = m4 Then πχ 1 = πχ 1 & " x = " & t1 & " y = " & t2 Else End If m1 = vich(m, i, ss) m2 = vich(umn(i, 6, ss), 1, ss) If OST(m1, m2, ss) = 0 Then t1 = i t2 = dln(m1, m2, ss) m4 = vich(slg(umn(umn(t1, t2, ss), 6, ss), t1, ss), t2, ss) If m = m4 Then πχ 3 = πχ 3 & " x = " & t1 & " y = " & t2 End If // slg(m, i, ss) - сложение больших чисел vich(m, i, ss) - вычитание больших чисел Next I umn(πχ1, πχ2, ss) - умножение больших чисел dln(m1, m2, ss) - деление больших чисел ora 2 = Time() OST(m1, m2, ss) - остаток при делении больших чисел End If End Sub Заключение Комплексное исследование проблемы нахождения и распределения простых и составных чисел, простых чисел близнецов и составных чисел близнецов, включающее теоретическое исследование, его программное обеспечение и численный анализ, позволило получить следующие результаты: - предложен новый алгоритм нахождения и распределения простых чисел; - приведено вычисление точного числа простых чисел в интервале ; - предложен способ получения простых чисел по их порядковым номерам во множестве простых чисел ; - предложен алгоритм проверки на простоту чисел вида ; - получен метод распределения параметров простых и составных чисел; - доказано, что любое составное может быть представлено одним из произведений , где x и y являются решениями одного из четырех диофантовых уравнений ; - приведены алгоритмы нахождения простых чисел близнецов и составных чисел близнецов, даны варианты доказательств их бесконечного количества.
Список литературы

1. Прахар К. Распределение простых чисел. М.: Мир, 1967. 511 с.

2. Крэндалл Р., Померанс К. Простые числа. Криптографические и вычислительные аспекты. М.: УРСС: Книжный дом «Либроком», 2011. 664 с.

3. Гельфанд А. О., Линник Ю. В. Элементарные методы в аналитической теории чисел. М.: Физматгиз, 1962. 131 с.

4. Чермидов С. И. О факторизации натуральных чисел // Диалоги о науке. 2011. № 2. С. 68-70.


Войти или Создать
* Забыли пароль?