Последовательность всех известных целочисленных последовательностей

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

Матрица всех последовательностей

Каждая последовательность в энциклопедии имеет номер A000001, A000002, ... Выстроим последовательности по номерам и запишем друг под другом.

A000001: 0, 1, 1, 1, 2, 1, 2, 1, 5, 2, ...
A000002: 1, 2, 2, 1, 1, 2, 1, 2, 2, 1, ...
A000003: 1, 1, 1, 1, 2, 2, 1, 2, 2, 2, ...
A000004: 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...
A000005: 1, 2, 2, 3, 2, 4, 2, 4, 3, 4, ...
A000006: 1, 1, 2, 2, 3, 3, 4, 4, 4, 5, ...
A000007: 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...
A000008: 1, 1, 2, 2, 3, 4, 5, 6, 7, 8, ...
A000009: 1, 1, 1, 2, 2, 3, 4, 5, 6, 8, ...
A000010: 1, 1, 2, 2, 4, 2, 6, 4, 6, 4, ...
A000011: 1, 1, 2, 2, 4, 4, 8, 9, 18, 23, ...
A000012: 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...
A000013: 1, 1, 2, 2, 4, 4, 8, 10, 20, 30, ...
A000014: 0, 1, 1, 0, 1, 1, 2, 2, 4, 5, ...
A000015: 1, 2, 3, 4, 5, 7, 7, 8, 9, 11, ...
A000016: 1, 1, 1, 2, 2, 4, 6, 10, 16, 30, ...
A000017: 1, 0, 0, 2, 2, 4, 8, 4, 16, 12, ...
A000018: 1, 1, 2, 2, 4, 8, 13, 25, 44, 83, ...
A000019: 1, 1, 2, 2, 5, 4, 7, 7, 11, 9, ...
A000020: 2, 1, 2, 2, 6, 6, 18, 16, 48, 60, ...

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

Функция спаривания

Первым функцию спаривания придумал Кантор. Графически спаривание двух целых по Кантору показано на рисунке.

Оно же выражается формулой:

z = (x^2 + x + 2xy+ 3y + y^2) / 2,

где (x, y) два целых неотрицательных числа, а z — их спаренный номер. Очевидно, что отображения (x, y) → z является однозначным и обратимым.

Последовательность последовательностей

Теперь каждому элементу матрицы последовательностей в позиции (x, y) сопоставим номер z. Учтем, что позиция элемента отсчитывается от нуля, то есть самый первый элемент z = 1 находится в позиции (0, 0). Таким способом мы пронумеруем все элементы матрицы последовательностей и, тем самым, составим новую последовательность всех последовательностей.

0, 1, 1, 1, 2, 1, 1, 2, 1, 0, 2, 1, 1, 0, 1, 1, 1, 1, 0, 2, 1, 2, 2, 2, 0, 2, 1, 1, 1, 1, 2, 0, 3, 2, 0, 1, 5, 2, 1, 0, 2, 2, 0, 1, 1, 2, 2, 2, 0, 4, 3, 0, 2, 1, 1, 2, 1, 2, 0, 2, 3, 0, 2, 1, 1, 1, 1, 2, 2, 0, 4, 4, 0, 3, 2, 2, 1, 1, 5, 2, 3, 0, 3, 4, 0, 4, 2, 2, 2, 1, 1, 1, 1, 2, 0, 4, 4, 0, 5, 3, 4, 2, 1, 1, 0, 2, 1, 2, 0, 2, 5, 0, 6, 4, 2, 4, 1, 2, 1, 1, 1, 2, 4, 0, 6, 5, 0, 7, 5, 6, 4, 1, 2, 1, 2, 1, 14, 1, 2, 0, 2, 6, 0, 8, 6, 4, 8, 1, 4, 0, 3, 1, 1, 1, 1, 2, 0, 4, 6, 0, 11, 8, 6, 9, 1, 4, 1, 4, 1, 0, 1, 5, 2, 4, 0, 4, 6, 0, 12, 10, 4, 18, 1, 8, 1, 5, 2, 0, 1, 1, 1, 2, 2, 0, 5, 6, 0, 15, 12, 10, 23, 1, 10, 2, 7, 2, 2, 2, 1, 2, 5, 1, 3, 0, 2, 7, 0, 16, 15, 4, 44, 1, 20, 2, 7, 4, 2, 2, 2, 1, 1, 2, 2, 4, 0, 6, 7, 0, 19, 18, 12, 63, 1, 30, 4, 8, 6, 4, 4, 2, 2, 1, 0, 2, 1, 4, 0, 2, 7, 0, 22, 22, 6, 122, 1, 56, 5, 9, 10, 8, 8, 5, 2, 2, 1, 1, 1, 1, 2, 0, 6, 8, 0, 25, 27, 8, 190, 1, 94, 10, 11, 16, 4, 13, 4, 6, 2, 0, -1, 1, 15, 2, 3, 0, 4, 8, 0, 28, 32, 8, 362, 1, 180, 14, 11, 30, 16, 25, 7, 6, 6, 1, 2, 1, 1, 2, 1, 4, 0, 4, 8, 0, 31, 38, 16, 612, 1, 316, 26, 13, 52, 12, 44, 7, 18, 9, 1, -2, 2, 1, 1, 2, 2, 2, 0, 2, 8, 0, 34, 46, 6, 1162, 1, 596, 42, 13, 94, 48, 83, 11, 16, 17, 2, 8, 2, -2, 2, 1, 5, 2, 6, 0, 8, 9, 0, 40, 54, 18, 2056, 1, 1096, 78, 16, 172, 80, 152, 9, 48, 30, 2, 8, 7, 3, 3, 2, 2, 4, 1, 3, 0, 3, 9, 0, 43, 64, 8, 3914, 1, 2068, 132, 16, 316, 136, 286, 8, 60, 54, 6, 112, 10, -3, 4, 3, 3, 1, 1, 1, 2, 0, 4, 9, 0, 49, 76, 12, 7155, 1, 3856, 249, 16, 586, 420, 538, 6, 176, 98, 9, 656, 20, 3, 5, 4, 4, 2, 0, 4, 2, 6, 0, 4, 10, 0, 52, 89, 10, 13648, 1, 7316, 445, 17, 1096, 1240, 1020, 9, 144, 183, 20, 5504, 36, -5, 6, 5, 5, 3, ...

Задача построения последовательности всех последовательностей решена.

Бесконечное множество последовательности последователностей

Допишем новую последовательность в конец нашей матрицы и снова перенумеруем все ее элементы. Тем самым мы построим новую последовательностей всех последовательностей. Далее это процесс мы можем продолжать до бесконечности.

Наконец, помимо функции спаривания Кантора, мы можем взять любую другую функцию спаривания: Хопкрофта-Ульмана (1979), Штейна (1999), Пижона (2001), Шуджика (2006), — и построить новую последовательность всех последовательностей. Либо вы можете придумать собственный способ нумерации элементов матрицы.

Идею о том, что функцию спаривания Кантора можно применить для нумерации элементом матрицы всех последовательностей, я подсмотрел у Ивана Бакшеева.

Спаривайтесь с умом)