Recaman's sequence

O(n)

Recaman's sequence was introduced by Colombian mathematician Bernardo Recaman Santos and popularised by Neil Sloane's On-Line Encyclopedia of Integer Sequences (OEIS A005132). Starting at 0, each step tries to subtract the step index k; if the result is positive and not already in the sequence it succeeds (a backward jump), otherwise it adds k instead (a forward jump). Whether every positive integer eventually appears is still an open question. The sequence's zigzag pattern produces a striking visual when drawn as arcs on a number line.

Sequence
Press ▶ to run
Edit the input and press Play

How it works

  1. Set a(0) = 0.
  2. For each k, compute a(k-1) - k.
  3. Use that value if it is positive and not yet seen.
  4. Otherwise use a(k-1) + k.

Pseudocode

1recaman(n):                         # O(n)2  a ← [0],  seen ← {0}3  for k in 1..n-1:4    back ← a[k-1] - k5    if back > 0 and back ∉ seen:6      a[k] ← back                  # backward jump7    else:8      a[k] ← a[k-1] + k            # forward jump9    seen.add(a[k])10    emit a[k]