Простые числа в разных системах исчисления.

[Apoxa]

Работая программистом, однажды переводил ряд чисел из одной системы исчисления в другую, и заметил интересную закономерность:

Если число является простым в одной системе исчисления, то число, записанное той же последовательностью цифр, в другой системе исчисления, весьма вероятно, окажется простым.
Приведу несколько примеров:
Простое число в десятичной системе - 11; в двоичной это 3 – тоже простое, будучи переведено в десятичную.
Взятое наугад простое в число 727 – если записать его в шестнадцатеричной системе 0x727 = 1831 - в десятисной также простое;
Простое в число десятичной системе 1011001:
При записи в двоичной это 89 – тоже простое,
При переводе его в восьмеричную: b131 – простое в десятичной.
При переводе его в шестнадцатеричную: 0x59 – простое в десятичной.
Теперь 0x89 = b211 в восьмеричной – простое в десятичной.
Немного путано, но надеюсь, понятно, что я имею в виду.

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

[bot]

Apoxa в сообщении #761004 писал(а):

Простое число в десятичной системе - 11; в двоичной это 3 – тоже простое

А в троичной - это четыре.

[venco]

Если учесть совпадение признаков делимости по цифрам на малые простые числа, то зависимость малоотличима от случайной.
Например, если оба основания чётные, то получившееся число точно не будет делиться на 2, т.е. случайную плотность простых ($1\over\ln x$) надо умножить на два. А при переводе из 16-ной системы в 10-ную надо ещё умножить на $3\over2$, т.к. получившееся число на 3 тоже не будет делиться. Ну и так далее.

[Aritaborian]

Исследовать так исследовать. Нужен систематический подход.
Возьмём первый миллион простых, запишем их в системе счисления с основанием $m$, потом сделаем вид, что на самом деле они записаны в системе счисления с основанием $n$, и проверим, сколько среди них простых.
Ясно, что $m<n$, и начинать нужно с $m=2$, $n=3$. Строчка кода (я использую Wolfram Mathematica)

With[{m = 2, n = 3, a = 10^6}, Count[Table[PrimeQ[FromDigits[IntegerDigits[Prime[i], m], n]], {i, 1, a}],True]/a // N]

нажатие Enter, и через несколько секунд мы видим, что в данном случае доля простых не превышает шести с половиной процентов.
Для $m=2$, $n=4$ — чуть более восьми процентов.
Для $m=3$, $n=4$ — пять с половиной процентов.
Для $m=2$, $n=10$ — чуть более шести процентов.
Для $m=4$, $n=8$ — десять процентов (почти что в точности, что интересно).
Дальше каждый может развлекаться самостоятельно, но полученные данные уже наводят на мысль, что зависимостью, по крайней мере, очевидной, здесь и не пахнет.
Вообще, такого рода «экспериментальная математика» — занятие чертовски интересное, особенно в наше время, когда всё числопережёвывание возлагается на плечи ЭВМ. Спасибо вам, Apoxa, за то, что подкинули забавную идею, позволившую мне немножко отвлечься и развлечься.

(Оффтоп)

И запомните, пожалуйста: системы счисления, а не «исчисления».

[galaxy]

На незначительных числах (первый миллион простых чисел с основанием от 3 до 31) проверил, что если набор цифр с некоторым основанием задает простое число, то обязательно найдется другое основание в котором этот же набор цифр тоже будет задавать простое число.

И наоборот, существую наборы цифр, которые в любом основании будут задавать составное число.

[Батороев]

По-видимому, здесь немаловажно, какие числа меньше (а также больше) на 1, чем основание. Например, при основании $m=4$, число $m-1=3$, следовательно, признак делимости на $3$ чисел, записанных в этой системе, будет таким же, что и в $10$-чной системе.

[INGELRII]

galaxy в сообщении #761136 писал(а):

И наоборот, существую наборы цифр, которые в любом основании будут задавать составное число.

Например, 22, 33, 444?

[galaxy]

INGELRII в сообщении #763775 писал(а):

Например, 22, 33, 444?

Да. А также элементарные примеры: 4, 50, 600.

[abzal]

Нашел вот такую закономерность:

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

[iifat]

Подозреваю, влияет приводимость многочленов. Если уж $n^2-1=(n-1)(n+1)$, то $99=9\times11$ в любой системе счисления с незначительными поправками. А если хоть в одной системе число простое, значит, соответствующий многочлен неприводим и вероятность быть простым как-то повышается.