Recaman's Sequence: A One-Line Rule That Looks Like Chaos

A greedy rule that looks random and isn't

Recamán's sequence starts at a(0) = 0, and every subsequent term follows one greedy rule: try subtracting n from the previous term first; if the result is positive and hasn't appeared anywhere earlier in the sequence, take it; otherwise add n instead. It's named for the Colombian mathematician Bernardo Recamán Santos and popularised by Neil Sloane and OEIS (it's sequence A005132, one of the most-viewed entries in the entire database). Despite the simplicity of the rule, the resulting sequence of numbers looks close to erratic — jumping unpredictably up and down — and visualising it as arcs makes the structure of that apparent randomness visible.

a[0] = 0;
seen = new Set([0]);
for (let n = 1; n <= N; n++) {
  const back = a[n-1] - n;
  if (back > 0 && !seen.has(back)) {
    a[n] = back;               // subtract, if it's new and positive
  } else {
    a[n] = a[n-1] + n;          // otherwise add
  }
  seen.add(a[n]);
}

Reading the arcs

Drawing each step as a semicircular arc connecting a(n−1) to a(n) — above the number line for an addition, below it for a subtraction — turns the raw sequence of numbers into the picture this simulation animates. The visual is not just decorative: the overlapping arcs are exactly the collisions the algorithm is checking for. Whenever a candidate subtraction would revisit a number already covered by an earlier arc, the rule is forced to add instead, and you can watch the arcs literally avoid crossing back onto themselves in the picture, generation by generation, in real time.

Why it never gets stuck, and whether every number appears

A subtlety of the rule is that it only forbids repeats, not gaps — the sequence is free to skip over numbers it never lands on directly, as long as it doesn't land on the same number twice. It is conjectured, and verified computationally for enormous ranges (well past 10^11 terms), that every non-negative integer eventually appears in the sequence, but this is not proven for all n. What is known is that the sequence keeps finding fresh territory largely by subtracting when it safely can, since going down revisits smaller numbers less often than a long run of only-adds would leave behind, and gaps that do appear tend to get filled in later, sometimes tens of thousands of steps afterward.

The arithmetic of when subtraction is forced to fail

Because a(n−1) − n must stay positive to even be considered, the subtraction branch becomes unavailable whenever n grows large relative to the current term — for n > a(n−1), subtracting would go negative, so the rule is forced onto pure addition for a stretch. Long addition runs push the sequence up quickly (each add is +n, so consecutive adds compound like a partial sum of n, n+1, n+2, …), which is exactly what refills the "budget" needed for later subtractions to become legal again once n has grown enough to exceed the accumulated value. This tug-of-war between forced addition runs and opportunistic subtraction is the real source of the sequence's visually erratic zig-zag.

Why mathematicians still study something this simple

Recamán's sequence sits in a small, popular family of "simple greedy rule, unpredictable output" integer sequences, alongside things like the EKG sequence and Ulam's sequence, that are interesting precisely because a one-line recursive definition produces open mathematical questions. Nobody has proven the every-integer-eventually-appears conjecture, nobody has a closed-form formula for a(n), and the growth rate and gap statistics are studied empirically by generating billions of terms and looking for patterns — which is a fair description of what most of number theory looked like before proof, and a reminder that "simple to define" and "simple to understand" are very different properties.

Frequently asked questions

Try it live

Everything above runs in your browser — open Recaman's Sequence and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.