# Integer sequence

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

An integer sequence may be specified explicitly by giving a formula for its nth term, or implicitly by giving a relationship between its terms. Integer sequence_sentence_1

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. Integer sequence_sentence_2

The sequence 0, 3, 8, 15, ... is formed according to the formula n − 1 for the nth term: an explicit definition. Integer sequence_sentence_3

Alternatively, an integer sequence may be defined by a property which members of the sequence possess and other integers do not possess. Integer sequence_sentence_4

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. Integer sequence_sentence_5

## Examples Integer sequence_section_0

Integer sequences that have their own name include: Integer sequence_sentence_6

## Computable and definable sequences Integer sequence_section_1

An integer sequence is a computable sequence if there exists an algorithm which, given n, calculates an, for all n > 0. Integer sequence_sentence_7

The set of computable integer sequences is countable. Integer sequence_sentence_8

The set of all integer sequences is uncountable (with cardinality equal to that of the continuum), and so not all integer sequences are computable. Integer sequence_sentence_9

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. Integer sequence_sentence_10

Suppose the set M is a transitive model of ZFC set theory. Integer sequence_sentence_11

The transitivity of M implies that the integers and integer sequences inside M are actually integers and sequences of integers. Integer sequence_sentence_12

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. Integer sequence_sentence_13

In each such M, there are definable integer sequences that are not computable, such as sequences that encode the Turing jumps of computable sets. Integer sequence_sentence_14

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. Integer sequence_sentence_15

2013). Integer sequence_sentence_16

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 (Hamkins et al. Integer sequence_sentence_17

2013). Integer sequence_sentence_18

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. Integer sequence_sentence_19

## Complete sequences Integer sequence_section_2

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. Integer sequence_sentence_20