Integer sequence

In mathematics, an integer sequence is a sequence (i.e., an ordered list) of integers.

An integer sequence may be specified explicitly by giving a formula for its nth term, or implicitly by giving a relationship between its terms. For example, the sequence 0, 1, 1, 2, 3, 5, 8, 13, … (the 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. The sequence 0, 3, 8, 15, … is formed according to the formula n² − 1 for the nth 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, even though we do not have a formula for the nth perfect number.

Examples

Integer sequences which have received their own name include:

• Abundant numbers
• Baum–Sweet sequence
• Bell numbers
• Binomial coefficients
• Carmichael numbers
• Catalan numbers
• Composite numbers
• Deficient numbers
• Euler numbers
• Even and odd numbers
• Factorial numbers
• Fibonacci numbers
• Fibonacci word
• Figurate numbers
• Golomb sequence
• Happy numbers
• Highly totient numbers
• Highly composite numbers
• Home primes
• Hyperperfect numbers
• Juggler sequence
• Kolakoski sequence
• Lucky numbers
• Lucas numbers
• Motzkin numbers
• Padovan numbers
• Partition numbers
• Perfect numbers
• Pseudoperfect numbers
• Prime numbers
• Pseudoprime numbers
• Regular paperfolding sequence
• Rudin–Shapiro sequence
• Semiperfect numbers
• Semiprime numbers
• Superperfect numbers
• Thue–Morse sequence
• Ulam numbers
• Weird numbers

Computable and definable sequences

An integer sequence is a computable sequence if there exists an algorithm which, given n, calculates a_n, for all n > 0. The set of computable integer sequences is countable. The set of all integer sequences is uncountable (with cardinality equal to that of the continuum), and so not all integer sequences are computable.

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 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 jumps 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 (Hamkins et al. 2013). In general, it is not possible to form within ZFC the set of definable sequences, or to form a map from the set of formulas that define integer sequences to the integer sequences they define. However, in any model that does possess such a definability map, not all integer sequences in the model are definable relative to the model (Hamkins et al. 2013).

Complete sequences

An integer sequence 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.

See also

• On-Line Encyclopedia of Integer Sequences
  • List of OEIS sequences

References

• 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.

External links

• Journal of Integer Sequences. Articles are freely available online.