2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки





Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Абсолютно простые числа
Сообщение24.08.2006, 18:03 
Заслуженный участник
Аватара пользователя


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

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

 Профиль  
                  
 
 
Сообщение24.08.2006, 19:49 
Заслуженный участник


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

 Профиль  
                  
 
 
Сообщение24.08.2006, 20:17 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 
Сообщение24.08.2006, 20:43 
Заслуженный участник


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

 Профиль  
                  
 
 
Сообщение24.08.2006, 20:47 


21/03/06
1545
Москва
Артамонов Ю.Н. писал(а):
Можно доказать и что кроме перечисленных в цитате, других абсолютно простых (исключая одни единицы) нет.

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

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


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

 Профиль  
                  
 
 
Сообщение24.08.2006, 21:17 
Заслуженный участник
Аватара пользователя


07/03/06
1716
Москва
Руст писал(а):
Я говорил легко доказать, что не более двух различных цифр встречается у такого числа. Пусть имеется три различных цифр у такого числа. Для чисел с количеством цифр не больше трёх других решений нет, а следовательно доказано. Поэтому, можно считать, что количество цифр не менее 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. Система счисления здесь не причем, а вопрос о бесконечности простых чисел из одних единиц - открыт.

 Профиль  
                  
 
 
Сообщение24.08.2006, 21:45 


21/03/06
1545
Москва
Цитата:
Для е2е4. Система счисления здесь не причем, а вопрос о бесконечности простых чисел из одних единиц - открыт.

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

 Профиль  
                  
 
 
Сообщение24.08.2006, 21:53 
Заслуженный участник


09/02/06
4328
Москва
e2e4 писал(а):
Цитата:
Для е2е4. Система счисления здесь не причем, а вопрос о бесконечности простых чисел из одних единиц - открыт.

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

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

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

 Профиль  
                  
 
 
Сообщение24.08.2006, 22:13 
Заслуженный участник


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

 Профиль  
                  
 
 
Сообщение24.08.2006, 22:36 
Заслуженный участник
Аватара пользователя


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

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

 Профиль  
                  
 
 
Сообщение24.08.2006, 23:10 
Заслуженный участник


09/02/06
4328
Москва
Число 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.

 Профиль  
                  
 
 
Сообщение25.08.2006, 00:44 
Заслуженный участник
Аватара пользователя


07/03/06
1716
Москва
Ваши рассуждения понятны, кроме подсчета вариантов (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.

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

 Профиль  
                  
 
 
Сообщение25.08.2006, 07:30 
Заслуженный участник


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

 Профиль  
                  
 
 
Сообщение25.08.2006, 10:12 
Заслуженный участник
Аватара пользователя


07/03/06
1716
Москва
Цитата:
Допустим, число цифр не меньше 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 первообразный корень.

 Профиль  
                  
 
 
Сообщение25.08.2006, 15:40 
Заслуженный участник


09/02/06
4328
Москва
Уже после 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}.$
Так, что кроме указанных не должен существовать абсолютно простых чисел, кроме вида состоящегося из одних единиц. Поэтому введение понятия "абсолютно-простое" число неоправданно, так как за исключением очень малого количества совпадает с классом простых чисел из одних единиц. Таких, по вероятностным соображениям бесконечно много.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 21 ]  На страницу 1, 2  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group