Онлайн-энциклопедия целочисленных последовательностей

Материал из Википедии — свободной энциклопедии
(перенаправлено с «OEIS»)
Перейти к навигации Перейти к поиску
On-Line Encyclopedia of Integer Sequences
Энциклопедия целочисленных последовательностей
Изображение логотипа
URL oeis.org
Тип сайта интернет-энциклопедия и онлайновая база данных[вд]
Создатель Нил Слоун
Начало работы 1996
Текущий статус работает
Логотип Викисклада Медиафайлы на Викискладе

Онлайн-энциклопедия целочисленных последовательностей (англ. On-Line Encyclopedia of Integer Sequences, OEIS) — сетевая энциклопедия, содержащая записи о последовательностях целых чисел[англ.], таких как числа Фибоначчи, числа Белла, числа Каталана, простые числа[1]. Наполняется по принципу вики с премодерацией.

OEIS была создана Нилом Слоуном во время его исследовательской деятельности в AT&T Labs. В октябре 2009 года Слоун передал интеллектуальную собственность и хостинг OEIS организации OEIS Foundation[2][3][4]. Слоун занимал пост президента OEIS Foundation до 2021 года, когда его сменил Расс Кокс[3][5].

В OEIS хранится информация о целочисленных последовательностях, представляющих интерес как для любителей, так и для специалистов в математике, комбинаторике, теории чисел, теории игр, физике, химии, биологии, информатике[4][6]. На 2022 год в базе данных хранится свыше 350 000 последовательностей[7].

Запись в OEIS включает в себя первые элементы последовательности, ключевые слова, математическое описание, фамилии авторов, ссылки на литературу; присутствует возможность построения графика или проигрывания музыкального представления последовательности. Поиск в базе данных может осуществляться по ключевым словам и по подпоследовательности[3][4][8].

По-видимому, первым упоминанием OEIS на русском языке стала статья Константина Кнопа «Энциклопедия чисел», опубликованная в журнале Компьютерра в феврале 1998 года[9], а первым упоминанием «бумажного» предшественника онлайн-энциклопедии — статья Мартина Гарднера «Числа Каталана», опубликованная в журнале Квант в июле 1978 года[8].

Нил Слоун начал собирать целочисленные последовательности в 1964—1965 годах, будучи аспирантом в Корнеллском университете, в связи со своими исследованиями в комбинаторике. Изначально база данных хранилась на перфокартах[3][4][10][11].

