Divisibility sequence
Encyclopedia
In mathematics, a divisibility sequence is an integer sequence
such that for all natural numbers m, n,
i.e., whenever one index is a multiple of another one, then the corresponding term also is a multiple of the other term. The concept can be generalized to sequences with values in any ring
where the concept of divisibility is defined.
A strong divisibility sequence is an integer sequence such that for all natural numbers m, n,
Note that a strong divisibility sequence is immediately a divisibility sequence; if , immediately . Then by the strong divisibility property, and therefore .
Integer sequence
In mathematics, an integer sequence is a sequence 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...
such that for all natural numbers m, n,
i.e., whenever one index is a multiple of another one, then the corresponding term also is a multiple of the other term. The concept can be generalized to sequences with values in any ring
Ring (mathematics)
In mathematics, a ring is an algebraic structure consisting of a set together with two binary operations usually called addition and multiplication, where the set is an abelian group under addition and a semigroup under multiplication such that multiplication distributes over addition...
where the concept of divisibility is defined.
A strong divisibility sequence is an integer sequence such that for all natural numbers m, n,
Note that a strong divisibility sequence is immediately a divisibility sequence; if , immediately . Then by the strong divisibility property, and therefore .
Examples
- Any constant sequence is a divisibility sequence.
- Every sequence of the form , for some nonzero integer k, is a divisibility sequence.
- Every sequence of the form for integers is a divisibility sequence.
- The Fibonacci numbers F = (0, 1, 1, 2, 3, 5, 8,...) form a strong divisibility sequence.
- Elliptic divisibility sequenceElliptic divisibility sequenceIn mathematics, an elliptic divisibility sequence is a sequence of integers satisfying a nonlinear recursion relation arising from division polynomials on elliptic curves. EDS were first defined, and their arithmetic properties studied, by Morgan Ward...
s are another class of such sequences.
External links
- Some divisibility sequences listed in the On-line Encyclopedia of Integer SequencesOn-Line Encyclopedia of Integer SequencesThe On-Line Encyclopedia of Integer Sequences , also cited simply as Sloane's, is an online database of integer sequences, created and maintained by N. J. A. Sloane, a researcher at AT&T Labs...
.