Перестановочное простое число

A перестановочное простое число, также известное как анаграмматическое простое число, является простым числом, которое в данном основании может переключаются позиции цифр с помощью любой перестановки и остаются простым числом. Х. Э. Рихерт, который предположительно первым изучил эти простые числа, назвал их перестановочными простыми числами, но позже их также назвали абсолютными простыми числами .

В основание 10 все перестановочные простые числа с менее чем 49 081 цифрой известны

2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, 97, 113, 131, 199, 311, 337, 373, 733, 919, 991, R 19 (1111111111111111111), R 23, R 317, R 1031,... (последовательность A003459 в OEIS )

Из вышеперечисленного имеется 16 уникальных наборов перестановок с наименьшими элементами

2, 3, 5, 7, R 2, 13, 17, 37, 79, 113, 199, 337, R 19, R 23, R 317, R 1031,... (последовательность A258706 в OEIS )

Примечание R n= $10\; n\; -\; 1\; 9\; \{\backslash \; displaystyle\; \{\backslash \; tfrac\; \{10\; ^\; \{n\}\; -1\}\; \{9\}\}\}$является перегруппировкой, число, состоящее только из n единиц (в base 10 ). Любое простое число повторного объединения является перестановочным простым числом с указанным выше определением, но для некоторых определений требуется как минимум две различные цифры..

Все перестановочные простые числа двух или более ди gits состоят из цифр 1, 3, 7, 9, потому что ни одно простое число, кроме 2, не является четным, и никакое простое число, кроме 5, не делится на 5. Доказано, что не существует перестановочного простого числа, которое содержит три различных из четырех цифр. 1, 3, 7, 9, а также то, что не существует перестановочного простого числа, состоящего из двух или более каждой из двух цифр, выбранных из 1, 3, 7, 9.

Не существует n-значной перестановочной простое число для 3 < n < 6·10 which is not a repunit. It is выдвинуло гипотезу о том, что не существует неразделимых перестановочных простых чисел, кроме перечисленных выше.

В базе 2 только повторные единицы могут быть переставляемыми простыми числами, потому что любой 0, переставленный на единицу, дает четное число. Следовательно, перестановочные простые числа с основанием 2 - это простые числа Мерсенна. Можно безопасно сделать обобщение, что для любой позиционной системы счисления перестановочные простые числа с более чем одной цифрой могут иметь только цифры, которые взаимно просты с основанием система счисления. Однозначные числа, означающие любое простое число ниже системы счисления, всегда тривиально перестановочны.

В с основанием 12 известны наименьшие элементы уникальных наборов перестановок перестановочных простых чисел с менее чем 9739 цифрами (с использованием перевернутых двух и трех для десяти и одиннадцати, соответственно)

2, 3, 5, 7, Ɛ, R 2, 15, 57, 5Ɛ, R 3, 117, 11Ɛ, 555Ɛ, R 5, R 17, R 81, R 91, R 225, R 255, R 4 ᘔ 5,...

Нет n-значного перестановочного простого числа по основанию 12 для 4 < n < 12 which is not a repunit. It is conjectured that there are no non-repunit permutable primes in base 12 other than those listed above.

В основаниях 10 и 12 каждое перестановочное простое число является повторной единицей или почти повторной цифрой, т. Е. перестановка целого числа P (b, n, x, y) = xxxx... xxxy b (n цифр по основанию b), где x и y - цифры, взаимно простые с b. Кроме того, x и y также должны быть взаимно простыми (поскольку если существует простое число p делит и x, и y, то p также делит число), поэтому, если x = y, то x = y = 1. (Это неверно в все базы, но исключения редки и могут быть конечными в любой данной базе; единственными исключениями ниже 10 в базах до 20 являются: 139 11, 36A 11, 247 13, 78A 13, 29E 19 (M. Fiorentini, 2015).)

Пусть P (b, n, x, y) будет перестановочное простое число в базе b, и пусть p простое число такое, что n ≥ p. Если b является примитивным корнем числа p, и p не делит x или | x - y |, то n кратно p - 1. (Поскольку b является примитивным корнем по модулю p, а p не делит не делить | x - y |, числа p xxxx... xxxy, xxxx... xxyx, xxxx... xyxx,..., xxxx... xyxx... xxxx (только цифра b - y, остальные - все x), xxxx... yxxx... xxxx (только цифра b - y, все остальные - x), xxxx... xxxx (repdigit с n xs) mod p - все разные. То есть одно - 0, другое - 1, третье - 2,..., другое - p - 1. Таким образом, поскольку первые p - 1 числа являются простыми, последнее число (повторная цифра с n xs) должен делиться на p. Поскольку p не делит x, p должно делить повторное объединение на n 1. Поскольку b является примитивным корнем по модулю p, порядок мультипликативности n по модулю p равен p - 1. Таким образом, n должно делится на p - 1)