База данных дважды была опубликована в печатной форме:

  1. A Handbook of Integer Sequences (рус. Справочник по целочисленным последовательностям) (1973)[10][12], содержавшая 2372 последовательности в лексикографическом порядке, пронумерованные от 1 до 2372;
  2. The Encyclopedia of Integer Sequences (рус. Энциклопедия целочисленных последовательностей) (в соавторстве с Симоном Плуффе[англ.] (1995)[11], содержавшая 5488 последовательностей, которым были присвоены M-номера от M0000 до M5487. Книга содержала ссылки на соответствующие последовательности (которые могли отличаться в нескольких первых элементах) в A Handbook of Integer Sequences в виде N-номеров от N0001 до N2372, а также содержала A-номера (используемые и по сей день), которых не было в A Handbook of Integer Sequences.

Книги были хорошо приняты и, особенно после второй публикации, Слоун стал получать от математиков постоянный поток новых последовательностей. Коллекцию стало невозможно поддерживать в форме книги, и Слоун решил опубликовать базу данных в сети Интернет — вначале в виде e-mail-сервиса (август 1994), а затем в виде веб-сайта (1996). В книге The Encyclopedia of Integer Sequences[11], в частности, говорится:

Имеются две онлайн-версии Энциклопедии, доступные по электронной почте. Первая — простой поисковой сервис, в то время как вторая делает всё, чтобы найти объяснение для последовательности. (...) Второй сервер не только ищет последовательность в таблице — он также пытается найти объяснение для неё, используя многие из описанных в этой главе приёмов.

База данных продолжает расти со скоростью около 10—18 тысяч записей в год[3][4]. В качестве побочного результата своей работы над базой данных в 1998 году Слоун основал Journal of Integer Sequences (рус. Журнал целочисленных последовательностей)[13]. Слоун лично редактировал энциклопедию сначала в бумажном, а затем в электронном виде почти 40 лет, однако с 2002 года ему в этом помогает сообщество редакторов-добровольцев[4][14][15].

В 2004 году в OEIS была добавлена стотысячная последовательность, A100000, подсчитывающая насечки на кости Ишанго[16]. В 2006 году пользовательский интерфейс был полностью переработан, появились дополнительные возможности для поиска. В 2010 году для упрощения совместной работы редакторов и участников была создана OEIS wiki[17][18]. Двухсоттысячная последовательность, A200000, была добавлена в ноябре 2011; вначале она была введена как A200715, но была перемещена в A200000 после недельного обсуждения в списке рассылки SeqFan[19][20], за которым последовало предложение главного редактора OEIS Чарльза Грэтхауса выбрать в качестве A200000 особенную последовательность[21].

Нецелочисленные последовательности

[править | править код]

Помимо последовательностей целых чисел, в OEIS имеются последовательности дробей, цифр трансцендентных чисел, комплексных чисел, тем или иным способом преобразованные в целочисленные последовательности.

Последовательности рациональных чисел представляются парой последовательностей, помеченных ключевым словом frac: последовательностью числителей и последовательностью знаменателей. К примеру, ряд Фарея пятого порядка

представлен в виде последовательности числителей

1, 1, 1, 2, 1, 3, 2, 3, 4 (A006842)

и последовательности знаменателей

5, 4, 3, 5, 2, 5, 3, 4, 5 (A006843).

Иррациональные числа входят в OEIS в виде последовательностей цифр. Так, число π = 3,1415926535897… можно найти в OEIS в виде:

Самореферентные последовательности

[править | править код]

Очень рано в истории OEIS были предложены последовательности, определённые через нумерацию последовательностей в самой OEIS. Как вспоминает Слоун,

Долгое время я сопротивлялся добавлению этих последовательностей, отчасти из-за желания сохранить репутацию базы данных, отчасти же потому, что были известны лишь 11 элементов A22!

N. J. A. Sloane, My favorite integer sequences[22]

Одной из первых самореферентных последовательностей в OEIS была A031135 (позже A091967) «a(n) = элемент последовательности An с номером n». Эта последовательность стимулировала поиск новых элементов последовательности A000022. Некоторые последовательности конечны (ключевое слово fini) и представлены полностью (ключевое слово full); такие последовательности не содержат элемента, который соответствует номеру последовательности в OEIS, и соответствующий элемент последовательности A091967 не определён (первый такой случай возникает при n = 53).

Соглашения

[править | править код]

OEIS была ограничена простым ASCII-текстом до 2011 года. В текстах записей часто используется линейная форма математической нотации (f(n) для функций, n для переменных и т. д.). Греческие буквы обычно записываются полными именами. Идентификатор каждой последовательности начинается с латинской буквой A, за которой следуют шесть цифр (например, A000315). Отдельные элементы последовательности разделены запятыми. Группы цифр никак не разделены. В комментариях и формулах a(n) обозначает элемент последовательности с номером n.

Особое значение ноля

[править | править код]

Ноль часто используется для обозначения несуществующих элементов последовательности. Например, последовательность A104157 перечисляет «наименьшее из n2 последовательных простых чисел, образующих магический квадрат n ×n с минимальной магической константой, или 0, если такого магического квадрата не существует». a(1) = 2; a(3) = 1 480 028 129; однако магического квадрата 2 × 2 из последовательных простых чисел не существует, поэтому a(2) = 0.

Иногда для той же цели используется −1, как в последовательности A094076.

Лексикографическое упорядочение

[править | править код]

В OEIS поддерживается лексикографический порядок последовательностей; таким образом, у каждой последовательности есть предшествующая и последующая последовательности («контекст»). Обычно в целях нормализации ведущие нули, единицы и знаки элементов опускаются.

В качестве примера можно рассмотреть следующие последовательности:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, …
2, 3, 5, 7, 11, 101, 131, 151, 181, 191, 313, 353, 373, 383, 727, 757, 787, 797, 919, 929, …
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, …
1, 2, 4, 7, 11, 16, 22, 29, 37, 46, 56, 67, 79, 92, 106, 121, 137, 154, …
  • Коэффициенты в разложении (A046970):
1, 3, 8, 3, 24, 24, 48, 3, 8, 72, 120, 24, 168, 144, …

Выделенные фрагменты при определении «контекста» последовательности опускаются.

Формат записей

[править | править код]

Урезанный пример

[править | править код]

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

A046970     Generated from Riemann Zeta function: coefficients in series expansion of Zeta(n+2)/Zeta(n).
            1, -3, -8, -3, -24, 24, -48, -3, -8, 72, -120, 24, -168, 144, 192, -3, -288, 24, -360, 72, 384, 360, -528, 24, -24, 504, -8, 144, -840, -576, -960, -3, 960, 864, 1152, 24, -1368, 1080, 1344, 72, -1680, -1152, -1848, 360, 192, 1584, -2208, 24, -48, 72, 2304, 504, -2808, 24, 2880, 144, 2880, 2520, -3480, -576  
OFFSET 	    1,2
COMMENTS    B(n+2) = -B(n)*((n+2)*(n+1)/(4pi^2))*z(n+2)/z(n) = -B(n)*((n+2)*(n+1)/(4pi^2))*Sum(j=1, infinity) [ a(j)/j^(n+2) ]
            ...
REFERENCES  M. Abramowitz and I. A. Stegun, Handbook of Mathematical Functions, Dover Publications, 1965, pp. 805-811.
LINKS       M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].  
            Wikipedia, Riemann zeta function.
