Seqüència de Recamán

Representació de la seqüència de Recamán sobre l'eix horitzontal, amb els salts indicats a la part posterior i inferior alternadament. En blau els salts que avancen, en vermell els que tornen enrere.

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.

La seqüència de Recamán es pot consultar a l'OEIS A005132

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

Definició

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

$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:

$R_{n}\geq 0$

$|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.

Variants

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.

Versió amb constant definida

$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 $K$ és un valor constant. El resultat és molt similar a la seqüència original.

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

Transformació iterativa

$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 $i$ és el primer nombre major o igual a 0 al qual $R_{n-1}+n+i$ encara no ha aparegut.

Podeu consultar a l'OEIS d'aquesta versió a A064387

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

$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}}$

Podeu consultar a l'OEIS d'aquesta versió a A064388

Transformació permutativa

$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 $k$ és 1, i es reinicia per cada $R_{n}$ nova a definir. Per cada iteració (transformar i repetir), $k$ augmenta 1 i es torna a provar, fins que finalment es pot definir $R_{n}$.

Podeu consultar a l'OEIS d'aquesta versió a A064389 i una versió permutativa similar amb l'ús de ${\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ó.

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

Combinació amb altres funcions

$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 $f(n)$ és una funció descrita, per exemple el quadrat $n^{2}$ o l'n-èssim nombre primer $p(n)$.

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

Per la funció $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.

$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 $m=n$ a A079053 i amb $m=1$ a A091484

Versió amb paritat acumulativa

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ó:

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

on la paritat $c(i)$ en cada cas es defineix:

$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ó $p(i)$ a A022831

Enllaços externs

• 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)