Integer sequence
Encyclopedia
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 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 n2 − 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.
sequence, if there exists an algorithm which given n, calculates an, for all n > 0. An integer sequence is a definable
sequence, if there exists some statement P(x) which is true for that integer sequence x and false for all other integer sequences. The set of computable integer sequences and definable integer sequences are both countable, with the computable sequences a proper subset of the definable sequences (in other words, some sequences are definable but not computable). The set of all integer sequences is uncountable (with cardinality equal to that of the continuum); thus, almost all integer sequences are uncomputable and cannot be defined.
if every positive integer can be expressed as a sum of values in the sequence, using each value at most once.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, an integer sequence is a sequence
Sequence
In mathematics, a sequence is an ordered list of objects . Like a set, it contains members , and the number of terms is called the length of the sequence. Unlike a set, order matters, and exactly the same elements can appear multiple times at different positions in the sequence...
(i.e., an ordered list) of integer
Integer
The integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...
s.
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 n2 − 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
Perfect number
In number theory, a perfect number is a positive integer that is equal to the sum of its proper positive divisors, that is, the sum of its positive divisors excluding the number itself . Equivalently, a perfect number is a number that is half the sum of all of its positive divisors i.e...
, even though we do not have a formula for the nth perfect number.
Computable and definable sequences
An integer sequence is a computableRecursion theory
Computability theory, also called recursion theory, is a branch of mathematical logic that originated in the 1930s with the study of computable functions and Turing degrees. The field has grown to include the study of generalized computability and definability...
sequence, if there exists an algorithm which given n, calculates an, for all n > 0. An integer sequence is a definable
Definable set
In mathematical logic, a definable set is an n-ary relation on the domain of a structure whose elements are precisely those elements satisfying some formula in the language of that structure...
sequence, if there exists some statement P(x) which is true for that integer sequence x and false for all other integer sequences. The set of computable integer sequences and definable integer sequences are both countable, with the computable sequences a proper subset of the definable sequences (in other words, some sequences are definable but not computable). The set of all integer sequences is uncountable (with cardinality equal to that of the continuum); thus, almost all integer sequences are uncomputable and cannot be defined.
Complete sequences
An integer sequence is called a complete sequenceComplete sequence
In mathematics, 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....
if every positive integer can be expressed as a sum of values in the sequence, using each value at most once.
External links
- Journal of Integer Sequences. Articles are freely available online.
- Inductive Inference of Integer Sequences