FORMULA     Multiplicative with a(p^e) = 1-p^2. a(n) = Sum_{d|n} mu(d)*d^2.
            a(n) = product[p prime divides n, p^2-1] (gives unsigned version) [From Jon Perry (jonperrydc(AT)btinternet.com), Aug 24 2010]
EXAMPLE     a(3) = -8 because the divisors of 3 are {1, 3} and mu(1)*1^2 + mu(3)*3^2 = -8.
            ...
MAPLE 	    Jinvk := proc(n, k) local a, f, p ; a := 1 ; for f in ifactors(n)[2] do p := op(1, f) ; a := a*(1-p^k) ; end do: a ; end proc:
            A046970 := proc(n) Jinvk(n, 2) ; end proc: # R. J. Mathar, Jul 04 2011 
MATHEMATICA muDD[d_] := MoebiusMu[d]*d^2; Table[Plus @@ muDD[Divisors[n]], {n, 60}] (Lopez)
            Flatten[Table[{ x = FactorInteger[n]; p = 1; For[i = 1, i <= Length[x], i++, p = p*(x[[i]][[1]]^2 - 1)]; p}, {n, 1, 50, 1}]] [From Jon Perry (jonperrydc(AT)btinternet.com), Aug 24 2010]
PROG 	    (PARI) A046970(n)=sumdiv(n, d, d^2*moebius(d)) (Benoit Cloitre)
CROSSREFS   Cf. A027641 and A027642.
            Sequence in context: A035292 A144457 A146975 * A058936 A002017 A118582
            Adjacent sequences:  A046967 A046968 A046969 * A046971 A046972 A046973 
KEYWORD     sign,mult
AUTHOR      Douglas Stoll, dougstoll(AT)email.msn.com
EXTENSIONS  Corrected and extended by Vladeta Jovovic (vladeta(AT)eunet.rs), Jul 25 2001
            Additional comments from Wilfredo Lopez (chakotay147138274(AT)yahoo.com), Jul 01 2005

