Recamán-sorozat

A Recamán-sorozat természetes számok $a_0,a_1,a_2,...$ végtelen sorozata, amelyet a következő rekurzióval definiálunk: $a_0=0$. Ha $a_0,a_1,a_2,...,a_{n-1}$ értékét már meghatároztuk, akkor $a_n=a_{n-1}-n$ ha az így kapott szám pozitív és még nem szerepel az eddig kiszámított tagok között, különben pedig $a_n=a_{n-1}+n$. A sorozat első néhány tagja tehát 0, 1, 3, 6, 2, 7, 13, 20, 12, 21 (A005132 sorozat az OEIS-ben). A Recamán-sorozat megalkotójáról, Bernardo Recamán Santos kolumbiai matematikusról kapta a nevét.

Példák

• $a_4=2$. A következő elem meghatározásához először kiszámítjuk $a_4-5$-öt, ami -3. Mivel ez nem pozitív, $a_5=a_4+5=7$.
• $a_6$ meghatározásához kiszámítjuk $a_5-6$-ot. Ez 1, ami korábban már szerepelt a sorozatban, ezért $a_6=a_5+6=13$.
• $a_7=20$; $a_7-8=12$. Ez pozitív és még nem szerepelt a sorozatban, ezért ez a következő elem: $a_8=12$.

Szürjektivitás

Neal Sloane sejtése szerint az $n\mapsto a_n$ leképezés szürjektív, azaz minden természetes szám eleme a Recamán-sorozatnak. Benjamin Chaffin 2010. március 21-i közlése szerint a sorozat első $4,28\times 10^{73}$ tagja közül a legkisebb hiányzó természetes szám a 852 655. A leképezés nem injektív: bizonyos elemek többször is előfordulnak. A legelső ismétlődő elem a 42.