Recamánova posloupnost

O(n)

Recamánovu posloupnost zavedl kolumbijský matematik Bernardo Recaman Santos a proslavil ji Neil Sloane v encyklopedii celých čísel OEIS (A005132). Začínáme od 0 a na každém kroku zkusíme odečíst index k; pokud je výsledek kladný a dosud se v posloupnosti nevyskytl, skok zpět se provede, jinak přičteme k. Otázka, zda se v posloupnosti nakonec vyskytne každé kladné celé číslo, je stále otevřená. Klikatý vzor posloupnosti vytváří působivý vizuál při zobrazení jako oblouky na číselné přímce.

Posloupnost
Stiskni ▶ a spusť
Uprav vstup a stiskni Přehrát

Jak to funguje

  1. Nastav a(0) = 0.
  2. Pro každé k vypočti a(k-1) - k.
  3. Použij tuto hodnotu, je-li kladná a dosud nepoužitá.
  4. Jinak použij a(k-1) + k.

Pseudokód

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]