Запись в OEIS может содержать следующие поля[23]:

ID number
Каждой последовательности в OEIS присвоен последовательный номер — шестизначное положительное целое число с префиксом A (от англ. absolute). Номера обычно назначаются автоматически.
Нумерация последовательностей в книгах, предшествовавших OEIS, отличается от существующей. M-номера, использовавшиеся в Handbook of Integer Sequences (1973), и N-номера, использовавшиеся в Encyclopedia of Integer Sequences (1995), также указаны в поле ID number в скобках после A-номера.
Sequence data
В поле «Данные последовательности» перечисляются сами числа. В данном поле не различаются конечные последовательности, слишком длинные для отображения, и бесконечные последовательности; для различения используются ключевые слова fini, full и more. Чтобы определить, какому значению n соответствуют значения элементов последовательности, используется поле offset, в котором указано значение n для первого указанного элемента.
Name
Поле «Имя» обычно содержит общепринятое наименование последовательности, иногда вместе с формулой.
Comments
Поле «Комментарии» предназначено для информации о последовательности, которая «не вмещается» в другие поля. Часто в комментариях указаны интересные взаимосвязи между разными последовательностями и не очевидные применения.
References
Ссылки на печатные документы (книги, статьи, публикации и т. п.).
Links
Ссылки (URL) на онлайн-ресурсы.
Formula
Формулы, рекуррентные формулы, производящие функции и т. п..
Example
Примеры значений элементов последовательности с пояснениями.
Maple
Код Maple.
Mathematica
Код Mathematica.
Program
Программы на разных языках, включая Magma[англ.], PARI/GP[англ.], Sage. Язык программирования указан в скобках.
See also
Перекрёстные ссылки, добавленные отправившим последовательность участником, обычно помечены «Cf.» За исключением новых последовательностей, поле «См. также» включает информацию о контексте последовательности и ссылки на последовательности с близкими A-номерами.
Keyword
В OEIS принят стандартный набор 4-5-буквенных ключевых слов, характеризующих последовательности[4][23][24]:
  • base Определение последовательности связано с определёнными системами счисления. Например, 2, 3, 5, 7, 11, 101, 131, 151, 181… (A002385) являются простыми числами в любой системе счисления, но палиндромами только в системе счисления с основанием 10.
  • bref Последовательность слишком коротка для анализа.
  • changed Последовательность была изменена в последние две или три недели.
  • cofr Последовательность представляет собой непрерывную дробь, например, разложение числа e (A003417) или π (A001203).
  • cons Десятичное представление математической константы, например, e (A001113) или π (A000796).
  • core Последовательность имеет фундаментальное значение в той или иной ветви математики. Примерами могут быть простые числа (A000040) и числа Фибоначчи (A000045).
  • dead Последовательность содержит ошибки либо дублирует другую последовательность. В базу данных включены ошибочные последовательности, появлявшиеся в литературе, со ссылками на корректные версии последовательностей.
  • dumb В большой степени субъективное ключевое слово, обозначающее последовательность, не имеющая прямого математического значения. В качестве примеров можно привести A001355 «Смесь цифр чисел "пи" и "е"», и A082390 «Числа на компьютерной цифровой клавиатуре по спирали».
  • easy Элементы последовательности легко вычислимы. Иногда ключевое слово используется для последовательностей «простые числа вида f(m)», где f(m) — легковычислимая функция, даже если проверка простоты f(m) является трудной задачей.
  • eigen Последовательность инвариантна при некотором преобразовании или является преобразованием другой последовательности.
  • fini Последовательность конечна, хотя могут отображаться не все элементы.
  • frac Последовательность числителей или знаменателей в последовательности дробей. Любая последовательность числителей должна ссылаться на соответствующую ей последовательность знаменателей (и наоборот).
  • full Последовательность отображена полностью. При наличии ключевого слова «full» ключевое слово «fini» также должно присутствовать.
  • hard Последовательность с трудом поддаётся вычислению. Часто ключевое слово используется для последовательностей, связанных с нерешёнными проблемами; например, A001116 перечисляет известные решения проблемы о числе n-сфер, касающихся данной n-сферы.
  • hear Последовательность с «особенно интересным и/или красивым» аудиопредставлением. «Последовательность, которую стоит послушать».
  • less «Не особенно интересная последовательность».
  • look Последовательность с «особенно интересным и/или красивым графиком».
  • more Требуется больше элементов последовательности; читатели могут отправлять дополнения.
  • mult Последовательность соответствует мультипликативной функции. Элемент a(1) должен равняться 1; элемент a(mn) может быть вычислен как a(m)a(n) при условии, что m и n взаимо просты (т.е. НОД(m,n) = 1). К примеру, в A046970 a(12) = a(3)a(4) = -8 × -3.
  • new Последовательность была недавно добавлена или изменена.
  • nice По-видимому, наиболее субъективное ключевое слово, для «исключительно красивых последовательностей».
  • nonn Элементы последовательности — неотрицательные целые числа. Не делается различия между последовательностями, состоящими из неотрицательных чисел только из-за выбранного смещения (таких, как последовательность кубов) и последовательностями, которые по определению являются неотрицательными (таких, как последовательность квадратов).
  • obsc Последовательность считается непонятной и требует лучшего определения.
  • sign Некоторые или все элементы последовательности отрицательны.
  • tabf Массив чисел сложной формы, преобразованный в последовательность построчно. Пример — A071031 «Последовательные состояния клеточного автомата с правилом 62».
  • tabl Последовательность получена построчным прочтением треугольного или квадратного массива чисел. Наиболее типичный пример — треугольник Паскаля (A007318).
  • uned Слоун или другие редакторы не редактировали последовательность, но считают её достойной включения в энциклопедию. Запись может содержать вычислительные ошибки или опечатки. Обычно редакторы проверяют все поступающие последовательности, чтобы убедиться, что:
  • последовательность достойна включения в OEIS
  • дано вразумительное определение
  • этой последовательности ещё нет в базе данных
  • в тексте используется корректный английский язык
  • используется корректное форматирование
  • и т. п.
  • unkn О последовательности почти ничего не известно, даже формула. Примером является последовательность A072036.
  • walk Последовательность указывает число (несамопересекающихся) путей на некотором графе или решётке.
  • word Последовательность зависит от слов того или иного языка. Пример — последовательность A006994, «Число букв в n в русском языке».
