среда, 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