Полный репенд прайм

В теории чисел, в полном расцвете сил reptend, полный расцвет рефрена, правильный штрих или длинный штрихе в базовом б нечетного простое числа р такой, что фактор Ферма

${\ displaystyle q_ {p} (b) = {\ frac {b ^ {p-1} -1} {p}}}$

(где p не делит b) дает циклическое число. Таким образом, цифровое расширение в базовом б повторяет цифры соответствующего циклического числа бесконечно, как и у с вращением цифры для любого а между 1 и р - 1. Циклическим число, соответствующее простым р будет обладать р - 1 цифр тогда и только тогда, когда p - простое число с полным повторением. То есть мультипликативный порядок ord p b = p - 1, что эквивалентно тому, что b является первообразным корнем по модулю p. ${\ displaystyle 1 / p}$${\ displaystyle a / p}$

Термин «длинное простое число» использовался Джоном Конвеем и Ричардом Гаем в их Книге чисел. Как ни странно, в OEIS Слоана эти простые числа называются «циклическими числами».

• 1 База 10
• 2 Паттерны появления простых чисел с полным повторением
• 3 Двоичные простые числа с полным повторением
• 4 п -го уровня reptend простое
• 5 простых чисел с полным повторением в различных базах
• 6 См. Также
• 7 ссылки

