Recamán's sequence ($r(0)=0,r(n)=r(n-1)\pm n$)

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.