Seqüència de Recamán

En matemàtiques, la seqüència de Recamán és una seqüència d'enters definida per una relació de recurrència, és a dir, cada element és definit sobre la base dels elements anteriors de la seqüència mitjançant recursivitat. Va ser descrita pel matemàtic colombià Bernardo Recamán Santos, i el matemàtic Neil Sloane (creador de la On-Line Encyclopedia of Integer Sequences, OEIS), li va posar aquest nom en honor seu.^[1]

Neil Sloane també va conjecturar que cada nombre enter apareix a la seqüència almenys una vegada, però no ha estat demostrat.^[2]

El valor inicial de la seqüència és 0. A partir d'aquest, la seqüència és definida de la següènt manera:

${\displaystyle R_{n}={\begin{cases}R_{n-1}-n&&{\text{si aquest}}>0{\text{ i si encara no es troba a }}R\\R_{n-1}+n&&{\text{en cas contrari}}\end{cases}}}$

Degut a aquesta fórmula definitòria, la seqüència satisfà dues propietats:

${\displaystyle R_{n}\geq 0}$

${\displaystyle |R_{n}-R_{n-1}|=n}$

La seqüència de Recamán no és una permutació dels nombres enters, ja que alguns nombres apareixen més d'una vegada a la seqüència.^[1]

La seqüència de Recamán ha estat la base d'un grup extens de seqüències similars, algunes d'elles amb propietats addicionals interessants.

${\displaystyle R_{n}={\begin{cases}R_{n-1}-(n+K)&&{\text{si aquest}}>0{\text{ i si encara no es troba a }}R\\R_{n-1}+(n+K)&&{\text{en cas contrari}}\end{cases}}}$

on ${\displaystyle K}$ és un valor constant. El resultat és molt similar a la seqüència original.

Podeu consultar a l'OEIS la versió amb ${\displaystyle K\!=\!-1}$ a A063733, ${\displaystyle K\!=\!1}$ a A066199 i ${\displaystyle K\!=\!2}$ a A066200

${\displaystyle R_{n}={\begin{cases}R_{n-1}-n&&{\text{si aquest}}>0{\text{ i si encara no es troba a }}R\\R_{n-1}+n+i&&{\text{en cas contrari}}\end{cases}}}$

on ${\displaystyle i}$ és el primer nombre major o igual a 0 al qual ${\displaystyle R_{n-1}+n+i}$ encara no ha aparegut.

La part interessant d'aquesta variant és que després permet afegir una variable addicional ${\displaystyle s}$ amb el qual obtenim un altre subgrup de variants. La variable ${\displaystyle s}$ té un valor inicial de 1 i augmenta ${\displaystyle 1}$ en el primer cas, o ${\displaystyle i+1}$ en el segon:

${\displaystyle R_{n}={\begin{cases}R_{n-1}-s&&{\text{si aquest}}>0{\text{ i si encara no es troba a }}R\\R_{n-1}+s+i&&{\text{en cas contrari}}\end{cases}}}$

${\displaystyle R_{n}={\begin{cases}R_{n-1}-(n+k)&&{\text{si aquest}}>0{\text{ i si encara no es troba a }}R\\R_{n-1}+(n+k)&&{\text{si aquest}}>0{\text{ i si encara no es troba a }}R\\{\mathsf {\text{(transformar i repetir)}}}&&{\text{en cas contrari }}\\\end{cases}}}$

El valor inicial de ${\displaystyle k}$ és 1, i es reinicia per cada ${\displaystyle R_{n}}$ nova a definir. Per cada iteració (transformar i repetir), ${\displaystyle k}$ augmenta 1 i es torna a provar, fins que finalment es pot definir ${\displaystyle R_{n}}$.

Podeu consultar a l'OEIS d'aquesta versió a A064389 i una versió permutativa similar amb l'ús de ${\displaystyle {\mathsf {mod}}\,n}$ a A125717

Aquesta versió s'anomena permutativa perquè no pot contenir valors repetits, i si es demostrés que tots els valors hi surten això implicaria que és una forma de reordenar tots els valors enters, i per tant es tracta d'una permutació.^[1]

Podeu consultar una versió amb ${\displaystyle kn}$ en comptes de ${\displaystyle n+k}$ a A274647

${\displaystyle R_{n}={\begin{cases}R_{n-1}-f(n)&&{\text{si aquest}}>0{\text{ i si encara no es troba a }}R\\R_{n-1}+f(n)&&{\text{en cas contrari}}\end{cases}}}$

On ${\displaystyle f(n)}$ és una funció descrita, per exemple el quadrat ${\displaystyle n^{2}}$ o l'n-èssim nombre primer ${\displaystyle p(n)}$.

Podeu consultar la versió amb ${\displaystyle n^{2}}$ a A053461 i la versió amb ${\displaystyle p(n)}$ a A064365

Per la funció ${\displaystyle f(n)}$ també s'ha utilitzat la successió de Fibonacci, però en aquest cas cal considerar no només el valor anterior en la seqüència sinó el dos anteriors.

${\displaystyle R_{n}={\begin{cases}m&&{\text{si }}n\leq 2\\R_{n-1}+R_{n-2}-F(n)&&{\text{si aquest}}>0{\text{ i si encara no es troba a }}R\\R_{n-1}+R_{n-2}+F(n)&&{\text{en cas contrari}}\end{cases}}}$

Podeu consultar a l'OEIS una versió amb ${\displaystyle m=n}$ a A079053 i amb ${\displaystyle m=1}$ a A091484

En aquest cas es fa un plantejament bastant diferent, similar al de la successió de Fibonacci amb component atzarós on es defineix la paritat en cada cas segons algun altre factor, probabilitat o funció:

${\displaystyle R_{n}=\sum _{i\rightarrow n}c(i)f(i)}$

on la paritat ${\displaystyle c(i)}$ en cada cas es defineix:

${\displaystyle c(i)={\begin{cases}1&&{\text{si }}R_{i-1}\leq f(i)\\-1&&{\text{en cas contrari}}\end{cases}}}$

Podeu consultar a l'OEIS una versió amb nombres primers, per tant amb la funció ${\displaystyle p(i)}$ a A022831

• OEIS Recaman's Sequence Output - Llista amb els primers 100000 nombres de la seqüència
• OEIS: Section Rea - Llista de seqüències relacionades i variants de la seqüència de Recamán
• Rosetta Code, Recaman's Sequence - Col·lecció de codis per recrear la seqüència en +30 llenguatges de programació (anglès)
• Weisstein, Eric W.; Wolfram Mathworld, Recaman's Sequence - Descripció de la seqüència (anglès)