Integer sequence

An integer sequence is a sequence whose terms are integers. It can be specified by a formula, a recurrence relation, a counting interpretation or a finite computational rule. Examples include $a_n=n^2$, the Fibonacci numbers and the prime numbers.

A finite prefix does not determine a unique infinite sequence. If a polynomial matches $a_0,\dots ,a_N$, adding $c{\prod }_{j=0}^N(x-j)$ leaves those values unchanged and usually changes later ones. Identifying a sequence therefore requires its definition, indexing convention and domain, rather than a few suggestive values alone.

The integer sequence proposed by Bernardo Recamán Santos starts at zero. At step $n>0$, subtract $n$ if the result is positive and has not appeared before; otherwise add $n$. The commonly written nonnegative version gives the same sequence because zero is already present. The initial values are $0,1,3,6,2,7,13,20,\dots$. The addition branch can repeat a value: $r(20)=r(24)=42$. Avoiding a repeated subtraction is therefore not a global injectivity condition.^[ref]

Since $r(n)\le r(n-1)+n$, induction gives $0\le r(n)\le n(n+1)/2$. A prefix scan needs only constant extra storage but can take quadratic membership work. A bitset-style bounded membership table makes each lookup constant time, while its allocation cost depends on the chosen value universe. This separates the number of generated terms from the range of possible stored values.

A divisibility sequence is an integer sequence satisfying $m\mid n⟹a_m\mid a_n$, with any conventions about zero terms stated. For example $a_n=2^n-1$ has this property because if $n=km$, thenThe Fibonacci numbers also form a divisibility sequence. The stronger identity $\gcd (a_m,a_n)=|a_{\gcd (m,n)}|$ defines a strong divisibility property and does not follow from the basic implication alone. Such sequences organize common-factor questions by relationships among their indices.

A divisibility sequence associated with multiples of a point on an elliptic curve, using suitably normalized division polynomials. With $W_0=0$ and $W_1=1$, its terms satisfy the Ward identity $W_{m+n}{W}_{m-n}=W_{m+1}{W}_{m-1}{W}_n^2-W_{n+1}{W}_{n-1}{W}_m^2$. Setting nearby indices gives doubling identities, enabling logarithmic-depth evaluation.

Starting with two distinct positive integers $a<b$, repeatedly append the smallest integer larger than the previous term that is expressible in exactly one way as the sum of two distinct earlier terms. Requiring distinct summands and counting unordered pairs are both essential parts of the definition.

The nondecreasing sequence of positive integers beginning with $G(1)=1$ in which the integer $n$ occurs exactly $G(n)$ times. Its first terms are $1,2,2,3,3,4,4,4,5,5,5,\dots$. The prefix sum ${\sum }_{j=1}^{k}G(j)$ gives the last position occupied by $k$.

Terms of a sequence satisfying the third-order linear recurrence $T_{n+3}=T_n+T_{n+1}+T_{n+2}$. Initial values vary by convention; some counting problems specify $T_1=T_2=T_3=1$. To study divisibility by $m$, retain three consecutive remainders modulo $m$, a deterministic state with at most $m^3$ possibilities.