Editing Integer sequence

{{short description|Ordered list of whole numbers}}
[[File:Goteborg ciag Fibonacciego.jpg|thumb|Beginning of the [[Fibonacci number|Fibonacci sequence]] on a building in [[Gothenburg]]]]
In [[mathematics]], an '''integer sequence''' is a [[sequence]] (i.e., an ordered list) of [[integer]]s.

An integer sequence may be specified ''explicitly'' by giving a formula for its ''n''th term, or ''implicitly'' by giving a relationship between its terms. For example, the sequence 0, 1, 1, 2, 3, 5, 8, 13,&nbsp;... (the [[Fibonacci number|Fibonacci sequence]]) is formed by starting with 0 and 1 and then adding any two consecutive terms to obtain the next one: an implicit description {{OEIS|id=A000045}}. The sequence 0, 3, 8, 15,&nbsp;... is formed according to the formula ''n''<sup>2</sup>&nbsp;&minus;&nbsp;1 for the ''n''th term: an explicit definition.

Alternatively, an integer sequence may be defined by a property which members of the sequence possess and other integers do not possess. For example, we can determine whether a given integer is a [[perfect number]], {{OEIS|id=A000396}}, even though we do not have a formula for the ''n''th perfect number.

==Computable and definable sequences==
An integer sequence is '''[[computable function|computable]]''' if there exists an algorithm that, given ''n'', calculates ''a''<sub>''n''</sub>, for all ''n'' &gt; 0. The set of computable integer sequences is [[countable]]. The set of all integer sequences is [[uncountable]] (with [[cardinality]] equal to [[beth one|that of the continuum]]), and so not all integer sequences are computable.

Although some integer sequences have definitions, there is no systematic way to define what it means for an integer sequence to be definable in the universe or in any absolute (model independent) sense.

Suppose the set ''M'' is a [[transitive model]] of [[ZFC set theory]]. The transitivity of M implies that the integers and integer sequences inside M are actually integers and sequences of integers. An integer sequence is a '''[[definable set|definable]] sequence relative to ''M''''' if there exists some formula ''P''(''x'') in the language of set theory, with one free variable and no parameters, which is true in ''M'' for that integer sequence and false in ''M'' for all other integer sequences. In each such ''M'', there are definable integer sequences that are not computable, such as sequences that encode the [[Turing jump]]s of computable sets.

For some transitive models ''M'' of ZFC, every sequence of integers in ''M'' is definable relative to ''M''; for others, only some integer sequences are. There is no systematic way to define in ''M'' itself the set of sequences definable relative to ''M'' and that set may not even exist in some such ''M''. Similarly, the map from the set of formulas that define integer sequences in ''M'' to the integer sequences they define is not definable in ''M'' and may not exist in ''M''. However, in any model that does possess such a definability map, some integer sequences in the model will not be definable relative to the model.{{sfn|Hamkins|Linetsky|Reitz|2013}}

If ''M'' contains all integer sequences, then the set of integer sequences definable in ''M'' will exist in ''M'' and be countable and countable in ''M''.

==Complete sequences==
A sequence of positive integers is called a [[complete sequence]] if every positive integer can be expressed as a sum of values in the sequence, using each value at most once.

==Examples==
Integer sequences that have their own name include:
{{Div col|colwidth=20em}}
*[[Abundant number]]s
*[[Baum–Sweet sequence]]
*[[Bell number]]s
*[[Binomial coefficient]]s
*[[Carmichael number]]s
*[[Catalan number]]s
*[[Composite number]]s
*[[Deficient number]]s
*[[Euler number]]s
*[[Even and odd numbers]]
*[[Factorial]] numbers
*[[Fibonacci number]]s
*[[Fibonacci word]]
*[[Figurate numbers]]
*[[Golomb sequence]]
*[[Happy number]]s
*[[Highly composite number]]s
*[[Highly totient number]]s
*[[Home prime]]s
*[[Hyperperfect number]]s
*[[Juggler sequence]]
*[[Kolakoski sequence]]
*[[Lucky number]]s
*[[Lucas number]]s
*[[Motzkin number]]s
*[[Natural number]]s
*[[Padovan sequence|Padovan number]]s
*[[Partition number]]s
*[[Perfect number]]s
*[[Practical number]]s
*[[Prime number]]s
*[[Pseudoprime]] numbers
*[[Recamán's sequence]]
*[[Regular paperfolding sequence]]
*[[Rudin–Shapiro sequence]]
*[[Semiperfect number]]s
*[[Semiprime]] numbers
*[[Superperfect number]]s
*[[Triangular number]]s
*[[Thue–Morse sequence]]
*[[Ulam numbers]]
*[[Weird number]]s
*[[Wolstenholme number]]
{{Div col end}}

==See also==
* [[Constant-recursive sequence]]
* [[On-Line Encyclopedia of Integer Sequences]]
** [[List of OEIS sequences]]

==References==
{{reflist}}
* {{citation |last1=Hamkins |first1=Joel David |last2=Linetsky |first2=David|last3=Reitz |first3=Jonas |title=Pointwise Definable Models of Set Theory |arxiv=1105.4597 |journal=[[Journal of Symbolic Logic]] |volume=78 |issue=1 |pages=139–156 |year=2013 |doi=10.2178/jsl.7801090 |s2cid=43689192}}.

==External links==
*[https://cs.uwaterloo.ca/journals/JIS/ Journal of Integer Sequences]. Articles are freely available online.

{{Series (mathematics)}}
{{Authority control}}

[[Category:Integer sequences| ]]
[[Category:Arithmetic functions]]