База 10 может быть принята, если база не указана, и в этом случае расширение числа называется повторяющимся десятичным числом. В базе 10, если простое число с полным повторением заканчивается цифрой 1, то каждая цифра 0, 1,..., 9 появляется в повторении такое же количество раз, что и каждая другая цифра. (Для таких простых чисел с основанием 10 см. OEIS :  A073761. Фактически, в базе b, если полное повторное простое число заканчивается цифрой 1, то каждая цифра 0, 1,..., b −1 появляется в повторяющемся такое же количество раз, как каждый другой цифрой, но нет такой простой существует тогда, когда б = 12, так как каждый полный reptend штрихом в базе 12 оканчивается на цифру 5 или 7 в одной и той же базе. в общем случае, нет такой простой, не существует, когда б является конгруэнтно с 0 или 1 по модулю 4.

Значения p меньше 1000, для которых эта формула дает циклические числа в десятичной системе, следующие:

7, 17, 19, 23, 29, 47, 59, 61, 97, 109, 113, 131, 149, 167, 179, 181, 193, 223, 229, 233, 257, 263, 269, 313, 337, 367, 379, 383, 389, 419, 433, 461, 487, 491, 499, 503, 509, 541, 571, 577, 593, 619, 647, 659, 701, 709, 727, 743, 811, 821, 823, 857, 863, 887, 937, 941, 953, 971, 977, 983,... (последовательность A001913 в OEIS )

Например, случай b = 10, p = 7 дает циклическое число 142857 ; таким образом, 7 - простое число с полным повторением. Кроме того, 1, деленная на 7, записанная в базе 10, дает 0,142857 142857 142857 142857...

Не все значения p дадут циклическое число с использованием этой формулы; например, p = 13 дает 076923 076923. Эти неудачные случаи всегда будут содержать повторение цифр (возможно, нескольких) в течение p - 1 цифр.

Известный образец этой последовательности исходит из теории алгебраических чисел, в частности, эта последовательность представляет собой набор простых чисел p, таких, что 10 является примитивным корнем по модулю p. Гипотеза Артина о первообразных корнях состоит в том, что эта последовательность содержит 37,395..% простых чисел.

Расширенная модульная арифметика может показать, что любое простое из следующих форм:

1. 40 к + 1
2. 40 к + 3
3. 40 к + 9
4. 40 к + 13
5. 40 к + 27
6. 40 к + 31
7. 40 к + 37
8. 40 к + 39

Никогда не может быть полным повторением простого числа с основанием 10. Первые простые числа этих форм с их периодами:

Однако исследования показывают, что две трети простых чисел вида 40 k  +  n, где n  ∈ {7, 11, 17, 19, 21, 23, 29, 33}, являются простыми числами с полным повторением. Для некоторых последовательностей преобладание простых чисел с полным повторением намного больше. Например, 285 из 295 простых чисел формы 120 k  + 23 ниже 100000 являются простыми числами с полным повторением, причем 20903 является первым, которое не является полным повторением.

В базе 2 простые числа с полным повторением: (менее 1000)

3, 5, 11, 13, 19, 29, 37, 53, 59, 61, 67, 83, 101, 107, 131, 139, 149, 163, 173, 179, 181, 197, 211, 227, 269, 293, 317, 347, 349, 373, 379, 389, 419, 421, 443, 461, 467, 491, 509, 523, 541, 547, 557, 563, 587, 613, 619, 653, 659, 661, 677, 701, 709, 757, 773, 787, 797, 821, 827, 829, 853, 859, 877, 883, 907, 941, 947,... (последовательность A001122 в OEIS )

Для этих простых чисел 2 является первообразным корнем по модулю p, поэтому 2 ⁿ по модулю p может быть любым натуральным числом от 1 до p - 1.

${\ Displaystyle а (я) = 2 ^ {я} ~ {\ bmod {p}} ~ {\ bmod {2}}}$

Эти последовательности периода p - 1 имеют функцию автокорреляции, которая имеет отрицательный пик -1 для сдвига. Случайность этих последовательностей была проверена жесткими тестами. ${\ Displaystyle (п-1) / 2}$

Все они имеют форму 8 k + 3 или 8 k + 5, потому что, если p = 8 k + 1 или 8 k + 7, то 2 является квадратичным вычетом по модулю p, поэтому p делится, а период по основанию 2 должны делиться и не могут быть p - 1, поэтому они не являются полностью повторяющимися простыми числами с основанием 2. ${\ Displaystyle 2 ^ {(п-1) / 2} -1}$${\ displaystyle 1 / p}$${\ Displaystyle (п-1) / 2}$

Кроме того, все безопасные простые числа, конгруэнтные 3 (модификация 8), являются простыми числами с полным повторением в основании 2. Например, 3, 11, 59, 83, 107, 179, 227, 347, 467, 563, 587, 1019, 1187, 1283, 1307, 1523, 1619, 1907 и др. (Менее 2000)

Двоичные последовательности простых чисел с полным повторением (также называемые десятичными последовательностями максимальной длины) нашли применение в криптографии и кодировании с исправлением ошибок. В этих приложениях обычно используются повторяющиеся десятичные дроби с основанием 2, что приводит к двоичным последовательностям. Максимальная длина двоичной последовательности для (когда 2 является примитивным корнем из p) определяется как: ${\ displaystyle 1 / p}$

Ниже приведен список периодов (в двоичном формате) простых чисел, конгруэнтных 1 или 7 (модификация 8): (менее 1000)

Ни один из них не является бинарным простым числом с полным повторением.

Двоичный период n- го простого числа равен

2, 4, 3, 10, 12, 8, 18, 11, 28, 5, 36, 20, 14, 23, 52, 58, 60, 66, 35, 9, 39, 82, 11, 48, 100, 51, 106, 36, 28, 7, 130, 68, 138, 148, 15, 52, 162, 83, 172, 178, 180, 95, 96, 196, 99, 210, 37, 226, 76, 29, 119, 24, 50, 16, 131, 268, 135, 92, 70, 94, 292, 102, 155, 156, 316, 30, 21, 346, 348, 88, 179, 183, 372, 378, 191, 388, 44,... (эта последовательность начинается с n = 2 или простого числа = 3) (последовательность A014664 в OEIS )

Уровень двоичного периода n- го простого числа равен

1, 1, 2, 1, 1, 2, 1, 2, 1, 6, 1, 2, 3, 2, 1, 1, 1, 1, 2, 8, 2, 1, 8, 2, 1, 2, 1, 3, 4, 18, 1, 2, 1, 1, 10, 3, 1, 2, 1, 1, 1, 2, 2, 1, 2, 1, 6, 1, 3, 8, 2, 10, 5, 16, 2, 1, 2, 3, 4, 3, 1, 3, 2, 2, 1, 11, 16, 1, 1, 4, 2, 2, 1, 1, 2, 1, 9, 2, 2, 1, 1, 10, 6, 6, 1, 2, 6, 1, 2, 1, 2, 2, 1, 3, 2, 1, 2, 1, 1,... (последовательность A001917 в OEIS )

Однако исследования показывают, что три четверти простых чисел формы 8 k + n, где n ∈ {3, 5} - простые числа с полным повторением в основании 2 (например, есть 87 простых чисел меньше 1000, конгруэнтных 3 или 5 (mod 8), из них 67 полноценных по базе 2, итого 77%). Для некоторых последовательностей преобладание простых чисел с полным повторением намного больше. Например, 1078 из 1206 простых чисел формы 24 k +5 ниже 100000 являются простыми числами с полным повторением по основанию 2, причем 1013 является первым, которое не полностью повторяется по основанию 2.

П -го уровня reptend главным является простым р, имеющим п разных циклов в разложении ( к представляет собой целое число, 1 ≤ K ≤ р -1). В базе 10 наименьшее число повторений n-го уровня равно ${\ displaystyle {\ frac {k} {p}}}$

7, 3, 103, 53, 11, 79, 211, 41, 73, 281, 353, 37, 2393, 449, 3061, 1889, 137, 2467, 16189, 641, 3109, 4973, 11087, 1321, 101, 7151, 7669, 757, 38629, 1231, 49663, 12289, 859, 239, 27581, 9613, 18131, 13757, 33931, 9161, 118901, 6763, 18233, 1409, 88741, 4003, 5171, 19489, 86143, 23201,... (последовательность A054471 в OEIS )

В базе 2 наименьшее число повторений n-го уровня равно

3, 7, 43, 113, 251, 31, 1163, 73, 397, 151, 331, 1753, 4421, 631, 3061, 257, 1429, 127, 6043, 3121, 29611, 1321, 18539, 601, 15451, 14327, 2971, 2857, 72269, 3391, 683, 2593, 17029, 2687, 42701, 11161, 13099, 1103, 71293, 13121, 17467, 2143, 83077, 25609, 5581, 5153, 26227, 2113, 51941, 2351,... (последовательность A101208 в OEIS )

Артин также предположил:

• Существует бесконечно много простых чисел с полным повторением во всех основаниях, кроме квадратов.
• Полностью повторяющиеся простые числа во всех основаниях, кроме совершенных степеней и чисел, бесквадратная часть которых конгруэнтна 1 по модулю 4, составляют 37,395...% всех простых чисел. (См. OEIS :  A085397 )

Наименьшие простые числа с полным повторением в базе n:

2, 3, 2, 0, 2, 11, 2, 3, 2, 7, 2, 5, 2, 3, 2, 0, 2, 5, 2, 3, 2, 5, 2, 7, 2, 3, 2, 5, 2, 11, 2, 3, 2, 19, 2, 0, 2, 3, 2, 7, 2, 5, 2, 3, 2, 11, 2, 5, 2, 3, 2, 5, 2, 7, 2, 3, 2, 5, 2, 19, 2, 3, 2, 0, 2, 7, 2, 3, 2, 19, 2, 5, 2, 3, 2, 13, 2, 5, 2, 3, 2, 5, 2, 11, 2, 3, 2, 5, 2, 11, 2, 3, 2, 7, 2, 7, 2, 3, 2, 0,... (последовательность A056619 в OEIS )

• Повторяющаяся десятичная дробь

• Вайсштейн, Эрик В. «Константа Артина». MathWorld.
• Вайсштейн, Эрик В. "Полный Reptend Prime". MathWorld.
• Conway, JH и Гай, Р.К.. Книга чисел. Нью-Йорк: Springer-Verlag, 1996.
• Фрэнсис, Ричард Л.; «Математические стога сена: новый взгляд на числа повторного объединения»; в журнале College Mathematics Journal, Vol. 19, № 3. (май 1988 г.), стр. 240–246.