Абсолютно простые числа

[juna]

В отпуске читал книжку Серпинского "Что мы знаем и чего не знаем о простых числах".
стр. 28

Цитата:

Найдены простые числа, которые остаются простыми при каждой перестановке их цифр. Среди двухзначных таковыми являются числа: 13 и 31, 17 и 71, 37 и 73, 79 и 97, среди трехзначных - числа 113, 131, 311; 199, 919, 991; 337, 373, 733. Мы не знаем других таких чисел и не знаем, конечно ли их число. Х.Е. Рихерт доказал, что для $3<n<60^{175}$ нет таких чисел, имеющих $n$ цифр, кроме простых чисел, все цифры которых суть единицы.

Возможно книга довольно древняя и вопрос этот уже давно решен в математике.
Итак, абсолютно простым числом называется простое число, если при любой перестановке его цифр снова получается простое число.
Предлагаю участникам форума доказать, что абсолютно простое число может состоять не более чем из двух различных цифр.

[Руст]

Все цифры абсолютно простого числа или 1 или 3 или 7 или 9. Это легко доказать, сделав некоторый перебор, рассматривая деление на числа 7 и 11.
На самом деле, можно доказать и то, что начиная с некоторого n, n-значные абсолютно простые числа это простые числа из одних единиц.

[juna]

Можно доказать и что кроме перечисленных в цитате, других абсолютно простых (исключая одни единицы) нет. Требуется доказать более мягкое - абсолютно простое число может состоять не более чем из двух различных цифр.

[Руст]

Я говорил легко доказать, что не более двух различных цифр встречается у такого числа. Пусть имеется три различных цифр у такого числа. Для чисел с количеством цифр не больше трёх других решений нет, а следовательно доказано. Поэтому, можно считать, что количество цифр не менее 4. Если все четыре цифры встречаются, рассматривая 24 числа 1379,1397,1739,1793,1937,1973,... по модулю 7 найдём, что все остатки встречаются, а следовательно абсолютно простое число не может иметь четыре различных цифры. Пусть имеет три различные цифры a,b,c и цифру a по крайней мере два. Рассматривая аналогично 12 различных окончаний aabc, aacb,abac,abca,... по модулю 7, убеждаемся, что все остатки по модулю 7 присутствуют.
Рассматривая числа имеющие не менее 7 цифр (опять по модулю 7) получаем, что если абсолютно простое число имеет две различные цифры, то количество одной из цифр равно 1. Рассматривая по модулю других простых чисел можно доказать, что если количество цифр больше некоторого числа, то и этот вариант исключён, т.е. число состоит из одних единиц.

[e2e4]

Артамонов Ю.Н. писал(а):

Можно доказать и что кроме перечисленных в цитате, других абсолютно простых (исключая одни единицы) нет.

Если Руст прав, что

Цитата:

На самом деле, можно доказать и то, что начиная с некоторого n, n-значные абсолютно простые числа это простые числа из одних единиц.

а мне кажется, что он говорит это небезосновательно, и это n<60^175, то все абсолютно простые числа перечислены вами же. И действительно, получается верным, что

Цитата:

абсолютно простое число может состоять не более чем из двух различных цифр

Другое дело - зачем это нужно? Удивительных фактов по перестановки цифр в десятичном(да и в любом другом) представлении числа можно подметить множество. Но они, в случае простых чисел, во всяком случае, не проливают, насколько мне известно, свет на основные вопросы, связанные с ними(простыми числами). Все это - всего-лишь дело системы счисления и закономерностей, присущей ей одной.

[juna]

Руст писал(а):

Я говорил легко доказать, что не более двух различных цифр встречается у такого числа. Пусть имеется три различных цифр у такого числа. Для чисел с количеством цифр не больше трёх других решений нет, а следовательно доказано. Поэтому, можно считать, что количество цифр не менее 4. Если все четыре цифры встречаются, рассматривая 24 числа 1379,1397,1739,1793,1937,1973,... по модулю 7 найдём, что все остатки встречаются, а следовательно абсолютно простое число не может иметь четыре различных цифры. Пусть имеет три различные цифры a,b,c и цифру a по крайней мере два. Рассматривая аналогично 12 различных окончаний aabc, aacb,abac,abca,... по модулю 7, убеждаемся, что все остатки по модулю 7 присутствуют.
Рассматривая числа имеющие не менее 7 цифр (опять по модулю 7) получаем, что если абсолютно простое число имеет две различные цифры, то количество одной из цифр равно 1. Рассматривая по модулю других простых чисел можно доказать, что если количество цифр больше некоторого числа, то и этот вариант исключён, т.е. число состоит из одних единиц.

