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

воскресенье, 17 августа 2014 г.

Почему нельзя делить на ноль, даже если очень хочется?

Недавно на Хабре появилась удивительная статья «Папа, а почему на ноль делить нельзя?», которая собрала массу не менее удивительных комментариев. 

Детские вопросы обычно очень сложны ("Почему небо ночью темное?", "Почему яблоки падают на землю?") и у взрослых обычно не хватает времени, чтобы их доходчиво объяснить. 
Да и не всегда взрослые знают ответ на эти вопросы. 

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

График гиперболы в интервале [0,1,10],
полученный при помощи системы Maxima
Самые серьезные сомнения появляются, я думаю, после изучения рациональных чисел, когда для любого числа \(x\), кроме нуля, вводится понятие обратного числа \(1/x\), и графика гиперболы \(y(x) = 1/x\). 

Очевидно, что при делении 1 на очень маленькие числа появляются очень большие числа, и чем меньше мы берем \(x\), тем больше становится \(1/x\). Почему же мы не можем сказать, что \(1/x = \infty\) - есть некоторое число?

Алгебраическое возражение против этого состоит в следующем. Предположим, что \(\infty = 1/x\) является числом. Тогда на это число должны распространяться все правила, которые имеют место быть для обычных чисел. В частности, с одной стороны должно быть верно соотношение \(0\cdot\infty=1\) , а с другой стороны поскольку \(0 = 1-1\) должно быть выполнено \(0\cdot\infty = 1\cdot\infty - 1\cdot\infty = 0\). Таким образом, имеем \(1 = 0\), а из этого уже следует, что все числа равны между собой и равны нулю. В самом деле, поскольку для любого числа \(x\) верно \(1\cdot x = x\), то \(1\cdot x = 0 \cdot x = 0\). 

«Ну разве это не полная чушь?» — спросим себя, добравшись до этого места.

Разумеется, это полная чушь, если мы говорим об обычных числах. Но я недаром подчеркнул выше слово «правила». К ним мы вернемся чуть позже, после рассмотрения арифметического возражения против деления на ноль, и поможет нам в этом фасоль. 

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

Для этого берем чашу с фасолью, символизирующую натуральный ряд, и высыпаем из нее какое-то количество зерен на разлинованный лист бумаги: 




Тем самым, мы установили делимое на нашем бобовом калькуляторе.

Задача состоит в том, чтобы разложить эти зерна на пять рядов. Чтобы не запутаться отмечаем эти ряды, то есть, устанавливаем делитель



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


Алгоритм завершается, когда мы получаем некоторое прямоугольное число и (возможно) остаток: 



В данном примере осталось 2 зерна, а рядов по 5 зерен образовалось 18. Получается, что случайное число было \(18 \cdot 5 + 2 = 92\).

Ясно, что мы можем выполнить этот алгоритм для любого натурального делимого и любого натурального делителя, отличного от нуля; если же делитель равен 0, то этот алгоритм выполнить попросту невозможно. 

«Подождите!» — скажет внимательный читатель. — «В рассмотренном примере мы получили остаток 2, что с ним делать?»

Это, на самом деле, очень важное замечание. Вообще говоря, мы не можем делить фасолины, не испортив наш бобовый калькулятор — мало того, что разделить 2 фасолины на 5 одинаковых частей проблематично, даже если мы их раздробим подобающим образом, мы уже не сможем их собрать.


Поэтому достаточно долго люди старались обходиться без дробей. Например, в анонимной арабской рукописи XII века описана следующая задача: «разделить 100 фунтов между 11 человеками». Поскольку \(100=11 \cdot 9 + 1\), средневековый математик предлагает сначала раздать каждому по 9 фунтов, а затем обменять оставшийся фунт на яйца, которых, как оказывается по курсу обмена, получается ровно 91. Но \(91 = 11\cdot8 + 3\), поэтому арабский ученый предлагает раздать каждому по 8 яиц, а три оставшихся яйца отдать тому, кто производит раздел, или же обменять на соль к яйцам.


