Распределение чисел Мерсенна / Habr

Число Мерсенна — число вида М = 2^n — 1, где n — натуральное число. Названы в честь французского математика Марена Мерсенна, исследовавшего их свойства в ХVII веке.

Одно из главных свойств чисел Мерсенна: число М является простым, только если число n — простое (р). Обратное утверждение не работает, например М (11) = 2047 = 23×89.

Последовательность простых чисел Мерсенна (начальная): М(р) = 3 (2), 7 (3), 31 (5), 127 (7), 8191 (13), 131 071 (17), 524 287 (19), 2 147 483 647 (31), 2 305 843 009 213 693 951 (61).....

Данное свойство меня очень заинтересовало, а именно как числа Мерсенна распределяются на простые и составные? Почему при простых показателях р = 11, 23, 29, …, числа Мерсенна не простые?

Для поиска ответа, пришлось посмотреть на числа Мерсенна с другой стороны — со стороны информатики, как на числа обладающие — идентификатором последовательности чисел. Решил применить принципы и методы информатики в математике (аналогично информационной математике).

Тогда задача поиска распределения чисел Мерсенна, меняется на задачу поиска зависимости идентификаторов к распределению чисел на простые и составные, где n — идентификатор числа М(n) = 2^n — 1. И данная зависимость была обнаружена в ряду 2(а^2) — 1, где числа Мерсенна появляются при а = 2, 4, 8, 16… или при а = 2^b, где b — натуральное число.

Для наглядности нахождения закономерности распределения составных чисел в ряду 2(а^2) — 1, прошу рассмотреть таблицу, где указаны идентификаторы ряда или значение числа — а, значение числа ряда 2(а^2) — 1 которые обозначим как А(а) = 2(а^2) — 1, так же в таблице указаны делители составных чисел и соответственно простые (без делителей), дополнительно показаны числа Мерсенна.

а	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17
А(а) = 2(а^2) –1	1	7	17	31	49	71	97	127	161	199	241	287	337	391	449	511	577
Делители					7*7				7*23			7*41		17*23		7*73
Число Мерсенна		М(3)		М(5)				М(7)								М(9)

а	18	19	20	21	22	23	24	25	26	27	28	29	30	31	32
А(а) = 2(а^2) — 1	647	721	799	881	967	1057	1151	1249	1351	1457	1567	1681	1799	1921	2047
Делители		7*103	17*47			7*151			7*193	31*47		41*41	7*257	17*113	23*89
Число Мерсенна															М(11)

Если мы возьмем идентификатор (а) и прибавим к нему значения А(а), то мы получим значение идентификатора и соответствующее число ряда, которое будет делиться на А(а). Например, если взять А(а)=7(2), то А(7+2) = А(9) = 161 = 7*23. При этом свойства чисел, делящиеся на А(а), будет повторяться, если повторять увеличение на А(а). Например, А(7+7+2) = А(16) = 511 = 7*73, А(7+7+7+2) = А(23) = 1057 = 7*151, делятся на 7.

Аналогично проявляются свойства чисел ряда и идентификатора, если от значения А(а) вычитать значение (а) и повторять увеличение на А(а). Например, для А(а)=7(2), будут А(7–2) = А(5) = 49 = 7*7, А(7+7-2) = А(12) = 287 = 7*41, А(7+7+7-2) = А(19) = 721 = 7*103, которые делятся на 7.

Данную выборку можно обозначить как s = k*А(а) +а и s = k*А(а) ‑а, где s — идентификатор составного числа ряда А(a), k — число повторов значений ряда А(а).

К сожалению, не всё так просто, данная выборка составных чисел является явной, но есть еще и скрытая.

Все делители составных чисел ряда А(а), тоже определяют составные числа, делящиеся на данные делители. Например для не явного делителя 23 числа А(9) = 161 = 7*23, будут образовываться числа А(23–9) = А(14) = 391 = 27*23, А(23+23-9) = А(37) = 2737 = 7*17*23, аналогично А(23+9) = А(32) = 2047 = 23*89, которые делятся на 23.

