integer sequence on:
[Wikipedia]
[Google]
[Amazon]
In
Journal of Integer Sequences
Articles are freely available online. {{Authority control Arithmetic functions
In mathematics
Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...
, 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 cal ...
(i.e., an ordered list) of integer
An integer is the number zero (0), a positive natural number (1, 2, 3, ...), or the negation of a positive natural number (−1, −2, −3, ...). The negations or additive inverses of the positive natural numbers are referred to as negative in ...
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
In mathematics, the Fibonacci sequence is a Integer sequence, sequence in which each element is the sum of the two elements that precede it. Numbers that are part of the Fibonacci sequence are known as Fibonacci numbers, commonly denoted . Many w ...
) 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''2 − 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 proper divisors, that is, divisors excluding the number itself. For instance, 6 has proper divisors 1, 2 and 3, and 1 + 2 + 3 = 6, so 6 is a perfec ...
, , even though we do not have a formula for the ''n''th perfect number.
Computable and definable sequences
An integer sequence iscomputable
Computability is the ability to solve a problem by an effective procedure. 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 cl ...
if there exists an algorithm that, given ''n'', calculates ''a''''n'', for all ''n'' > 0. The set of computable integer sequences is countable
In mathematics, a Set (mathematics), set is countable if either it is finite set, 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 fro ...
. The set of all integer sequences is uncountable
In mathematics, an uncountable set, informally, is an infinite set that contains too many elements to be countable. The uncountability of a set is closely related to its cardinal number: a set is uncountable if its cardinal number is larger tha ...
(with cardinality
The thumb is the first digit of the hand, next to the index finger. When a person is standing in the medical anatomical position (where the palm is facing to the front), the thumb is the outermost digit. The Medical Latin English noun for thum ...
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 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 jump
In computability theory, the Turing jump or Turing jump operator, named for Alan Turing, is an operation that assigns to each decision problem a successively harder decision problem with the property that is not decidable by an oracle machine ...
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.
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: *Abundant number
In number theory, an abundant number or excessive number is a positive integer for which the sum of its proper divisors is greater than the number. The integer 12 is the first abundant number. Its proper divisors are 1, 2, 3, 4 and 6 for a total ...
s
*Baum–Sweet sequence
In mathematics the Baum–Sweet sequence is an infinite automatic sequence of 0s and 1s defined by the rule:
:''b'n'' = 1 if the binary representation of ''n'' contains no block of consecutive 0s of odd length;
:''b'n'' = 0 otherwise;
for ...
* 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 number
In number theory, a Carmichael number is a composite number which in modular arithmetic satisfies the congruence relation:
: b^n\equiv b\pmod
for all integers . The relation may also be expressed in the form:
: b^\equiv 1\pmod
for all integers b ...
s
*Catalan number
The Catalan numbers are a sequence of natural numbers that occur in various Enumeration, counting problems, often involving recursion, recursively defined objects. They are named after Eugène Charles Catalan, Eugène Catalan, though they were p ...
s
*Composite number
A composite number is a positive integer that can be formed by multiplying two smaller positive integers. Accordingly it is a positive integer that has at least one divisor other than 1 and itself. Every positive integer is composite, prime numb ...
s
*Deficient number
In number theory, a deficient number or defective number is a positive integer for which the sum of divisors of is less than . Equivalently, it is a number for which the sum of proper divisors (or aliquot sum) is less than . For example, th ...
s
*Euler number
Leonhard Euler ( ; ; ; 15 April 170718 September 1783) was a Swiss polymath who was active as a mathematician, physicist, astronomer, logician, geographer, and engineer. He founded the studies of graph theory and topology and made influential ...
s
*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 divisible by 2, and odd if it is not.. For example, −4, 0, and 82 are even numbers, while −3, 5, 23, and 69 are odd numbers.
The ...
*Factorial
In mathematics, the factorial of a non-negative denoted is the Product (mathematics), 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 ...
numbers
*Fibonacci number
In mathematics, the Fibonacci sequence is a Integer sequence, sequence in which each element is the sum of the two elements that precede it. Numbers that are part of the Fibonacci sequence are known as Fibonacci numbers, commonly denoted . Many w ...
s
*Fibonacci word
A Fibonacci word is a specific sequence of Binary numeral system, binary digits (or symbols from any two-letter Alphabet (formal languages), alphabet). The Fibonacci word is formed by repeated concatenation in the same way that the Fibonacci num ...
*Figurate numbers
The term figurate number is used by different writers for members of different sets of numbers, generalizing from triangular numbers to different shapes (polygonal numbers) and different dimensions (polyhedral numbers). The ancient Greek mathemat ...
*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 number
In number theory, a happy number is a number which eventually reaches 1 when the number is replaced by the sum of the square of each digit. For instance, 13 is a happy number because 1^2+3^2=10, and 1^2+0^2=1. On the other hand, 4 is not a happy ...
s
*Highly composite number
A highly composite number is a positive integer that has more divisors than all smaller positive integers. If ''d''(''n'') denotes the number of divisors of a positive integer ''n'', then a positive integer ''N'' is highly composite if ''d''(' ...
s
* Highly totient numbers
* 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 number
The Lucas sequence is an integer sequence named after the mathematician François Édouard Anatole Lucas (1842–1891), who studied both that sequence and the closely related Fibonacci sequence. Individual numbers in the Lucas sequence ar ...
s
* Motzkin numbers
*Natural number
In mathematics, the natural numbers are the numbers 0, 1, 2, 3, and so on, possibly excluding 0. Some start counting with 0, defining the natural numbers as the non-negative integers , while others start with 1, defining them as the positive in ...
s
* Padovan numbers
* Partition numbers
*Perfect number
In number theory, a perfect number is a positive integer that is equal to the sum of its positive proper divisors, that is, divisors excluding the number itself. For instance, 6 has proper divisors 1, 2 and 3, and 1 + 2 + 3 = 6, so 6 is a perfec ...
s
* Practical numbers
*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 In mathematics, the Rudin–Shapiro sequence, also known as the Golay–Rudin–Shapiro sequence, is an infinite 2- automatic sequence named after Marcel Golay, Harold S. Shapiro, and Walter Rudin, who investigated its properties.
Definition
E ...
* Semiperfect numbers
* Semiprime numbers
* Superperfect numbers
*Triangular number
A triangular number or triangle number counts objects arranged in an equilateral triangle. Triangular numbers are a type of figurate number, other examples being square numbers and cube numbers. The th triangular number is the number of dots in ...
s
*Thue–Morse sequence
In mathematics, the Thue–Morse or Prouhet–Thue–Morse sequence is the binary sequence (an infinite sequence of 0s and 1s) that can be obtained by starting with 0 and successively appending the Boolean complement of the sequence obtained thus ...
* Ulam numbers
* Weird numbers
* Wolstenholme number
See also
*Constant-recursive sequence
In mathematics, an sequence, infinite sequence of numbers s_0, s_1, s_2, s_3, \ldots is called constant-recursive if it satisfies an equation of the form
:s_n = c_1 s_ + c_2 s_ + \dots + c_d s_,
for all n \ge d, where c_i are constant (mathemat ...
* On-Line Encyclopedia of Integer Sequences
The On-Line Encyclopedia of Integer Sequences (OEIS) is an online database of integer sequences. It was created and maintained by Neil Sloane while researching at AT&T Labs. He transferred the intellectual property and hosting of the OEIS to th ...
** List of OEIS sequences
References
* .External links
Journal of Integer Sequences
Articles are freely available online. {{Authority control Arithmetic functions