Некоторые ключевые слова исключают друг друга, а именно: core и dumb, easy и hard, full и more, less и nice, nonn и sign.
Offset
Смещение — индекс первого приведённого элемента последовательности. Смещение по умолчанию — 0. Смещение большинства последовательностей в OEIS равно 0 или 1. В поле указаны два числа, первое из которых — смещение, а второе — индекс первого элемента, абсолютное значение которого превышает 1. Так, в случае последовательности A000001, начинающейся числами a(0) = 0, a(1) = 1, a(2) = 1, a(3) = 1, a(4) = 2, поле «Смещение» содержит числа 0, 5.
Author(s)
Автор (авторы) последовательности — те, кто отправил последовательность в OEIS, даже если она была известна с древних времён.
Extension
Имена тех, кто дополнил последовательность, вместе с датами обновления записи.

Примечания

[править | править код]
  1. Когда определение целочисленного множества не определяет явно способ упорядочения (как в случае с простыми числами), считается, что элементы упорядочены по возрастанию.
  2. Transfer of IP in OEIS to The OEIS Foundation Inc. — «Yesterday (Monday, October 26 2009) was a landmark day in the history of the OEIS. I transferred the intellectual property I own in the OEIS to The OEIS Foundation Inc. The letter of assignment can be seen here.» Дата обращения: 29 октября 2015. Архивировано из оригинала 6 декабря 2013 года.
  3. 1 2 3 4 5 The OEIS Foundation Inc. Дата обращения: 2 декабря 2023. Архивировано 2 декабря 2023 года.
  4. 1 2 3 4 5 6 7 The Achievement of The Online Encyclopedia of Integer Sequences. AT&T Labs Research (6 марта 2012). Архивировано 20 октября 2015 года.
  5. Katie Steckles. Aperiodical News Roundup – June 2021. The Aperiodical (7 июля 2021). Дата обращения: 12 июля 2021. Архивировано 12 июля 2021 года.
  6. Из предисловия к A Handbook of Integer Sequences (1973): «Who will use this handbook? Anyone who has ever been confronted with a strange sequence, whether in an intelligence test in high school… or in solving a mathematical problem… or from a counting problem… or in physics… or in chemistry… or in electrical engineering… will find this handbook useful.»
  7. The On-Line Encyclopedia of Integer Sequences. Дата обращения: 1 июня 2010. Архивировано 29 марта 2011 года.
  8. 1 2 Надежда Сербина, Алексей Извалов. Web-обзор онлайновой энциклопедии целочисленных последовательностей. Дата обращения: 29 октября 2015. Архивировано 9 февраля 2016 года.
  9. Кноп, 1998.
  10. 1 2 N. J. A. Sloane. A Handbook of Integer Sequences (англ.). — Academic Press, 1973. — ISBN 0-12-648550-X.
  11. 1 2 3 N. J. A. Sloane, Simon Plouffe. Encyclopedia of Integer Sequences (англ.). — Сан-Диего: Academic Press, 1995. — ISBN 0-12-558630-2.
  12. Гарднер М. Глава 20. Числа Каталана // Путешествие во времени. — М.: Мир, 1990. — С. 285. — 341 с. — ISBN 5-03-001166-8.
  13. Journal of Integer Sequences (неопр.). — ISSN 1530-7638. Архивировано 23 мая 2013 года.
  14. Sloane, N. J. A. The On-Line Encyclopedia of Integer Sequences (англ.) // Notices of the American Mathematical Society : journal. — 2003. — Vol. 50, no. 8. — P. 912—915. Архивировано 20 марта 2021 года.
  15. Editorial Board. On-Line Encyclopedia of Integer Sequences. Дата обращения: 19 марта 2022. Архивировано 23 июня 2011 года.
  16. Последовательность A100000 в OEIS. Middle column of marks found on the oldest object with logical carvings, the 22000-year-old Ishango bone from the Congo.
  17. OeisWiki. Дата обращения: 29 октября 2015. Архивировано 11 июля 2020 года.
  18. Neil Sloane. Announcement, Nov 17 2010: New Version of OEIS! (17 ноября 2010). Дата обращения: 5 октября 2015. Архивировано 7 февраля 2016 года.
  19. Neil J. A. Sloane. [seqfan] A200000. SeqFan mailing list (14 ноября 2011). Дата обращения: 5 октября 2015. Архивировано 26 апреля 2012 года.
  20. Neil J. A. Sloane. [seqfan] A200000 chosen. SeqFan mailing list (22 ноября 2011). Дата обращения: 5 октября 2015. Архивировано 26 апреля 2012 года.
  21. Suggested Projects. OeisWiki. Дата обращения: 29 октября 2015. Архивировано 19 сентября 2015 года.
  22. N. J. A. Sloane. My Favorite Integer Sequences. arXiv.org. Дата обращения: 5 октября 2015. Архивировано 11 сентября 2015 года.
  23. 1 2 Explanation of Terms Used in Reply From. On-Line Encyclopedia of Integer Sequences. Дата обращения: 29 октября 2015. Архивировано 5 декабря 2015 года.
  24. User:Charles R Greathouse IV/Keywords. OeisWiki. Дата обращения: 29 октября 2015. Архивировано 15 сентября 2015 года.

Литература

[править | править код]