Для удобства обозначения делителей предлагаю ввести уровни, где делители начального (нулевого) уровня будут числами ряда А(а) — явные делители, то есть. А(а) = 7(2), 17(3). Делители начального уровня, в свою очередь образуют делители (скрытые) первого уровня А₁{s₁}, где s₁ — идентификатор, в котором образуется делитель, А₁ — значение делителя, например А₁{s₁} = 41(12), где 41 - делитель который появился в А(12) = 287 = 7*41. В свою очередь делители первого уровня образуют делители второго уровня А₂{s₂}, где s₂ — идентификатор, в котором образуется делитель, А₂ — значение делителя, например А₂{s₂} = 89{32}, где 82 - делитель который появился в А(32) = 2047 = 23*89 и так далее

Теперь можно ввести математическое доказательство распределения простых и составных чисел в ряду А(а) = 2(а^2) — 1 с применением нового алгоритма (предлагаю назвать «решето Вдовина») выявления составных чисел с идентификатором s_n+1 = k_n*А_n ± s_n, где n — уровень делителя, s_n+1 — идентификатор составного числа образующийся от делителя n‑го уровня, s_n — идентификатор в котором образуется делитель, А_n — делитель n‑го уровня, k_n — количество повторов для каждого делителя (данные коэффициенты не связаны между уровнями, для каждого уровня и делителя они свои). По аналогии с решетом Эратосфена оставшиеся идентификаторы будут соответствовать простым числам.

Делители начального уровня будут определяться А(а), в свою очередь они определяют составные числа с идентификаторами s = k*А(а) +а и s = k*А(а) ‑а (для упрощения предлагаю рассмотреть в начале формулу s = k*А(а) +а). В свою очередь данные идентификаторы образуют делителей первого уровня s₁ = k*А(а) +а. Тогда формулу делителей первого уровня получим подставляя s₁ в формулу образования ряда А(s₁) = 2(s₁^2) — 1, тогда А(s₁) = 2[(k*А(а) +а)^2] — 1 = (2(а^2) — 1) [(2kа+1) ^2 — 2(k^2)] = А(а) А₁.

Получили формулу делителей первого уровня А₁ {s₁} = (2kа+1)^2 — 2(k^2) с идентификаторами s₁ = k*А(а) +а где они образуются.

В свою очередь делители первого уровня образовывают идентификаторы составных чисел как s₂ = k₁*А₁ ± s₁. Что также является идентификатором образования делителя второго уровня и подставляя его в формулу образования ряда (рассмотрим s₂ = k₁*А₁ + s₁), получим: А(s₂) = 2[(k₁*А₁ + s₁)^2] — 1 = А₁ (2(k₁^2) А₁ + 4 s₁ k₁ + А) = А₁ А₂.

Получили формулу делителей второго уровня А₂ {s₂} = 2(k₁^2) А₁ + 4 s₁ k₁ + А с образующими идентификаторами s₂ = k₁*А₁ + s₁, где А — делитель начального уровня образовавший делитель первого уровня А₁.

Продолжая применять делители для нахождения составных чисел и соответственно идентификаторы делителей последующих уровней, можно получить обобщённую формулу делителей А_n+1 {s_n+1} = 2(k_n^2) А_n + 4 s_n k_n + А_n-1 для идентификаторов s_n+1 = k_n*А_n + s_n (при n > 1).

Чтобы не нагружать статью математическими выкладками предоставляю формулу для делителя первого порядка А₁ {s₁} = (2kа-1)^2 — 2(k^2) при s₁ = k*А(а) ‑а. И обобщенную формулу делителей (при n > 1) А_n+1 {s_n+1} = 2(k_n^2) А_n — 4 s_n k_n + А_n-1 для идентификаторов s_n+1 = k_n*А_n — s_n.

Если объединить идентификаторы получим формулу решето Вдовина (алгоритма нахождения составных (простых) чисел в ряду А(а) = 2(а^2) — 1). Все составные числа данного ряда будут находиться идентификаторами s_n+1 = k_n*А_n ± s_n, с делителями первого уровня А₁ {s₁} = (2kа ± 1)^2 — 2(k^2), и последующими делителями А_n+1 {s_n+1} = 2(k_n^2) А_n + А_n-1 ± 4 s_n k_n

