Энциклопедия чисел
АрхивРешили не допустить ни одной опечатки. Держали десять корректур. И все равно на титульном листе стояло: "Британская энциклопудия".
И. Ильф. "Записные книжки"
В наше время очень трудно удивить кого-то новой энциклопедией: справочников (в том числе электронных) выпущено столько, что ни один человек уже не в состоянии собрать не то что полную коллекцию, но даже приличную библио- и дискографию. И все же я постараюсь рассказать о совершенно удивительной энциклопедии, доступной всем, однако известной лишь узкому кругу любителей. Но сначала несколько слов о ее авторе.
Нил Дж. А. Слоун (Neil J. A. Sloane) - известный математик, работает в AT&T Bell Laboratories. Его основные работы относятся к теории графов, геометрии выпуклых тел и комбинаторике. В 1995 году вышла книга Дж. Слоуна "Энциклопедия целочисленных последовательностей", о которой я и собираюсь рассказать.
Книга представляет собой хорошо систематизированную подборку самых разнообразных числовых последовательностей, которые встречаются в математике, computer science и смежных науках. О каждой последовательности можно узнать много занимательных фактов, найти ссылки на литературу. Но самое интересное, что все эти факты и комментарии не только существуют в изданной за рубежом и не переведенной книге, но и доступны любому желающему через Интернет. Просто заходишь на www.research.att.com/~njas/sequences, выбираешь функцию lookup, вводишь несколько членов последовательности и тут же получаешь необходимую справку. Энциклопедия Слоуна работает и в "почтовом" режиме: точно такая же справка будет выслана по электронной почте, если отправить e-mail по адресу sequences@research.att.com, а в теле письма указать начало интересующей вас последовательности. Например, для запроса о простых числах надо написать "lookup 2 3 5 7 11 13".
Чтобы не быть голословным, приведу несколько примеров. Можете попробовать сначала догадаться о законе, управляющем данной последовательностью, а уже потом подглядеть объяснение. Только честно предупреждаю: во многих случаях отыскать закономерность очень и очень непросто.
Примеры:
1. A019460: 2, 3, 3, 5, 10, 13, 39, 43, 172, …
2. A006567: 13, 17, 31, 37, 71, 73, 79, 97, 107, …
3. A001462: 1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, …
4. A005228: 1, 3, 7, 12, 18, 26, 35, 45, 56, 69, …
5. A006751: 2, 12, 1112, 3112, 132112, 1113122112, …
6. A004000: 1, 2, 4, 8, 16, 77, 145, 668, ...
7. A007449: 7, 9, 40, 74, 1526, 5436, 2323240, 29548570, …
8. A006933: 2, 4, 6, 30, 32, 34, 36, 40, 42, 44, 46, 50, …
Пояснения и отгадки:
1. Здесь закон образования последовательности такой: прибавим 1, затем умножим на 1; прибавим 2 и умножим на 2; прибавим 3 и умножим на 3…
2. В последовательность входят только те простые числа, для которых их палиндром (то же число, прочитанное от конца к началу) является другим простым числом. Таким образом, все числа этой последовательности естественным путем разбиваются на пары: 13 и 31, 17 и 71, 37 и 73, 79 и 97, 107 и 701…
3. Пространное словесное описание, которое дают почти все, выглядит примерно так: сначала единица, потом две двойки и две тройки, затем три четверки и три пятерки, четыре шестерки и четыре семерки и т. д. Один мой знакомый сумел дать более короткое описание (именно оно, кстати, приведено у Слоуна): n-й член последовательности показывает, сколько раз в ней встречается число n.
4. Это очень трудная для разгадывания, но воистину замечательная цепочка чисел. Закономерность такова: если выписать, кроме всех этих чисел, всевозможные разности между соседними числами цепочки, то мы получим все натуральные числа: 2=3-1, 4=7-3, 5=12-7, 6=18-12 и т. д.
5. Судя по всему, это самая любимая последовательность Слоуна. Он постоянно приводит ее в качестве примера. Каждое следующее число описывает цифры предыдущего числа: сначала 2, потом "одна двойка" - 12; затем "одна единица и одна двойка" - 1112; "три единицы и одна двойка" - 3112 и т. д.
6. Закон формирования ряда чисел таков: нужно взять палиндром числа (см. выше отгадку к последовательности 2), сложить его с исходным числом и цифры результата расположить в возрастающем порядке.
7. 40=7*7-9, 74=9*9-7. Далее повторяется та же арифметическая закономерность: 1526=40*40-74, 5436=74*74-40.
8. А эта задачка в очень сильной степени не математическая, а лингвистическая. Для ее решения надо знать английские числительные. Правильный ответ состоит в том, чтобы перечислить те числа, для которых в соответствующих числительных ни разу не использована буква "e". Соответствующая "русская" последовательность была бы далеко не столь разреженной: 1, 2, 3, 5, 11, 13, 15, 20, 21, 22, …
Я однажды попытался придумать последовательность, которая отсутствует в энциклопедии Слоуна. Для этого я вспомнил классическую программистскую головоломку, приведенную еще 25 лет назад в книге Д. Кнута "Искусство программирования": как возвести число в n-ю степень, используя при этом минимальное количество умножений (зато можно запоминать промежуточные результаты). Например, для возведения в четвертую степень достаточно не трех умножений, а двух, а двенадцатая степень требует всего четырех умножений. Немного повозившись, я получил начало последовательности, которая задает вот это самое наименьшее число умножений: 0, 1, 2, 2, 3, 3, 4, 3, 4 … Увы, электронный "оракул" развеял все мои иллюзии о новизне придуманной мною последовательности. В ответ на запрос "lookup 0 1 2 2 3 3 4 3" он выдал пулеметную очередь цифр 0,1,2,2,3,3,4,3,4,4,5,4,5,5,5,4,5,5,6,5,6,6,6,5,6,6,6,6,7,6, 7,5,6,6,7,6,7,7,7,6,7,7,7,7,7,7,8,6,7,7,7,7,8,7,8,7,8,8,8,7, 8,8,8,6,7,7,8,7,8,8, сопроводив ее номером последовательности по "бумажной" энциклопедии, словесным описанием и, наконец, ссылкой на второй том упомянутой книги Кнута.
Еще один интереснейший проект реализовал соавтор Нила Слоуна - Саймон Плофф (Simon Plouffe). Его сайт называется "Обратный символьный калькулятор" (Inverse Symbolic Calculator): www.cecm.sfu.ca/projects/ISC/. Калькулятор является "обратным" в том смысле, что по введенному числу выдает возможную формулу, по которой это число было получено. Например, я беру обыкновенный калькулятор Windows, умножаю на нем число e=2,7182818 на пи=3,14159265 и к результату прибавляю единицу. На экранчике высветилось число 9,5397341. Я отправляю это число в "пасть" ISC и мгновенно получаю ответ: "1+e*pi". Не правда ли, забавно?
Пишите мне, как обычно, по адресу kk@knop.spb.ru, я постараюсь ответить на все письма.