Таким образом, если b = 10, цифры, взаимно простые с 10, равны {1, 3, 7, 9}. Поскольку 10 является примитивным корнем по модулю 7, то если n ≥ 7, то либо 7 делит x (в данном случае x = 7, поскольку x ∈ {1, 3, 7, 9}), либо | x - y | (в данном случае x = y = 1, поскольку x, y ∈ {1, 3, 7, 9}. То есть простое число является повторным объединением) или n делится на 7 - 1 = 6. Аналогично, поскольку 10 является примитивным корнем по модулю 17, поэтому, если n ≥ 17, то либо 17 делит x (невозможно, поскольку x ∈ {1, 3, 7, 9}), либо | x - y | (в данном случае x = y = 1, поскольку x, y ∈ {1, 3, 7, 9}. То есть простое число является повторным объединением) или n делится на 17 - 1 = 16. Кроме того, 10 также является примитивным корнем по модулю 19, 23, 29, 47, 59, 61, 97, 109, 113, 131, 149, 167, 179, 181, 193,..., поэтому n ≥ 17 очень невозможно (так как для это простые числа p, если n ≥ p, то n делится на p - 1), и если 7 ≤ n < 17, then x = 7, or n is divisible by 6 (the only possible n is 12). If b = 12, the digits coprime to 12 are {1, 5, 7, 11}. Since 12 is a primitive root mod 5, so if n ≥ 5, then either 5 divides x (in this case, x = 5, since x ∈ {1, 5, 7, 11}) or |x − y| (in this case, either x = y = 1 (That is, the prime is a repunit) or x = 1, y = 11 or x = 11, y = 1, since x, y ∈ {1, 5, 7, 11}.) or n is a multiple of 5 − 1 = 4. Similarly, since 12 is a primitive root mod 7, so if n ≥ 7, then either 7 divides x (in this case, x = 7, since x ∈ {1, 5, 7, 11}) or |x − y| (in this case, x = y = 1, since x, y ∈ {1, 5, 7, 11}. That is, the prime is a repunit) or n is a multiple of 7 − 1 = 6. Similarly, since 12 is a primitive root mod 17, so if n ≥ 17, then either 17 divides x (not possible, since x ∈ {1, 5, 7, 11}) or |x − y| (in this case, x = y = 1, since x, y ∈ {1, 5, 7, 11}. That is, the prime is a repunit) or n is a multiple of 17 − 1 = 16. Besides, 12 is also a primitive root mod 31, 41, 43, 53, 67, 101, 103, 113, 127, 137, 139, 149, 151, 163, 173, 197,..., so n ≥ 17 is very impossible (since for this primes p, if n ≥ p, then n is divisible by p − 1), and if 7 ≤ n < 17, then x = 7 (in this case, since 5 does not divide x or x − y, so n must be divisible by 4) or n is divisible by 6 (the only possible n is 12).

Предполагаемые наибольшие непереставляемые перестановочные простые числа в базе n (записаны в базе 10, начинаются с n = 3, поскольку такое простое число не существует для n = 2)

7, 53, 3121, 211, 1999, 3803, 6469, 991, 161047, 19793, 16477, 24907, 683437, 3547, 67853, 80273, 94109, 72421, 148639, 182537, 228953, 9967, 358069, 17467, 99929, 21943, 369319, 26981, 23580569, 1048571, 1037657, 1012369, 1271117, 1367687,... (последовательность A317689 в OEIS )

1. ^ Richert, Hans-Egon (1951). «On permutable primtall». Norsk Matematiske Tiddskrift. 33 : 50–54. Zbl 0054.02305.
2. ^Бхаргава, TN; Дойл, PH (1974). «О существовании абсолютного простого числа s ". Математика. Mag. 47 : 233. Zbl 0293.10006.
3. ^Крис Колдуэлл, The Prime Glossary: ​​перестановочное число на Prime Pages.
4. ^A.W. Джонсон, "Абсолютные простые числа", Mathematics Magazine 50 (1977), 100–103.