Говоря современным математическим языком, деление проводилось в полукольце натуральных чисел. Впрочем, с таким же успехом, используя красную и белую фасоль, мы могли бы определить деление с остатком и в кольце целых чисел  — в изложенном алгоритме появились бы дополнительные правила для выбора цветов используемых для вычислений зерен фасоли, но точно так же остались бы бессмысленными операции вида \(x/0\) и \(5/2\).

Очевидно, что для того, чтобы придать символу \(5/2\) конкретный смысл, нужно изменить правила игры, и перейти к полю рациональных дробей, пополнив множество целых чисел всевозможными выражениями \(m/n\), где \(m\) - целое, а  \(n\) - натуральное.

Важно заметить, что сделать это можно не единственным способом, однако в классической арифметике рассматривается такое пополнение, в котором символ \(1/n\) означает долю от деления 1 на \(n\), т. е. такое число, для которого верно выражение \(n \cdot 1/n =1\); при чем доли имеют смысл не при подсчете штучных предметов (например, зерен фасоли), а при измерении величин, которые предполагаются непрерывными (или хотя бы неограниченно делимыми) - длин отрезков, площадей фигур и т. д.

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

В самом деле, пусть требуется разделить рациональное число \(\alpha = {p}/{q}\) на \(\beta = {r}/{s}\). Это равносильно выполнению следующих действий:

\(\alpha:\beta = {p}/{q} : {r}/{s} = {p\cdot s}/{q\cdot r}\)

и задача при любых рациональных \(\alpha\) и \(\beta\) свелась к уже известной процедуре деления целых чисел. Это еще раз показывает, что деление на ноль не имеет никакого арифметического смысла.

«Получается, делить на ноль нельзя, даже если очень хочется?» — увы, ответ на этот вопрос положительный: мы не можем определить операцию деления на ноль исходя их естественных потребностей счета и измерений.  Правда, есть две лазейки.

Первая: вместо «обычных» чисел (т.е. кольца натуральных и поля рациональных, а также поля действительных чисел, о котором я, кстати, до сих пор не сказал ни слова и расскажу как-нибудь в другой раз) рассмотреть вырожденный случай — тривиальное кольцо \({0}\), и положить по определению \(0/0 = 0\). В этом случае, когда нам говорят: «Все числа равны между собой и равны нулю!» - мы можем сказать невозмутимым тоном: «Ну и что? Это всегда было так».

