Послідовність цілих чисел

Послідовність цілих чисел — у математиці — це впорядкований список цілих чисел.

Послідовність цілих чисел можна задати в явному вигляді формулою n-го члена, або неявно, за допомогою відношення між її членами.

Наприклад, послідовність Фібоначчі (0, 1, 1, 2, 3, 5, 8, 13, …) можна задати так:

• неявно — рекурентним співвідношенням: ${\mathcal {F}}_{0}=0,~{\mathcal {F}}_{1}=1,~{\mathcal {F}}_{n+2}={\mathcal {F}}_{n+1}+{\mathcal {F}}_{n}$;
• явно — формулою Біне: ${\mathcal {F}}_{n}={\frac {(1+{\sqrt {5}})^{n}-(1-{\sqrt {5}})^{n}}{2^{n}{\sqrt {5}}}}$.

Приклади

До цілочисельних послідовностей, які отримали власні назви, належать:

• Надлишкові числа
• Послідовність Баума — Світа
• Число Белла
• Біноміальний коефіцієнт
• Число Кармайкла
• Число Каталана
• Складене число
• Недостатні числа
• Числа Ейлера
• Парні та непарні числа
• Факторіальні числа
• Послідовність Фібоначчі
• Слово Фібоначчі
• Фігурні числа
• Послідовність Ґоломба
• Щасливе число
• Високототієнтне число
• Надскладене число
• Гіпердосконале число
• Послідовність жонглера
• Послідовність Колакоскі
• Щасливе число
• Число Люка
• Число Моцкіна
• Послідовність Падована
• Розбиття числа
• Досконале число
• Напівдосконале число
• Просте число
• Псевдопросте число
• Регулярна послідовність складання паперу
• Послідовність Рудіна — Шапіро
• Напівдосконале число
• Напівпросте число
• Високонадлишкове число
• Послідовність Морзе — Туе
• Число Уляма
• Дивне число
• Число Волстенголма

Обчислювані та визна́чні послідовності

Цілочисельна послідовність є обчислюваною послідовністю, якщо існує алгоритм, який за заданим n обчислює a_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. Проте, в будь-якій моделі, що має таке відображення визна́чності, деякі цілочисельні послідовності в моделі не будуть визна́чними відносно моделі (Hamkins et al. 2013).

Якщо M містить всі цілочисельні послідовності, то множина цілочисельних послідовностей, визначених в M, існуватиме в M і буде зліченною і зліченною в M.

Повні послідовності

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

Див. також

• Енциклопедія послідовностей цілих чисел
• Список послідовностей OEIS

Література

• Hamkins, Joel David; Linetsky, David; Reitz, Jonas (2013), Pointwise Definable Models of Set Theory, Journal of Symbolic Logic, 78 (1): 139—156, arXiv:1105.4597, doi:10.2178/jsl.7801090.

Посилання

• Journal of Integer Sequences [Архівовано 23 травня 2013 у Wayback Machine.]. Статті доступні в Інтернеті.