В целом Ваша идея аналогична моей. Я доказывал поэтапно:
1. абсолютно простое число может состоять не более чем из трех различных цифр (используя сравнение по модулю 7)
2. Не существует абсолютно простого числа, составленного из трех различных цифр и трех и более одинаковых (используя сравнение по модулю 7, 13)
3. Не существует абсолютно простого числа, состоящего из трех различных цифр семи разрядов и более (очевидное следствие)
4. Абсолютно простое число может состоять не более чем из двух различных цифр.
Для е2е4. Система счисления здесь не причем, а вопрос о бесконечности простых чисел из одних единиц - открыт.

[e2e4]

Цитата:

Для е2е4. Система счисления здесь не причем, а вопрос о бесконечности простых чисел из одних единиц - открыт.

Система счисления здесь именно что причем. Возьмите, навскидку, ваше число 17(71), переведите в любую систему счисления с другим основанием и попробуйте найти какую-нибудь закономерность (уверен, что что-нибудь да получится). Что это нам дает??

[Руст]

e2e4 писал(а):

Цитата:

Для е2е4. Система счисления здесь не причем, а вопрос о бесконечности простых чисел из одних единиц - открыт.

Система счисления здесь именно что причем. Возьмите, навскидку, ваше число 17(71), переведите в любую систему счисления с другим основанием и попробуйте найти какую-нибудь закономерность (уверен, что что-нибудь да получится). Что это нам дает??

Вопрос о бесконечности простых чисел из единиц чуть более интересен, хотя почему - фиг знает, то ли интуиция подсказывает, то ли читал где-то о чем-то интересном на эту тему.

Суть проблемы не зависит от системы исчисления. При любом основании системы исчисления q абсолютно простые числа имеющие n>6 цифр имеют цифры одни 1 или одну цифру a и n-1 цифр b. Если число цифр больше 17, то такое число имеет только цифры 1.

[Руст]

Здесь с числами 7 и 17 немного напутал, это числа для 10-ичной системы. К тому же в десятичной системе рассматривая по модулю 7 и 17 получается только, что абсолютно простое число имеющее не менее 17 цифр или состоит из одних 1 или количество цифр делится на 7*17 и одна цифра а, остальные b.
Для q -ичной системы исчисления надо рассмотреть по модулю таких простых чисел p, что минимальным периодом m, т.е минимальное натуральное число m удовлетворяющее $q^m=1(mod \ p)$ была равна р-1 (т.е. q образующая по модулю р). И число 7 надо заменить на первое такое простое, число 17 на второе.

[juna]

Цитата:

...в десятичной системе рассматривая по модулю 7 и 17 получается только, что абсолютно простое число имеющее не менее 17 цифр или состоит из одних 1 или количество цифр делится на 7*17 и одна цифра а, остальные b.

Поясните, пожалуйста, эти результаты.

[Руст]

Число 10 является образующим для простых чисел 7,17,19,23,29,47,59,61,97,109,113,131,149,167,179,181,193,...
Допустим, число цифр не меньше 7. Тогда рассматривая окончания из пяти цифр получаем, что если каждой цифры не меньше одного получаем, что одно из чисел делится на 7. Поэтому, абсолютно простое число имеющее n>4 цифр или состоит из одних единиц или одну цифру а, остальные b. Тогда такое число есть $x=(a-b)*10^k+b\frac{10^n-1}{9}$. В дальнейшем рассмотрим только простые р, для которых 10 является образующей. Когда к пробегает от нуля до р-2 остаток первого слагаемого при делении на р пробегает все ненулевые остатки по модулю р, так как второе число не делится на р если n не делится на р, то одно из перестановок будет делится на р. Таким образом, проверяя 7 значные и 14 значные всего (7+14)*4*3 вариантов с двумя различными цифрами приходим, что если число имеет две различные цифры, то одно из них а, а остальные b, причём количество цифр числа делится на все простые р<=n, для которых 10 является образующим. Т.е. если количество цифр не меньше 17, то n делится на 7 и 17, а следовательно и на 19,23,29,47,59,61,97,109,113, а следовательно на очень большое число. На самом деле, я могу доказать, что не существует абсолютно простого числа кроме состоящего из одних единиц, если количество цифр больше 14.

