среда, 5 августа 2015 г.

Волшебство составных чисел Мерсенна

Числами Мерсенна \(M_n\) называются числа вида \(2^n-1\), где \(n\) - натуральное число. 

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

Но сегодня мы займемся исследованием вопроса, относящегося к свойствам составных чисел Мерсенна.

А именно, правда ли, что для любого натурального \(n\) число \(M_{3628800 \cdot n}\) делится на 5643118635?


Ответ на этот вопрос можно легко получить, используя следующую теорему:

Теорема. Пусть \(n\) - некоторое натуральное число и \(d\) - любой из делителей числа мерсенна \(M_n\). Тогда для любого натурального \(m\) число \(M_{n \cdot m}\) также делится на \(d\).

Доказательство построим по индукции.  В самом деле, для \(m=1\) утверждение очевидно. Предполагая, что оно верно для некоторого m, рассмотрим цепочку тождеств

\(M_{n \cdot (m+1)} = (M_{n \cdot m}+1) \cdot (M_n +1) -1 = (d*q_1+1)(d*q_2+1)-1 = \)
\(=d*(d*q_1*q_2 + q_1 + q_2)\),

из которой следует, что \(d\) является также делителем числа \(M_{n \cdot (m+1)}\).

Из доказанной теоремы следует:

Следствие 1. Пусть \(D(n,1)\) - множество делителей числа \(M_n\), и \(D(n,m)\) - множество делителей числа \(M_{n \cdot m}\), где  \(m\) - произвольное натуральное число. Тогда \(D(n,1) \subseteq D(n,m)\).

Доказательство очевидно. 

Покажем теперь, что если \(n = d_1 \cdot d_2 \cdot ... \cdot d_q\), то для любого \(i \in \{1,...,q\}\) число \(M_n\) делится  на \(M_{d_i}\).

Действительно, для любого \(d_i\) верно \(n = d_i*Q\). Но тогда

\(M_{d_i \cdot Q} = (M_{d_i}+1)^Q-1 = \)
\(= M_{d_i}*((M_{d_i}+1)^{Q-1} + (M_{d_i}+1)^{Q-2} + ... + 1)\), 

и утверждение доказано.

Таким образом, имеет место 

Следствие 2. Если  \(n = d_1 \cdot d_2 \cdot ... \cdot d_q\) то для любого натурального \(m\) \( (D(d_1,1) \cup D(d_2,1) \cup … \cup D(d_q,1)) \subseteq D(n,m)\).

Имеют место следующие утверждения:

\(M_2 \equiv 0 \pmod {3} \);

\(M_3 \equiv 0 \pmod {7} \);

\(M_4 \equiv 0 \pmod {5} \);

\(M_5 \equiv 0 \pmod {31} \);

\(M_7 \equiv 0 \pmod {127} \);

\(M_8 \equiv 0 \pmod {17} \);

\(M_9 \equiv 0 \pmod {73} \);

\(M_{10} \equiv 0 \pmod {11} \).


В силу доказанного выше, для любого натурального \(n\) \(\{3,7,5,31,127,17,73,11\} \subseteq D(10!, n)\).

Другими словами, \(M_{3628800 \cdot n} \equiv 0 \pmod{5643118635}\), что и требовалось доказать.

среда, 4 марта 2015 г.

Таблица цепочек повторяющихся чисел в последовательности K(n)

Проверив первые 10 миллионов элементов последовательности \(K(n)\) (OEIS A003418) я составил таблицу цепочек повторяющихся чисел (см. запись о повторах и скачках).

Вычисления велись при помощи простого скрипта на Python и отняли около 2004 минут процессорного времени.

Как легко увидеть в таблице, цепочек четной длины значительно больше, чем цепочек с нечетной длиной. Однако, как показал Marcin B. из Вроцлава (см. обсуждение в Linkedin) существует множество цепочек нечетной длины. Более того, среди чисел вида \(2^n\)

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

C(1) = K(1)
C(2) = K(5)
C(3) = K(13)
C(4) = K(19)
C(5) = K(32)
C(6) = K(53)
C(7) = K(1024)
C(8) = K(89)
C(9) = K(512)
C(10) = K(139)
C(12) = K(199)
C(14) = K(293)
C(15) = K(65521)
C(16) = K(1831)
C(17) = K(8192)
C(18) = K(1069)
C(20) = K(887)
C(21) = K(524288)
C(22) = K(1129)
C(24) = K(4177)
C(26) = K(2477)
C(27) = K(16384)
C(28) = K(2971)
C(29) = K(131072)
C(30) = K(1331)
C(32) = K(5591)
C(34) = K(8467)
C(36) = K(9551)
C(38) = K(30593)
C(40) = K(19333)
C(42) = K(16141)
C(44) = K(15683)
C(46) = K(81463)
C(48) = K(28229)
C(50) = K(31907)
C(52) = K(19609)
C(54) = K(35617)
C(56) = K(82073)
C(58) = K(44293)
C(60) = K(43331)
C(62) = K(34061)
C(64) = K(89689)
C(66) = K(162143)
C(68) = K(134513)
C(70) = K(173359)
C(72) = K(31397)
C(74) = K(404597)
C(76) = K(212701)
C(78) = K(188029)
C(80) = K(542603)
C(82) = K(265621)
C(84) = K(461717)
C(86) = K(155921)
C(88) = K(544279)
C(90) = K(404851)
C(92) = K(927869)
C(94) = K(1100977)
C(96) = K(360653)
C(98) = K(604073)
C(100) = K(396733)
C(102) = K(1444309)
C(104) = K(1388483)
C(106) = K(1098847)
C(108) = K(2238823)
C(110) = K(1468277)
C(112) = K(370261)
C(114) = K(492113)
C(116) = K(5845193)
C(118) = K(1349533)
C(120) = K(1895359)
C(122) = K(3117299)
C(124) = K(6752623)
C(126) = K(1671781)
C(128) = K(3851459)
C(130) = K(5518687)
C(132) = K(1357201)
C(134) = K(6958667)
C(136) = K(6371401)
C(138) = K(3826019)
C(140) = K(7621259)
C(146) = K(6034247)
C(148) = K(2010733)
C(152) = K(8421251)
C(154) = K(4652353)

UPD.: Дэвид Рэдклифф (David Radcliffe) из США проверил 10 миллиардов чисел тоже простым, но намного более эффективным (хотя и не позволяющим получить дополнительную информацию о \(K(n)\)) способом, его результаты доступны по адресу: http://nbviewer.ipython.org/github/Radcliffe/iPythonNotebooks/blob/master/PrimePowerGaps.ipynb