Мы обосновали математически распределение составных и соответственно простых чисел в ряду А(а) = 2(а^2) — 1 через решето Вдовина s_n+1 = k_n*А_n ± s_n. Теперь проверим данное распределение на числа Мерсенна. Напоминаю, что числа Мерсенна появляются в ряду А(а) при а = 2^b.

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

В приведенной ранее таблице наглядно видно, что М(3) = А(2) = 7, М(5) = А(4) = 31, М(7) = А(8) = 127 простые числа.

Составное М(9) = А(16) = А(2*7+2) = 511 = 7*23 — делиться на 7 и возникло от начального делителя А(2) = 7.

Последующее число М(11) = А(32) = А(23+9) = 2 047 = 23*89 возникло от делителя первого уровня А₁ {9} =23, который появился от составного числа А (9) = 161 = 7*23 = А (7+2) и соответственно от начального делителя А(2) = 7. Данное число Мерсенна наглядный пример как скрытые делители формируют составные числа Мерсенна с простыми значениями р, где М = 2^р — 1.

Последующее число М(13) = А (64) = 8 191 будет простым. Для наглядности предоставляю таблицу, где указано распределение около а = 64.

а	58	59	60	61	62	63	64	65	66	67	68	69	70
А(а) = 2(а^2) — 1	6727	6961	7199	7441	7687	7937	8191	8449	8711	8977	9247	9521	9799
Делители	73131		23*313	7*1063				71771	31*281	47*191	7*1321		41*239
Число Мерсенна							М(13)

Число М(15) = А (128) = 32 767 = 7*31*151, можно получить от двух начальных делителей А(2)=7 как А (18*7+2) = А (128) и делителя А(4) = 31 как А (4*31+4) = А (128). А также от делителя первого уровня А₁ {23} = 151 полученное как А (151–23) = А (128).

Число М(17) = А (256) = 131 071 простое, так же, как и М(19) = А (512) = 524 287. Для наглядности предоставляю таблицы, где указаны распределение около а = 256 и 512.

а	251	252	253	254	255	256	257	258	259
А(а) = 2(а^2) — 1	126 001	127 007	128 017	129 031	130 049	131 071	132 097	133 127	134 161
Делители		1731241	313*409	7*18433	47*2767		7113167	1741191
Число Мерсенна						М(17)

а	507	508	509	510	511	512	513	514	515
А(а) = 2(а^2) — 1	514 097	516 127	518 161	520 199	522 241	524 287	526 337	528 391	530 449
Делители	17*30241		779937	607*857	367*1423		7174423		23*23063
Число Мерсенна						М(19)

Число Мерсенна М(21) = А(1024) = 2 097 151 = 7*7*127*337 будет иметь четыре начальных делителя А(2)=7, А(5)=49, А(8)=127, А(13) = 337, как А(1024) = А(146*7+2) = А(21*49-5) = А(8*127+8) = А(3*337+13).

Ну и напоследок число М(23) = А (2048) = 8 388 607 = 47*178481 определяется делителем второго уровня А₂ {2048} =178 481 возникшего в данном составном числе М(23) и одним делителем первого уровня А₁ {20} =47 как А(44*47-20) = А(2048) полученного из составного числа А(20)=А(17+3)= 799 = 17*47 образованного от делителя А(3)=17.

Заключение:

1) Применяя методы информатики в математике, позволили нам дополнить подходы к поиску простых чисел.

2) Получили новый способ нахождения простых чисел в ряду А(а) = 2(а^2) — 1 через решето Вдовина.

3) Получили обоснованную зависимость распределения чисел Мерсенна на простые и составные.

Уважаемый читатель, у меня огромная просьба!

Рассмотрите и найдите зависимость распределения простых (составных) чисел Ферма в ряде А(а) = (а^2) + 1 через решето Вдовина (s_n+1 = k_n*А_n ± s_n).

Спасибо за интерес к теме!