Перестановочное простое число , также известное как анаграмматическое простое число , — это простое число , которое в данной базе может менять позиции своих цифр посредством любой перестановки и при этом оставаться простым числом. HE Richert , который, как предполагается, первым изучал эти простые числа, назвал их перестановочными простыми числами, [1] но позже их также стали называть абсолютными простыми числами . [2]
В системе счисления с основанием 2 только репьюниты могут быть перестановочными простыми числами, потому что любой 0, переставленный на место единиц, дает четное число. Следовательно, перестановочные простые числа в системе счисления с основанием 2 являются простыми числами Мерсенна . Можно смело сделать обобщение, что для любой позиционной системы счисления перестановочные простые числа с более чем одной цифрой могут иметь только цифры, взаимно простые с основанием системы счисления. Однозначные простые числа, то есть любое простое число ниже основания, всегда тривиально перестановочны.
В десятичной системе счисления известны все перестановочные простые числа, содержащие менее 49 081 цифр.
Где R n := — это репьюнит, число, состоящее только из n единиц (в десятичной системе счисления ). Любое репьюнитное простое число является перестановочным простым числом с приведенным выше определением, но некоторые определения требуют по крайней мере двух различных цифр. [3]
Из вышеперечисленного существует 16 уникальных наборов перестановок с наименьшими элементами
Все перестановочные простые числа из двух или более цифр состоят из цифр 1, 3, 7, 9, поскольку ни одно простое число, кроме 2, не является четным, и ни одно простое число, кроме 5, не делится на 5. Доказано [4] , что не существует перестановочного простого числа, содержащего три различные из четырех цифр 1, 3, 7, 9, а также что не существует перестановочного простого числа, составленного из двух или более цифр каждой из двух цифр, выбранных из 1, 3, 7, 9.
Не существует n -значного перестановочного простого числа для 3 < n < 6·10 175 , которое не является репьюнитом. [1] Предполагается , что не существует нерепьюнитных перестановочных простых чисел, кроме восемнадцати, перечисленных выше. Их можно разбить на семь наборов перестановок:
В системе счисления с основанием 12 известны наименьшие элементы уникальных наборов перестановок перестановочных простых чисел, содержащих менее 9739 цифр (с использованием перевернутых двойки и тройки для десяти и одиннадцати соответственно).
Не существует n -значного перестановочного простого числа в 12-ричной системе счисления для 4 < n < 12 144 , которое не является репьюнитом. Предполагается, что не существует нерепьюнитных перестановочных простых чисел в 12-ричной системе счисления, кроме перечисленных выше.
В системах счисления с основанием 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 9 в системах счисления до 20 являются: 139 11 , 36A 11 , 247 13 , 78A 13 , 29E 19 (М. Фиорентини, 2015).)
Пусть P(b, n, x, y) — перестановочное простое число в системе счисления b , а p — простое число, такое что n ≥ p . Если b — примитивный корень числа p , а p не делит x или | x - y |, то n кратно p - 1. (Поскольку b является примитивным корнем mod p и p не делит | x − y |, то числа p xxxx ... xxxy , xxxx ... xxyx , xxxx ... xyxx , ..., xxxx ... xyxx ... xxxx (только цифра b p −2 равна y , все остальные равны x ), xxxx ... yxxx ... xxxx (только цифра b p −1 равна y , все остальные равны x ), xxxx ... xxxx ( цифра повторения с n x s) mod p все различны. То есть одно равно 0, другое равно 1, третье равно 2, ..., третье равно p − 1. Таким образом, поскольку все первые числа p − 1 являются простыми, последнее число (цифра повторения с n x s) должно делиться на p . Поскольку p не делит x , то p должен делить репьюнит на n единиц. Поскольку b является примитивным корнем mod p , мультипликативный порядок n mod 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 также является примитивным корнем mod 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, то x = 7, или n делится на 6 (единственно возможным n является 12). Если b = 12, то цифры, взаимно простые с 12, это {1, 5, 7, 11}. Поскольку 12 является примитивным корнем по модулю 5, то если n ≥ 5, то либо 5 делит x (в этом случае x = 5, так как x ∈ {1, 5, 7, 11}), либо | x − y | (в этом случае либо x = y = 1 (то есть простое число является репьюнитом), либо x = 1, y = 11, либо x = 11, y = 1, так как x , y ∈ {1, 5, 7, 11}.) или n кратно 5 − 1 = 4. Аналогично, поскольку 12 является примитивным корнем mod 7, поэтому если n ≥ 7, то либо 7 делит x (в этом случае x = 7, так как x ∈ {1, 5, 7, 11}), либо | x − y | (в этом случае x = y = 1, так как x , y ∈ {1, 5, 7, 11}. То есть простое число является репьюнитом), либо nкратно 7 − 1 = 6. Аналогично, поскольку 12 является примитивным корнем по модулю 17, то если n ≥ 17, то либо 17 делит x (это невозможно, так как x ∈ {1, 5, 7, 11}), либо | x − y | (в этом случае x = y = 1, так как x , y ∈ {1, 5, 7, 11}. То есть простое число является репьюнитом) или n кратно 17 − 1 = 16. Кроме того, 12 также является примитивным корнем mod 31, 41, 43, 53, 67, 101, 103, 113, 127, 137, 139, 149, 151, 163, 173, 197, ..., поэтому n ≥ 17 совершенно невозможно (так как для этого простого числа p , если n ≥ p , то n делится на p − 1), а если 7 ≤ n < 17, то x = 7 (в этом случае, так как 5 не делит x или x − y , поэтому n должно делиться на 4) или n делится на 6 (единственно возможным n является 12).
