Послідовність Рекамана: Одна Лінія, Що Виглядає Як Хаос

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]);
}

Understanding the simulation

The simulation displays the sequence of numbers generated by the algorithm. Each number is represented as a semicircular arc above or below the number line, depending on whether it’s an addition or subtraction. The arcs overlap to represent the collisions that the algorithm is checking for.

When a candidate subtraction would revisit a number already covered by an earlier arc, the rule is forced to add instead. This can be observed as the arcs avoid crossing back onto themselves in real time, generation by generation.

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.

Чому математики продовжують вивчати таку просту річ

Послідовність Рекамана займає невелику, але популярну родину «простих жадібних правил, непередбачуваного виводу» цілих чисел, поряд з такими речами, як послідовність EKG та послідовність Улама, які цікаві саме тому, що одностроковий рекурсивний визначення породжує відкриті математичні питання. Ніхто не довів конвеєрну гіпотезу, ніхто не має закриття формули для a(n), і статистику росту та прогалин вивчають емпірично, генеруючи мільярди термінів і шукаючи закономірності — що є справедливим описом того, як більшу частину теорії чисел виглядало до доведення, і нагадує, що «легко визначити» та «легко зрозуміти» - це дуже різні властивості.

Frequently asked questions

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте Recaman's Sequence і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.