Целочисленная последовательность

Начало последовательности Фибоначчи на здании в Гетеборге.

В математике целочисленная последовательность — это последовательность (т. е. упорядоченный список) целых чисел .

Целочисленная последовательность может быть задана явно, задав формулу для ее n- го члена, или неявно, задав связь между ее членами. Например, последовательность 0, 1, 1, 2, 3, 5, 8, 13, ... ( последовательность Фибоначчи ) формируется, начиная с 0 и 1, а затем добавляя любые два последовательных члена для получения следующего: неявное описание (последовательность A000045 в OEIS ). Последовательность 0, 3, 8, 15,... формируется по формуле n ² − 1 для n- го члена: явное определение.

Альтернативно, целочисленная последовательность может определяться свойством, которым обладают члены последовательности и которым не обладают другие целые числа. Например, мы можем определить, является ли данное целое число совершенным числом (последовательность A000396 в OEIS ), даже если у нас нет формулы для n -го совершенного числа.

Вычислимые и определимые последовательности

Целочисленная последовательность является если вычислимой, алгоритм, который по заданному n вычисляет n _{существует} для всех n > 0. Множество вычислимых целочисленных последовательностей счетно . Множество всех целочисленных последовательностей несчетно (с мощностью, равной мощности континуума ), поэтому не все целочисленные последовательности вычислимы.

Хотя некоторые целочисленные последовательности имеют определения, не существует систематического способа определить, что означает, что целочисленная последовательность может быть определена во вселенной или в каком-либо абсолютном (независимом от модели) смысле.

Предположим, что множество M является транзитивной моделью теории множеств ZFC . Транзитивность M подразумевает, что целые числа и целочисленные последовательности внутри M на самом деле являются целыми числами и последовательностями целых чисел. Целочисленная последовательность — это определимая последовательность относительно M, существует некоторая формула P ( x если на языке теории множеств ) с одной свободной переменной и без параметров, которая верна в M для этой целочисленной последовательности и ложна в M для всех остальных. целочисленные последовательности. В каждом таком M существуют определимые целочисленные последовательности, которые не являются вычислимыми, например последовательности, которые кодируют скачки Тьюринга вычислимых множеств.

Для некоторых транзитивных моделей M ZFC каждая последовательность целых чисел в M определима относительно M ; для других — только некоторые целочисленные последовательности (Hamkins et al. 2013). Не существует систематического способа определить в самом M набор последовательностей, определяемых относительно M , и этот набор может даже не существовать в каком-то таком M . Аналогично, отображение набора формул, определяющих целочисленные последовательности в M, в целочисленные последовательности, которые они определяют, не определимо в M и может не существовать в M . Однако в любой модели, которая обладает такой картой определимости, некоторые целочисленные последовательности в модели не могут быть определены относительно модели (Hamkins et al. 2013).

Если M содержит все целочисленные последовательности, то набор целочисленных последовательностей, определяемых в M, будет существовать в M и быть счетным и счетным в M .

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

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

Примеры

Целочисленные последовательности, имеющие собственное имя, включают:

• Обильные цифры
• Последовательность Баума – Свита
• Номера звонков
• Биномиальные коэффициенты
• Числа Кармайкла
• Каталонские цифры
• Составные числа
• Недостаточные цифры
• числа Эйлера
• Четные и нечетные числа
• Факториальные числа
• Числа Фибоначчи
• Слово Фибоначчи
• Фигурные числа
• Последовательность Голомба
• Счастливые числа
• Очень составные числа
• Очень внимательные числа
• Домашние простые числа
• Гиперсовершенные числа
• Последовательность жонглера
• Последовательность Колакоски
• Счастливые числа
• Числа Лукаса
• Числа Моцкина
• Натуральные числа
• Падованские числа
• Номера разделов
• Совершенные числа
• Практические цифры
• Простые числа
• Псевдопростые числа
• Последовательность Рекамана
• Обычная последовательность складывания бумаги
• Последовательность Рудина-Шапиро
• Полусовершенные числа
• Полупростые числа
• Суперсовершенные числа
• Треугольные числа
• Последовательность Туэ – Морса
• Номера блюд
• Странные цифры
• Число Вольстенхолма

См. также

• Интернет-энциклопедия целочисленных последовательностей
  • Список последовательностей OEIS

Ссылки

• Хэмкинс, Джоэл Дэвид; Линецкий, Дэвид; Рейтц, Йонас (2013), «Поточечно определяемые модели теории множеств», Журнал символической логики , 78 (1): 139–156, arXiv : 1105.4597 , doi : 10.2178/jsl.7801090 , S2CID   43689192 .

Внешние ссылки

• Журнал целочисленных последовательностей . Статьи находятся в свободном доступе в Интернете.