Sucesión de Recamán

Estudiamos hoy una original sucesión que Bernardo Recamán Santos envió a N. J. A. Sloane en 1991 para su colección, y que desde entonces ha originado múltiples desarrollos, incluso musicales (ver https://www.youtube.com/watch?v=h3qEigSSuF0).

Su definición es la siguiente (versión con a₁=1):

a₁=1
a_n = a_n-1 – n, si este valor es positivo y no figura ya en la sucesión
a_n = a_n-1 + n, en caso contrario.

Sus primeros términos son: 1, 3, 6, 2, 7, 13, 20, 12, 21, 11, 22, 10, 23, 9, 24, 8, 25, 43, 62, 42, 63, 41, 18, 42, 17, 43, 16, 44, 15, 45, 14, 46, 79, 113, 78, 114, 77, 39, 78, 38, 79, 37, 80, 36, 81, 35, 82, 34, 83, 33, 84, 32, 85, 31, 86, 30, 87, 29, 88, 28, 89, 27, 90, 26, 91, 157,… (existe otra versión que comienza en 0, idéntica a esta en todo lo demás http://oeis.org/A005132)

El punto clave, y que nos permitirá estudiar su programación con hoja de cálculo es el de no figura ya en la sucesión, pues esto obliga a mantener en memoria un registro de los valores anteriores ¿Cómo solucionarlo en una hoja de cálculo? Intentaremos varias posibilidades.

Desarrollo de la sucesión mediante celdas

Las celdas de una hoja sirven de memoria en cualquier proceso, por lo que comenzaremos el estudio por ahí. En la imagen verás la formación de la sucesión de Recaman en la columna E, junto a otra auxiliar D que hemos añadido por simple comodidad:

La columna D contiene, simplemente, la diferencia a_n-1 – n, que se obtiene con las expresiones =E2-FILA(),=E3-FILA(),=E4-FILA(),…aprovechando la función FILA, que aquí representará el valor de n en la definición. Por eso hemos creado la sucesión a partir de la primera fila. Si ese valor en la columna D es positivo y no ha salido ya, será el valor del siguiente término de la sucesión. Por eso no extrañará que algunos de estos valores figuren en la columna E que estudiaremos a continuación.
En dicha columna E hemos construido una fórmula un poco compleja. Esta es la correspondiente a la celda E3:

=SI(Y(D3>0;CONTAR.SI(E$1:E2;D3)=0);D3;FILA()+E2)

Recuerda que D3 contiene a_n-1 – n, que en este caso sería  a₂ – 2.

La fórmula comienza con un SI, puesto que la definición se basa en una alternativa. Después una Y, ya que existen dos condiciones: una que D3 sea positiva, y otra que no figure ya en la columna E. La primera se resuelve con D3>0 y la segunda con CONTAR.SI(E$1:E2;D3)=0. Usamos CONTAR.SI para ver si D3 ha salido ya. Si el CONTAR da cero, es que no ha salido, y se admite. Observa que se busca desde la primera celda E$1 (referencia absoluta) hasta la anterior E2.

Si ambas condiciones se cumplen, la función SI devuelve D3, como era de esperar, y, en caso contrario, FILA()+E2, es decir, a_n-1 + n.

Rellenando esta fórmula hacia abajo obtendremos la sucesión hasta el término que deseemos. Lo hemos efectuado hasta 2000 términos, para crear un gráfico similar al que figura en las publicaciones que tratan esta sucesión, en este caso de tipo lineal:

Llaman la atención en el mismo las fuertes oscilaciones que se producen en algunos intervalos, en los que los términos sufren incrementos alternativamente positivos y negativos, como en este:

En este tramo, las diferencias positivas decrecen de uno en uno y las negativas de tres en tres.
Si hubiésemos usado un gráfico de dispersión entre n y a_n obtendríamos

Pertenencia de todos los enteros positivos

N. J. A. Sloane conjeturó que cualquier entero positivo terminará apareciendo en la sucesión, y de hecho, estas son las posiciones en las que figuran los primeros términos: 1, 4, 2, 131, 129, 3, 5, 16, 14, 12, 10, 8, 6, 31, 29, 27, 25, 23, 99734, 7, 9, 11, 13, 15, 17, 64, 62, 60, 58, 56,… https://oeis.org/A057167

Nosotros podemos construir esta sucesión con la función COINCIDIR. Observa la imagen:

Se han reproducido los valores de las posiciones de 1, 2, 3,… salvo la del 19, que al ser 99734 excedía nuestro ámbito de estudio. Como uno de los objetivos de este documento es el aprendizaje de las técnicas de la hoja de cálculo, reproducimos la fórmula usada. La columna F contiene los primeros números naturales, y recuerda que E contiene la sucesión. Bastará, pues, usar la función COINCIDIR, para ver si el número dado figura o no en la sucesión, y en qué posición, que es lo que nos devuelve esa función COINCIDIR. Por ejemplo, para el 5 usamos esta fórmula: =COINCIDIR(F5;E$1:E$2000;0). En ella F5 es el valor 5 y E$1:E$2000 el rango de búsqueda (hemos llegado a 2000 elementos). El 0 final indica que buscamos valores exactos, y la función nos devuelve 129, que es la posición en la que aparece el 5, como puedes ver en este recorte de la tabla:

En ella también aparece el 131, número de orden del 4.

Si hubiéramos creado una tabla de muchos más términos terminaríamos por encontrar en ella todos los números naturales. Eso es lo que conjetura Sloane.

Función RECAMAN(n)

El desarrollo anterior puede ser más o menos interesante, pero, como hemos procedido en casos parecidos, sería muy útil obtener un valor de la sucesión por cálculo directo (en realidad, en su interior sería recursivo), de forma que dado un número de orden, existiera una función que nos devolviera el término correspondiente de la sucesión de Recaman. Esto choca con el mismo inconveniente que en el caso del cálculo progresivo, y es el almacenamiento de los valores anteriores. Esa función debería contener un vector o tabla que memorizara dichos valores. En el Basic de las hojas de cálculo no existe un dimensionamiento dinámico de un vector en función de n, por lo que no sería práctico. Por ello hemos pensado almacenar los valores previos en un string o cadena de caracteres, que crece dinámicamente sin problemas.

La función cuya codificación presentamos ahora almacena los valores previos de la sucesión en el string prev$, pero para que no se den ambigüedades, rodea cada número de dos almohadillas #, es decir, almacenamos un 12 como #12#, para evitar que se confunda con 112, que sería #112# en nuestro sistema. Es un truco que nos evitará muchos problemas. También deberemos suprimir el espacio en blanco que las hojas añaden a los números, pues, si no, el 12 se podría codificar como # 12# y no ser detectado. Este cambio lo efectuará la función AJUSTA, que es la siguiente (quien no tenga interés en esto puede pasar a la función principal):

Public Function ajusta(a$) As String
If Mid(a$, 1, 1) = " " Then a$ = Right$(a$, Len(a$) - 1)
ajusta = "#" + a$ + "#"
End Function

Disponiendo de esta función auxiliar ya podemos describir la función RECAMAN(n). Es esta:

Public Function recaman(n)
Dim prev$, sd$
Dim d, ant, reca, i

prev$ = " #1# "
ant = 1   ‘Inicia los valores de la sucesión de Recaman

If n = 1 Then
reca = 1 ‘Caso en el que n=1
Else

For i = 2 To n
d = ant – i ‘Calculamos la diferencia a_n-1 – n

If d > 0 Then
sd$ = ajusta(Str$(d)) ‘Si la diferencia es positiva, vemos si ya figura en la sucesión
If InStr(prev$, sd$) = 0 Then ‘Usamos InStr para ver si la diferencia figura en el string
reca = d ‘Si no está, la admitimos como nuevo valor
Else
reca = ant + i ‘Si ya figura en la sucesión, usamos la definición alternativa
End If
Else
reca = ant + i ‘Si es negativa, también usamos la definición alternativa
End If

sd$ = Str$(reca) ‘Incorporamos el nuevo término al string que los recuerda
prev = prev + ajusta(sd$)
ant = reca
Next i

End If
recaman = reca
End Function

Copia, si así lo deseas, estas dos funciones en tu hoja de cálculo, y así podrás jugar un poco con esta sucesión. Por ejemplo, puedes descubrir estas curiosidades o ampliarlas:

Elementos repetidos

El primer caso de términos repetidos en la sucesión de Recaman es el 42, que aparece en el índice 20 y en el 24: recaman(20)=recaman(24)=42. Dado un término, no es difícil encontrar el siguiente con el mismo valor. Hemos señalado que el primer repetido es el 42, en los lugares 20 y 24 Dado otro valor, ¿existirá otro con el mismo valor?¿cuál será la siguiente aparición?
Esta cuestión y otras parecidas podemos resolverla con esta función:

Public Function sig_recaman(indi)
Dim v, j, v1

v = recaman(indi)
j = indi
v1 = 0
While v <> v1
j = j + 1
v1 = recaman(j)
Wend
sig_recaman = j
End Function

En ella, dado un número de orden, se busca la siguiente aparición del término correspondiente a ese número de orden. Se le incluye un tope de 10^4  para evitar el bloqueo de la función. Como esta última situación es la más frecuente, sólo destacaremos los casos contenidos en http://oeis.org/A064284
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1,…

En ellos se descubre que repeticiones hay pocas, y casi siempre de sólo dos elementos. Con nuestra función sig_recaman se pueden comprobar algunas:

Recaman(20)=recaman(24)=42

Otros casos tardan mucho en aparecer y no merece la pena seguir por este camino.

Términos iguales a su número de orden

También existen muy pocos. Se puede plantear que recaman(n)=n y ver qué pasa. Sólo encontraremos recaman(1)=1, recaman(1520)=1520, recaman(9317)=9317 y alguno más. Los demás, si existen, sobrepasan nuestra capacidad de cálculo, ya que pertenecerían a esta sucesión

http://oeis.org/A064568

3, 11, 21, 39, 76, 248, 844, 1520, 2752, 9317, 17223, 31221, 57071, 99741, 589932, 58056875, en los que el término es múltiplo del número de orden.

El mismo caso, pero con una unidad de diferencia

¿Pueden ser n y recaman(n) número consecutivos en cualquiera de los dos sentidos?
Podemos plantear la condición ABS(RECAMAN(N)-N)=1 y hemos encontrado recaman(2)=3 y recaman(10)=11. Entre los números menores que 3000 no hay más.

A continuación incluimos la tabla de los números N menores que 1000 cuya diferencia con RECAMAN(N) es menor que 10

Una vez que tienes a tu disposición la función RECAMAN puedes emprender tus propias búsquedas.