[juna]

Ваши рассуждения понятны, кроме подсчета вариантов (7+14)*4*3?
Результат, что количество цифр $n$ абсолютно простого числа должно делиться на все простые $p$, для которых 10 - первообразный корень и $p<n$ - интересен, тем более, что на вырожденный случай из одних единиц это возможно тоже распространяется, точнее количество единиц должно быть простым числом из указанной последовательности 7,17,19,23,29,47,59,61,97,109,113,131,149,167,179,181,193...

Цитата:

На самом деле, я могу доказать, что не существует абсолютно простого числа кроме состоящего из одних единиц, если количество цифр больше 14.

Было бы интересно увидеть это доказательство.

[Руст]

Я ошибся. На самом деле для делимости на р числа из одинаковых цифр, необходимо и достаточно, чтобы количество цифр делилось на р-1. Соответственно уточнение. Если количество цифр больше 12, то их должно быть как минимум 18 и делящимся на 6. Но тут появляется делимость на 17. Т.е. количество цифр должна делиться на НОК(6,16)=48. Но пока дойдем до 48 появиться делимость на 22,28,46, т.е. количество цифр должна делится на 12144. Но пока проверим до этого, появиться делимость на НОК(p-1|по всем p, для которых 10 образующая) и потолок увеличится до небесных высот.
Соответственно суть доказательства отсутствия абсолютно простых чисел с количеством цифр больше 12 сводится к доказательству бесконечности числа таких простых чисел и к некоторой проверке.

[juna]

Цитата:

Допустим, число цифр не меньше 7. Тогда рассматривая окончания из пяти цифр получаем, что если каждой цифры не меньше одного получаем, что одно из чисел делится на 7. Поэтому, абсолютно простое число имеющее n>4 цифр или состоит из одних единиц или одну цифру а, остальные b.

В это пришлось поверить.
Далее слагаемое $(a-b)*10^k$ - перемещает цифру $a$ по разрядам для разных $k$ и дает все ненулевые остатки от деления на $p=7,17...$, $p<n$. Поэтому необходимо рассматривать только случаи, когда второе слагаемое делится на $p$. Отсюда следует, что $b=1,3,9$. Далее из малой теоремы Ферма следует, что если НОД(h,p)=1, то $h^{p-1}-1=0(mod{p})$. Поскольку НОД(10, р)=1, то должно быть $n=m(p-1)$, т.е. количество цифр числа $b\frac{10^n-1}{9}$ должно делиться на $p-1$

Цитата:

Если количество цифр больше 12, то их должно быть как минимум 18 и делящимся на 6. Но тут появляется делимость на 17. Т.е. количество цифр должна делиться на НОК(6,16)=48. Но пока дойдем до 48 появиться делимость на 22,28,46, т.е. количество цифр должна делится на 12144. Но пока проверим до этого, появиться делимость на НОК(p-1|по всем p, для которых 10 образующая) и потолок увеличится до небесных высот.

Отсюда следует, что конкретного абсолютно простого числа из двух различных цифр больше 12 разрядов указать никогда не удастся, т.к. его количество цифр должно делиться на бесконечное множество чисел. Нужно только проверить, что каждый раз новое НОК перекрывает новое простое, для которого 10 первообразный корень.

[Руст]

Уже после 131 этот НОК превышает два миллиарда. Для статистики прогнал по всем постым меньше 65536. Из 6542 (включая 2 и 5) простых из этого интервала 10 является образующим для 2475 простых. После этого НОК поднялся до космических высот: $2^{11}*3^7*5^6*7^3*11^3*13^3*17^2*19^2*23^2*29^3*...=2,28*10^{2688}.$
Так, что кроме указанных не должен существовать абсолютно простых чисел, кроме вида состоящегося из одних единиц. Поэтому введение понятия "абсолютно-простое" число неоправданно, так как за исключением очень малого количества совпадает с классом простых чисел из одних единиц. Таких, по вероятностным соображениям бесконечно много.