mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...

, an integer sequence is a

sequence In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is called ...

(i.e., an ordered list) of

integer An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign ( −1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the languag ...

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, ... (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 ''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 In number theory, a perfect number is a positive integer that is equal to the sum of its positive divisors, excluding the number itself. For instance, 6 has divisors 1, 2 and 3 (excluding itself), and 1 + 2 + 3 = 6, so 6 is a perfect number. ...

, even though we do not have a formula for the ''n''th perfect number.

Examples

Integer sequences that have their own name include: * Abundant numbers * Baum–Sweet sequence * Bell numbers *

Binomial coefficient In mathematics, the binomial coefficients are the positive integers that occur as coefficients in the binomial theorem. Commonly, a binomial coefficient is indexed by a pair of integers and is written \tbinom. It is the coefficient of the t ...

s * Carmichael numbers * Catalan numbers *

Composite number A composite number is a positive integer that can be formed by multiplying two smaller positive integers. Equivalently, it is a positive integer that has at least one divisor In mathematics, a divisor of an integer n, also called a factor ...

s * Deficient numbers * Euler numbers *

Even and odd numbers In mathematics, parity is the property of an integer of whether it is even or odd. An integer is even if it is a multiple of two, and odd if it is not.. For example, −4, 0, 82 are even because \begin -2 \cdot 2 &= -4 \\ 0 \cdot 2 &= 0 \\ 41 ...

Factorial In mathematics, the factorial of a non-negative denoted is the product of all positive integers less than or equal The factorial also equals the product of n with the next smaller factorial: \begin n! &= n \times (n-1) \times (n-2) \ ...

numbers * Fibonacci numbers * Fibonacci word * Figurate numbers *

Golomb sequence In mathematics, the Golomb sequence, named after Solomon W. Golomb (but also called Silverman's sequence), is a monotonically increasing integer sequence where ''an'' is the number of times that ''n'' occurs in the sequence, starting with ''a''1 ...

* Happy numbers * Highly composite numbers *

Highly totient number A highly totient number k is an integer that has more solutions to the equation \phi(x) = k, where \phi is Euler's totient function, than any integer below it. The first few highly totient numbers are 1, 2, 4, 8, 12, 24, 48, 72, 144, 240, 4 ...

s * Home primes * Hyperperfect numbers * Juggler sequence * Kolakoski sequence *

Lucky number In number theory, a lucky number is a natural number in a set which is generated by a certain "sieve". This sieve is similar to the Sieve of Eratosthenes that generates the primes, but it eliminates numbers based on their position in the rema ...

s * Lucas numbers * Motzkin numbers *

Natural number In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country"). Numbers used for counting are called '' cardinal ...

s * Padovan numbers *

Partition number In number theory, the partition function represents the number of possible partitions of a non-negative integer . For instance, because the integer 4 has the five partitions , , , , and . No closed-form expression for the partition function i ...

s *

Perfect number In number theory, a perfect number is a positive integer that is equal to the sum of its positive divisors, excluding the number itself. For instance, 6 has divisors 1, 2 and 3 (excluding itself), and 1 + 2 + 3 = 6, so 6 is a perfect number. ...

s *

Prime number A prime number (or a prime) is a natural number greater than 1 that is not a Product (mathematics), product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime ...

s * Pseudoprime numbers * Recamán's sequence * Regular paperfolding sequence * Rudin–Shapiro sequence * Semiperfect numbers *

Semiprime In mathematics, a semiprime is a natural number that is the product of exactly two prime numbers. The two primes in the product may equal each other, so the semiprimes include the squares of prime numbers. Because there are infinitely many prime ...

numbers *

Superperfect number In mathematics, a superperfect number is a positive integer ''n'' that satisfies :\sigma^2(n)=\sigma(\sigma(n))=2n\, , where σ is the divisor summatory function. Superperfect numbers are a generalization of perfect numbers. The term was coine ...

s *

Thue–Morse sequence In mathematics, the Thue–Morse sequence, or Prouhet–Thue–Morse sequence, is the binary sequence (an infinite sequence of 0s and 1s) obtained by starting with 0 and successively appending the Boolean complement of the sequence obtained thus ...

* Ulam numbers * Weird numbers *

Wolstenholme number A Wolstenholme number is a number that is the numerator of the generalized harmonic number ''H'n'',2. The first such numbers are 1, 5, 49, 205, 5269, 5369, 266681, 1077749, ... . These numbers are named after Joseph Wolstenholme, who prove ...

Computable and definable sequences

An integer sequence is a

computable Computability is the ability to solve a problem in an effective manner. It is a key topic of the field of computability theory within mathematical logic and the theory of computation within computer science. The computability of a problem is clos ...

sequence if there exists an algorithm which, given ''n'', calculates ''a''_''n'', for all ''n'' > 0. The set of computable integer sequences is

countable In mathematics, a set is countable if either it is finite or it can be made in one to one correspondence with the set of natural numbers. Equivalently, a set is ''countable'' if there exists an injective function from it into the natural numbers ...

. The set of all integer sequences is uncountable (with

cardinality In mathematics, the cardinality of a set is a measure of the number of elements of the set. For example, the set A = \ contains 3 elements, and therefore A has a cardinality of 3. Beginning in the late 19th century, this concept was generalized ...

equal to 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 In mathematical set theory, a transitive model is a model of set theory that is standard and transitive. Standard means that the membership relation is the usual one, and transitive means that the model is a transitive set or class. Examples *An ...

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). 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. 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 In mathematics, a sequence of natural numbers 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. For example, the sequence of powers of two (1, 2, 4, 8, ...), ...

if every positive integer can be expressed as a sum of values in the sequence, using each value at most once.

References

* .

External links

Journal of Integer Sequences
Articles are freely available online. {{Series (mathematics) Arithmetic functions

Examples

Computable and definable sequences

Complete sequences

See also

References

External links