viernes, 5 de octubre de 2012

Las vueltas que da el SOPFR


Ciclos en iteraciones de la función SOPFR(N)

Construye en una hoja de cálculo en la que hayas implementado la función SOPFR (ver http://hojaynumeros.blogspot.com.es/2009/11/logaritmo-entero-3.html) el siguiente esquema de cálculo. Recuerda que SOPFR suma todos los factores primos de un número contando su multiplicidad. Así, sopfr(24)=2+2+2+3=11.


















El coeficiente C y el Inicio son números enteros que puedes elegir libremente. La segunda columna rotulada como SOPFR(N) contiene dicha función aplicada a los elementos de la primera. Así, 7=SOPFR(12)=2+2+3, 20=SOPFR(51)=3+17,…

Los demás elementos de la primera columna se construyen multiplicando el anterior de la segunda por el coeficiente y sumando después 1. Por ejemplo, 36=7*5+1, 506=101*5+1,…

Extiende este esquema hacia abajo hasta que descubras que los números de la segunda columna se quedan encerrados en un ciclo: 22, 40, 70. Si cambias el Inicio a 8, te puedes encontrar un ciclo de 23 elementos: {30089, 367, 103, 24, 193, 111, 134, 66, 46, 47. 42, 337, 63, 106, 286, 119, 953, 76, 39, 313, 175, 470, 3761}

Este es un comportamiento normal de estas recurrencias. Puedes ir cambiando el coeficiente  y siempre llegarás a un ciclo. Cambia también el inicio y verás que se llega al mismo final cíclico. Puede que te recuerde hechos parecidos, como el “fósil” de un número, el algoritmo 196, la conjetura de Collatz y otros.

En lugar de sumar 1 puedes elegir otro número cualquiera. Incluso lo puedes incorporar al esquema de cálculo



















Sustituimos la iteración A(n+1)=SOPFR(8*A(n)+1) por A(n+1)=SOPFR(8*A(n)+D) y entonces aumenta nuestra sorpresa, porque ahora la longitud del ciclo varía de un valor a otro de D. Por ejemplo, si D=17 el ciclo se reduce a la unidad, pues se llega al punto fijo 34, mientras que para D=29 se desemboca en un ciclo de 29 elementos.

No parece relevante si C y D son o no coprimos, porque al ser SOPFR aditiva los factores comunes se pueden sacar como sumandos. Lo que sí ocurre es que los resultados para valores cercanos de C o D son muy dispares, como puedes comprobar en la tabla que hemos creado para C=12



Investigando por ahí nos hemos dado cuenta de que a veces, según el valor de inicio pueden obtenerse unos ciclos distintos. Prueba con C=7 y D=3. No parece que se altere la longitud del ciclo si cambiamos el valor inicial. En este caso siempre vale 8.


Caso C=1 D=0

Si fijamos estos valores los ciclos siempre tendrán longitud 1, es decir, que se llegará a un único valor fijo o invariante. La razón es que vimos en su momento que SOPFR(N) es siempre menor o igual a N (la igualdad se da en los primos y en el 4), por lo que la sucesión formada será decreciente y al llegar al primer primo (o el 4) entrará en un valor fijo.

Lo tienes estudiado en  http://oeis.org/A029909

Estos son los puntos fijos a los que se llega desde los números que no son primos (con el 1 incluido)

0, 4, 5, 5, 5, 7, 7, 5, 5, 5, 5, 5, 7, 13, 5, 7, 5, 5, 11, 7, 7, 5, 19, 7, 7, 7, 5, 11, 7, 5, 11, 7, 11, 5, 7, 5, 17, 11, 5, 13, 13, 31, 7, 5, 13, 7, 5, 5, 7,…

Como ves, son todos primos salvo el 4. Son los números para los que SOPFR(N)=N

Hemos estudiado cuántos pasos necesita cada número no primo para llegar a su punto fijo. Por ejemplo, el 51 necesita 4 pasos: sopfr(51)=17+3=20, sopfr(20)=2+2+5=9, sopfr(9)=3+3=6, sopfr(6)=2+3=5 y sopfr(5)=5. Se ha llegado al 5 en cuatro pasos.

El resultado ha sido

1, 0, 1, 2, 2, 1, 1, 3, 3, 3, 3, 3, 2, 1, 3, 2, 4, 3, 1, 2, 2, 4, 1, 2, 2, 3, 4, …

Otros ciclos

Sorprendentemente, estos ciclos también aparecen si la función SOPFR se reitera sobre la suma de los dos anteriores términos. En la imagen hemos comenzado la iteración con los números 291 y 405. Debajo le hemos calculado la suma de divisores primos de su suma:



291+405=696=2^3*3*29, luego sopfr(291+405)=2+2+2+3+29=38, como puedes comprobar en la imagen. Reiteramos: 405+38=443, que es primo, luego sopfr(405+38)=443. Después sumaríamos 38+443…y así seguiríamos reiterando.

Al final se desemboca en el ciclo {19,11,10,10,9}

Más sorprendente todavía: reitera con tres, cuatro o cinco sumandos y seguirás obteniendo ciclos.
Intenta investigar las causas y si existen otras variantes de iteración.

Alguien ha construido autómatas celulares en los que se ven muy bien los ciclos, pero no hemos podido localizarlos.

No hay comentarios: