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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
On-Line Encyclopedia of Integer Sequences
Энциклопедия целочисленных последовательностей
OEISicon.svg
URL:

oeis.org

Тип сайта:

интернет-энциклопедия

Автор:

Нил Слоан

Начало работы:

1996

Текущий статус:

Работает

Онла́йн-энциклопе́дия целочи́сленных после́довательностей (англ. On-Line Encyclopedia of Integer Sequences, OEIS) — онлайн-энциклопедия[en], содержащая статьи о последовательностях целых чисел[en], таких, как числа Фибоначчи, числа Белла, числа Каталана, простые числа[1]. OEIS была создана Нилом Слоаном во время его исследовательской деятельности в AT&T Labs. Предвидя свой уход из AT&T Labs в 2012 году и необходимость независимого фонда, в октябре 2009 года Слоан согласился передать интеллектуальную собственность и хостинг OEIS организации OEIS Foundation[2][3][4]. В настоящее время Слоан является президентом OEIS Foundation[3].

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

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

По-видимому, первым упоминанием OEIS на русском языке стала статья Константина Кнопа «Энциклопедия чисел», опубликованная в журнале Компьютерра в феврале 1998 года[7][8].

История[править | править вики-текст]

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

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

  1. A Handbook of Integer Sequences (рус. Руководство по целочисленным последовательностям) (1973)[9], содержавшая 2372 последовательности в лексикографическом порядке, пронумерованные от 1 до 2372;
  2. The Encyclopedia of Integer Sequences (рус. Энциклопедия целочисленных последовательностей) (в соавторстве с Симоном Плуффе[en] (1995)[10], содержавшая 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[10], в частности, говорится:

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

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

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

Нецелочисленные последовательности[править | править вики-текст]

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

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

\textstyle {1 \over 5}, {1 \over 4}, {1 \over 3}, {2 \over 5}, {1 \over 2}, {3 \over 5}, {2 \over 3}, {3 \over 4}, {4 \over 5}

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

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

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

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

Иррациональные числа регистрируются в виде последовательностей цифр. Так, число π = 3.1415926535897… можно обнаружить в OEIS в виде:

Самореферентные последовательности[править | править вики-текст]

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

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

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

Одной из первых самореферентных последовательностей в 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, …
  • Коэффициенты в разложении \textstyle {{\zeta(n + 2)} \over {\zeta(n)}} (A046970):
1, 3, 8, 3, 24, 24, 48, 3, 8, 72, 120, 24, 168, 144, …

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

Статья OEIS[править | править вики-текст]

Урезанный пример[править | править вики-текст]

Статья 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 может содержать следующие поля[21]:

ID number
Каждой последовательности в OEIS присвоен последовательный номер — шестизначное положительное целое число с префиксом A (от англ. absolute). Номера назначаются либо редактором (редакторами), либо распределителем A-номеров, что удобно при добавлении сразу нескольких взаимосвязанных последовательностей с перекрёстными ссылками. Срок действия A-номера, полученного с помощью распределителя, в случае неиспользования истекает спустя месяц после выдачи.
Нумерация последовательностей в книгах, предшествовавших 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[en], PARI/GP[en], Sage. Язык программирования указан в скобках.
See also
Перекрёстные ссылки, добавленные отправившим последовательность участником, обычно помечены «Cf.» За исключением новых последовательностей, поле «См. также» включает информацию о контексте последовательности и ссылки на последовательности с близкими A-номерами.
Keyword
В OEIS принят стандартный набор 4-5-буквенных ключевых слов, характеризующих последовательности[21][22][4]:
  • 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 В большой степени субъективное ключевое слово, обозначающее «последовательность, не имеющая прямого значения» (англ. An unimportant sequence). В качестве примеров можно привести A001355, «Смесь цифр чисел "пи" и "е"», и A082390, «Числа на компьютерной цифровой клавиатуре по спирали».
  • dupe Дубликат другой последовательности.
  • easy Элементы последовательности легко вычислимы. Иногда ключевое слово используется для последовательностей «простые числа вида f(m)», где f(m) — легковычислимая функция, даже если проверка простоты f(m) является трудной задачей.
  • eigen Последовательность инвариантна при некотором преобразовании или является преобразованием другой последовательности.
  • fini Последовательность конечна, хотя могут отображаться не все элементы.
  • frac Последовательность числителей или знаменателей в последовательности дробей. Любая последовательность числителей должна ссылаться на соответствующую ей последовательность знаменателей (и наоборот).
  • full Последовательность отображена полностью. При наличии ключевого слова «full» ключевое слово «fini» также должно присутствовать.
  • hard Последовательность с трудом поддаётся вычислению. Часто ключевое слово используется для последовательностей, связанных с нерешёнными проблемами; например, A001116 перечисляет известные решения проблемы о числе n-сфер, касающихся данной n-сферы.
  • hear Последовательность с «особенно интересным и/или красивым» аудиопредставлением. «Последовательность, которую стоит послушать» (англ. A sequence worth listening to).
  • 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 Последовательность считается непонятной и требует лучшего определения.
  • probation Последовательность может быть удалена позже по решению редактора.
  • sign Некоторые или все элементы последовательности отрицательны. Статья содержит два поля: поле signed содержит элементы исходной последовательности, а поле sequence — их абсолютные значения.
  • 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
  3. 1 2 3 4 5 The OEIS Foundation Inc..
  4. 1 2 3 4 5 6 7 The Achievement of The Online Encyclopedia of Integer Sequences. AT&T Labs Research (March 6, 2012). Архивировано из первоисточника 20 октября 2015.
  5. Из предисловия к 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.»
  6. The On-Line Encyclopedia of Integer Sequences.
  7. 1 2 Надежда Сербина, Алексей Извалов. Web-обзор онлайновой энциклопедии целочисленных последовательностей.
  8. Кноп К. Энциклопедия чисел // Компьютерра. — 1998. — № 7.
  9. 1 2 N. J. A. Sloane. A Handbook of Integer Sequences. — Academic Press, 1973. — ISBN 0-12-648550-X.
  10. 1 2 3 N. J. A. Sloane, Simon Plouffe. Encyclopedia of Integer Sequences. — Сан-Диего: Academic Press, 1995. — ISBN 0-12-558630-2.
  11. «Journal of Integer Sequences». ISSN 1530-7638.
  12. Sloane, N. J. A. (2003). «The On-Line Encyclopedia of Integer Sequences». Notices of the American Mathematical Society 50 (8): 912–915.
  13. Editorial Board. On-Line Encyclopedia of Integer Sequences.
  14. Статья A100000 в OEIS. Middle column of marks found on the oldest object with logical carvings, the 22000-year-old Ishango bone from the Congo.
  15. OeisWiki.
  16. Neil Sloane. Announcement, Nov 17 2010: New Version of OEIS! (17 ноября 2010).
  17. Neil J. A. Sloane. [seqfan] A200000. SeqFan mailing list (14 ноября 2011).
  18. Neil J. A. Sloane. [seqfan] A200000 chosen. SeqFan mailing list (22 ноября 2011).
  19. Suggested Projects. OeisWiki.
  20. N. J. A. Sloane. My Favorite Integer Sequences. arXiv.org.
  21. 1 2 Explanation of Terms Used in Reply From. On-Line Encyclopedia of Integer Sequences.
  22. User:Charles R Greathouse IV/Keywords. OeisWiki.

Литература[править | править вики-текст]

Ссылки[править | править вики-текст]