Вторая: отказаться от некоторых привычных правил умножения. В частности, от аксиомы \(0 \cdot x = 0\). Говорят, что это возможно (см. http://en.wikipedia.org/wiki/Wheel_theory). Разумеется, этот вариант гораздо интереснее первого, но и он представляет собой такое изменение правил игры, которое сразу выводит нас за рамки классической арифметики.

В заключение этой заметки, хочу привести список литературы для тех, кто заинтересовался числовыми системами: 

— И .В. Арнольд «Теоретическая арифметика», М, ОГИЗ 1938 — очень подробная и детальная книга, в которой можно найти описания классических числовых систем, включая кватернионы.
— Е. Г. Гонин «Теоретическая арифметика», М, 1959 — эта книга покороче и посовременнее, и тоже очень хороша, хотя не так подробна, как книга И.В. Арнольда.С. Феферман «Числовые системы» — классическая монография, местами достаточно сложная; в ней изложены некоторые частные вопросы, которых нет в двух других книгах по теоретической арифметике.

— А. А. Кириллов «Что такое число?» (1993) — небольшая брошюра, рассчитанная на подготовленного читателя.

— Е. Б. Дынкин, В. А. Успенский  «Математические беседы» — популярная книга, рассчитанная на школьников. Содержит массу информации и задач по такой «нестандартной» теме, как p-адические числа.

среда, 13 августа 2014 г.

Счеты и соробан

Эта заметка была опубликована в 02.03.2011 года в моем старом сумбурном блоге, который был ранее доступен по тому же адресу (blog.sandovin.name), а теперь отправлен в архив. Совершенно неожиданно, я обнаружил, что на нее есть ссылка в статье "Соробан" русской Википедии, причем ведет она на совсем другой текст. Исправляю это безобразие. 
Я уже писал в своем блоге о логарифмических линейках, теперь настало время поговорить о счетах. Давно ли вы считали на счетах? Есть ли у вас счеты дома? Можете ли вы подсказать, где можно купить счеты, и не детскую игрушку, а взрослый 20-разрядный конторский прибор?

Однажды мы пытались научить кролика вычислять числа Фибоначчи, но ничего из этого не вышло.

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


Но и там изящный счетный прибор с отполированными от частого и долгого употребления деревянными костяшками еще лет пять тому назад заменил калькулятор CITIZEN. И хотя последний перед вводом в действие был самым провинциальнейшим образом обвернут полиэтиленом, это не помешало ему превратиться вскоре в замызганный кусок пластмассы (такова судьба всех калькуляторов в продовольственных магазинах).

Японским счетам - соробану - повезло куда больше, чем русским.


Соробан не только не забыт в Японии, но и продолжает завоевывать популярность за ее пределами. И хотя в России соробанный счет является малоизвестным, любители соробана есть и у наc.

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


Не знаю, в чем здесь секрет: в большей ли технологичности соробана, как счетного устройства (хотя соробан, очевидно, еще более близок к древнему римскому абаку, чем русские счеты),  или же в том особо бережном отношении японцев к своему культурному наследию, которое заставляет их поднимать старинные храмы на вершины строящихся на том же месте небоскребов, а не взрывать, как это делалось в СССР.

Как бы то ни было, основанная около 90 лет назад японская компания Tomoe Soroban до сих пор продолжает производить и продавать счеты, некоторые из которых стоят более 600 долларов, то есть дороже чем многие смартфоны и планшеты.

Но владельцам iPhone повезло, поскольку для него существует прекрасный программный эмулятор:

Поговорим о логарифмических линейках

Эта заметка была опубликована в 01.10.2011 года в моем старом сумбурном блоге, который был ранее доступен по тому же адресу (blog.sandovin.name), а теперь отправлен в архив. По-хорошему, ее нужно полностью переписать; но в ближайшее время я до этого не доберусь, и в связи с этим, публикую в прежнем виде. 
Это уже случалось лет двадцать тому назад, но история повторяется, и вот - уже мои дети находят в одном из ящиков шкафа странный прибор, и начинают задавать вопросы, которые я сам задавал когда-то: "Папа, что это такое? Можно этой линейкой чертить?" 

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

-А ты умеешь на ней считать?

-Да, конечно. Смотри. Вот, допустим, я хочу умножить 23 на 78. Я ставлю визир на 23, двигаю бегунок, еще раз двигаю визир и читаю ответ: 1,7,9 и... кажется, 4. Бегунок двигали влево, значит, порядки складываем - ответ 1794! Но сегодня это искусство уже никому не нужно.

-А почему?

-Ну вы же сами знаете про цифровые калькуляторы. Кто будет сейчас возиться со счетными палочками?

И правда - кто? Найти сегодня логарифмическую линейку трудно, но цифровые вычислительные машины позволяют моделировать аналоговые, интернет велик, и кто ищет - тот всегда найдет. И мы очень быстро нашли "Derek's Virtual Slide Rule Gallery", виртуальный музей, все экспонаты которого вполне работоспособны.


среда, 6 августа 2014 г.

Хладнокровные и прыгающие числа

Беглый просмотр последовательности \(\{K(n) := [1,2,...,n]\}\) позволяет сказать, что цепочки повторов и скачков длины \(l\) (см. запись о повторах и скачках) встречаются в этой последовательности не в единственном экземпляре.

Более того, можно предполагать, что для любого \(l\in\mathbb{N}\) такие цепочки существуют и повторяются неограниченное множество раз. 

Исходя из этого предположения, я буду называть числа, с которых начинаются цепочки повторов длины \(l\) хладнокровными (это название им подходит, поскольку далее они сохраняют постоянство) и обозначать их как \(C(l,n)\), где \(n=1,2,3\dots\) - номер очередного числа в последовательности хладнокровных чисел; числа, с которых начинаются цепочки скачков длины \(l\)  я буду называть прыгающими (их можно было бы назвать "скачущими числами", но такой термин представляется мне вульгарным) и обозначать их как  \(J(l,n)\), где \(n=1,2,3\dots\) - номер очередного числа в последовательности прыгающих чисел.

Таким образом, приходим к следующим любопытным вопросам:

  • Действительно ли для любого \(l\ge1\) существуют хладнокровные и прыгающие числа? 
  • Каковы последовательности хладнокровных  \(C(l,n)\) и прыгающих  \(J(l,n)\) чисел?
  • Как часто встречаются хладнокровные и прыгающие числа?
  • Как соотносятся \(C(l,n)\) и \(J(l,n)\) при различных \(l\) и \(n\), т. е.  какой знак имеет выражение \((C(l,n)-J(l,n)\))?

Характер роста первых шести прыгающих чисел \(J(1,n)\) показывает следующая последовательность:  

\(J(1,1)=K(10)=2520\), 
\(J(1,2)=K(13)=360360\),
\(J(1,3)=K(18)=12252240\),
\(J(1,4)=K(22)=232792560\),
\(J(1,5)=K(24)=5354228880\),
\(J(1,6)=K(26)=26771144400\).

Повторы и скачки

Пусть \(K(n)\) — наименьшее из чисел, которые делятся на \(1,2,3,..., n\).

Выпишем несколько членов этой последовательности (больше можно увидеть в энциклопедии OEIS - см. последовательность A003418):

\(1, 2, 6, 12, 60, 60, 420, 840, 2520, 2520, 27720, 27720, 360360, 360360, 360360, 720720,...\).

Очевидно, что \(K(n)\) монотонно возрастает: при любом натуральном \(n\) верно неравенство \(K(n+1)\ge K(n)\). В тех точках, где неравенство строгое будем говорить, что \(K(n)\) делает скачок. 

Однако, в некоторых случаях возникают цепочки повторов длины \(l\): 

\(K(n-1)<K(n)=K(n+1)=K(n+2)=...=K(n+l-1)<K(n+l)\).

Обозначим через \(C(l)\) наименьшее из чисел \(K(n)\), с которых начинается цепочка повторов длины \(l\).

Ясно, что \(C(2) =60, C(3) = 360360\).

Спрашивается, каковы \(C(4), C(5), C(6),...\)?

Еще интереснее вопрос о цепочках скачков. 

Если \(J(l)\) — наименьшее из чисел \(K(n)\), с которого начинается цепочка скачков длины \(l\), то есть имеет место 

\(K(n-1)=K(n)<K(n+1)<K(n+2)<...<K(n+l-1)=K(n+l)\),

то каковы \(J(2), J(3), ...\)? 

Если, как это указано в OEIS, положить по определению \(K(0):=1\), то можно сказать, что \(J(5)=1\); также очевидно, что \(J(4)=60\).

И последний, самый интересный вопрос: что встречается чаще — цепочки повторов или цепочки скачков? 

вторник, 5 августа 2014 г.

Несколько простых тождеств с гармоническими числами

В качестве упражнения вывел несколько простых тождеств с гармоническими числами.

Не уверен, что они новы и сильно полезны; но с другой стороны и в полной их бесполезности уверенности нет.

Поэтому решил опубликовать их здесь.

Первое тождество совсем тривиально:

\((H_n)^3 \equiv \sum_{i=1}^n\sum_{j=1}^n\sum_{k=1}^n\frac{1}{ijk}\).

Остальные несколько сложнее, но тоже практически очевидны:

\(\sum_{i=1}^n\sum_{j=1}^{n-1}\sum_{k=j+1}^1\frac{1}{ijk}\equiv \frac{1}{2}H_n(H_n^2-\zeta_n(2))\);

\(\zeta_{n}(2) \equiv (H_{n})^2-\sum_{k=1}^{n-1}\frac{2H_k}{k+1}-1\);

\(H_{n^2} + 1 \equiv (H_n)^2 + \sum_{k=1}^{n-1}\left(H_{(k+1)^2-1} - \frac{2H_{k}}{k+1} - H_{k^2}\right)\),

где \(H_n := \sum_{k=1}^n\frac{1}{k}\) - \(n\)-ое гармоническое число, \(\zeta_{n}(2) := \sum_{k=1}^{n}\frac{1}{k^2}\).



вторник, 24 сентября 2013 г.

Загадка суммы цифр числовой последовательности

Одна из простых вычислительных задач привела меня к следующим вопросам.

Пусть \(s_{10}(n)\) - сумма цифр записи числа \(n\) в десятичной системе счисления, a \(ds2t(n) = s_{10}(2^{10^n})\).

Для \(n = 1,2,...,7\) я составил такую таблицу:

\(ds2t(1) = s_{10}(2^{10^1}) = 7\),
\(ds2t(2) = s_{10}(2^{10^2}) = 115\) ,
\(ds2t(3) = s_{10}(2^{10^3}) = 1366\),
\(ds2t(4) = s_{10}(2^{10^4}) = 13561 = 135\cdot10^2 + 61\),
\(ds2t(5) = s_{10}(2^{10^5}) = 135178 = 135\cdot10^3 + 178\),
\(ds2t(6) = s_{10}(2^{10^6}) = 1351546 = 135\cdot10^4 + 1546\),
\(ds2t(7) = s_{10}(2^{10^7}) = 13546438 = 135\cdot10^5 + 46438\),

далее, выяснилось, что и при \(n = 8\) для \(ds2t(n)\) сохраняется закон, который начал действовать с n = 4: \(ds2t(n) = 135\cdot10^{n-2} + r, r\ge0\).

А именно,

\(ds2t(8) = 135481777 = 135\cdot10^6 + 481777\)

это наводит на мысль, что тот же закон будет действовать и для \(n\ge9\).

Мне пока непонятно, как доказать или опровергнуть эту гипотезу, если только не пытаться найти опровержение посредством вычисления очередного \(ds2t(n)\).

В более широкой последовательности \(s_{10}(2^{n}),  n = 1, 2, 3, ... \) числа вида  \(135\cdot10^{k} + r\), вообще говоря, встречаются нечасто. 

Проверив 281686 показателей, я нашел, что только 816 из них приводит к появлению чисел вида \(135\cdot10^{k} + r\). Возникает вопрос: каков закон распределения этих чисел?

Далее представлена таблица из указанных выше 816 показателей \(2^n\).

четверг, 22 марта 2012 г.

Логические машины коллежского советника Корсакова



С.Н. Корсаков (1787-1853)

Говорит ли вам что-либо имя Семёна Николаевича Корсакова, чиновника Императорского МВД? Признаюсь, я сам никогда не слышал о Корсакове, пока не заинтересовался историей вычислительной техники.

Семён Николаевич изобрел целых пять видов вычислительных машин:
  • Гомеоскоп прямолинейный с неподвижными частями;
  • Гомеоскоп прямолинейный с подвижными частями;
  • Плоский гомеоскоп;
  • Идеоскоп;
  • Простой компаратор.

Схема одного из гомеоскопов Корсакова

Несмотря на это, изобретения и само имя коллежского советника С. Н. Корсакова было забыто более чем на 100 лет. Рецензия комиссии на прошение, представленное изобретателем в Императорскую Академию Наук, была следующей: «Г-н Корсаков потратил слишком много разума на то, чтобы научить других обходиться без разума». 

Увы, инновации в России во все времена внедрялись со скрипом и, как правило, лишь перед лицом серьезных вызовов, либо в результате тяжелых военных поражений. Родись Корсаков в другое время и в другой стране, судьба его изобретений могла бы быть иной. 

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

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

Иными словами, это более совершенный вариант машины №1.
3. Плоский гомеоскоп таким же образом мгновенно указывает соответствия, имеющиеся у сравниваемых между собой идей, число деталей которых может достигать десяти тысяч и даже больше. Число этих деталей можно довести до одного миллиона, используя градуированные стержни. 
Теперь становится понятно, почему академическая комиссия  «зарезала» проект Корсакова. Ставить задачу эффективной обработки значительных объемов данных, и тем более заявлять о возможности ее практического решения в первой половине XIX века было дерзостью не меньшей, чем заявление о возможности непротиворечивой геометрии, в которой не имеет места пятый постулат Евклида.

Последние две машины Корсакова также весьма интересны и функциональны:

4. Идеоскоп мгновенно выдаёт, исходя из специальной таблицы и заранее определённого предмета, следующие результаты:
1) все соответствия, которые есть у сравниваемых идей при их соприкосновении;
2) всё то, что находится в заданной идее, но отсутствует в той идее, с которой её сравнивают, в сей момент;
3) всё то, что отсутствует в заданной идее, но есть в той идее, с которой её сравнивают;
4) всё то, чего нет ни у одной, ни у другой идеи, но есть у других идей из той же таблицы.
Помимо этого мгновенного и всестороннего анализа большого числа идей, представленных в таблице в материальном виде, идеоскоп также способен определить непосредственно в момент сравнения степень относительной важности каждой из деталей; число сравниваемых идей во время проведения одной операции может легко достигать многих сотен, и каждая из этих идей может свободно содержать сто и более деталей. При этом устройство будет способно выдать в течение нескольких минут точный и полный результат всех этих столь разнообразных и сложных сравнений.
Если же потребуется, чтобы идеоскоп сам остановился именно на идее из таблицы, содержащей всю совокупность сравниваемых идей, или чтобы о подобном сходстве давал бы знать звон колокольчика, можно очень легко достичь подобных результатов с помощью крайне простого механизма, добавляемого к устройству. Идеоскоп, так же как и гомеоскопы (1 и 2), может быть легко сконструирован для работы с цилиндрическими таблицами, такими же, как те, что находят применение в органах и шарманках.
5. Простой компаратор - это устройство выдаёт те же четыре результата, что и идеоскоп, но оно способно работать только с двумя идеями, которые сравниваются между собой. Оно может содержать только несколько десятков деталей, но преимущество его состоит в том, что оно не имеет нужды в заранее заготовленной таблице.
Для своих логических машин Сёмен Николаевич использовал перфокарты. Идея их применения для кодирования и обработки данных для того времени была гениальной.

Но практический успех в этом направлении был достигнут только в 1890 г. в С.-А.С.Ш., когда имя Корсакова было уже крепко забыто. Американский же изобретатель стал одним из основателей старейшей из известных в мире IT компаний (угадайте ее название).

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

P.S. Прекрасный сайт, на котором можно найти подробную информацию о С.Н. Корсакове и его интеллектуальных машинах, находится здесь. Авторское описание машин взято из книги Корсаков С.Н. Начертание нового способа исследования при помощи машин, сравнивающих идеи / Пер. с франц. под ред. А.С. Михайлова. – М.: МИФИ, 2009, PDF-версия которой размещена на указанном сайте. Иллюстрации взяты из статьи о Корсакове, размещенной в русской Википедии.

UPD. 23.03.2012:  Как выяснилось, о Корсакове краткая заметка есть и на Хабрахабре.