Conjetura de
Collatz
Sea la siguiente operación, aplicable a cualquier
número entero positivo:
Si el número es par, se divide entre
2.Si el número es impar, se multiplica por 3 y
se suma 1.
La conjetura dice que siempre alcanzaremos el 1 (y por
tanto el ciclo 4, 2, 1) para cualquier número con el que
comencemos.
Iniciaremos el análisis para un número n
de la forma 2a con
2.1- Se aplicará el primer criterio y
habrán divisiones hasta que el cociente es 1; dado que 1
es impar, se aplica el segundo criterio (3n +1) iniciando
así el ciclo 4,2,1.
2.2- Si n es un número par, compuesto, admite
divisiones por 2, el cociente llegará a ser un
número impar, se aplicará el segundo criterio (3n +
1), lo cual inevitablemente genera un número
par.
2.3- Si n es un número impar, directamente aplica
el segundo criterio (3n + 1)
En consecuencia de lo descrito anteriormente, en proceso
de iteraciones sucesivas pasará por el segundo criterio
(3n + 1) por lo menos una vez.
Al sustituir k obtendremos los siguientes
valores:
TABLA N° 1
De los elementos mostrados en la tabla N°1, se
desprende que podemos determinar a simple vista cinco
progresiones aritméticas de la forma ax + b; donde a
será treinta (30) y b será los elementos h(k)
menores a treinta (30). Podemos expresar lo siguiente:
Si se define:
Congruencia
Mostramos en la tabla N° 2, nueve elementos de los
conjuntos C,D,E,G y J.
TABLA N° 2
Queda claro que los elementos del mismo conjunto son
congruentes entre sí, y que no hay congruencia entre
elementos de conjuntos diferentes.
El conjunto H agrupa a todos los n con clase residual
4,10, 16,22 y 28.
Los elementos en azul son números perfectos; los
elementos resaltados en naranja y verde, identifica el ciclo de
la clase residual mod(30): 0,16,6,28.
TABLA N° 3
5.- Al aplicar CONJETURA DE COLLATZ
Se cumple que necesaria y obligatoriamente se pasa por
determinar el valor de f(n) para un número impar,
aplicación del segundo criterio, este valor, cualquiera
que sea, es congruente con uno de los cinco elementos b < 30
para x = 0.
Tabla N° 4
Si n es par, habrá divisiones sucesivas hasta que
el cociente sea impar y los cambios de clases residuales se
muestran en la siguiente tabla.
TABLA N° 5
Para validar y explicar en detalle este punto, definamos
los conjuntos siguientes de la forma Ca = 30k + a
TABLA N° 6
Para adelantarnos definiremos lo siguiente:
Número Conector, NC:
Dado el desarrollo de la función de Collatz entre
dos números, llamaremos Número Conector al
último número común entre ambas columnas
visto en forma ascendente.
Figura N° 1
Este número permite unir dos columnas o
más. Tienen una ubicación única, pertenecen
al conjunto H y por lo tanto, puede poseer una clase residual:
cuatro (4), diez (10), dieciséis (16), veintidós
(22) o veintiocho (28).
Para dar un ejemplo de esto, veamos la Tabla N°
7.
TABLA N°7
Se muestra tres elementos desarrollados con la
función de Collatz, para el número NC 16, su
ubicación es cinco (5), clase residual 16, para el
número NC 34, su ubicación es 14, su clase residual
es cuatro (4).
Número de Transito, NT:
Dado el desarrollo de Collatz de dos números
naturales, llamaremos Número de Transito a aquel N cuyos
elementos de desarrollo incluyendo N, estén incluidos en
el otro. Por ejemplo:
Figura N°2
El número 28 es un número de transito en
relación al número 37.
Para el análisis siguiente se tomaron los
primeros 40 elementos de cada uno de los conjuntos definidos en
la Tabla N° 5. El detalle por conjunto se hace muy denso, por
lo tanto se muestra en el anexo un ejemplo.
Dicho de otro modo:
H = C4 U C10 U C16 U C22 U C28
Recordemos que los cambios de columnas pueden ser por
dos razones, dado un Número Conector NC o
Número de Transito NT. Debe coincidir en la misma
fila, celdas del mismo color e identificadas con el mismo
número.
La función de Collatz, divide por dos a todo
número n par, cuando el cociente llega a ser impar o el
número de inicio es impar, la función de Collatz
para n impar es igual a 3n + 1, transforma a n en un valor par
pero restringido en su clase residual.
Elaborando un diagrama de flujo desde los resultados de
los cambio de clase residual mostrados en la Tabla 4 y 5, podemos
obtener como cambia la clase residual por cada iteración,
la decisión depende de la magnitud de n, por
ejemplo:
DIAGRAMA N°1
DIAGRAMA DE FLUJO
CAMBIO DE CLASE RESIDUAL POR
ITERACIÓN.
En el diagrama N° 1, cada clase residual está
representada en un círculo y se identifica con un
número, de este modo se representa los cambios de clase
residual por cada iteración, puede iniciar por cualquiera
de los círculos, siempre llegara a la clase residual uno,
a la unidad y luego al ciclo 4, 2, 1. Sin duda alguna, la
trayectoria dependerá de la magnitud de N pero
terminará irremediablemente en uno y en el ciclo
4,2,1.
Adicionalmente, se demuestra en el anexo, que la
función de Collatz tiene la propiedad de que cualquier
número N sometido a este proceso de iteración,
entre los diferentes elementos que se generan están los
números NC, este número entrelaza y hace
común el camino o desarrollo de estas dos columnas. Este
efecto, desplaza, si se quiere, la trayectoria descrita por el
elemento en desarrollo a recorridos transitados por elementos
menores y congruentes. De forma que cada elemento nuevo a
desarrollar se conectará con un elemento anterior a
través de números conectores o simplemente, ese
nuevo elemento es un número de transito. En cualquier
caso, habrá un cambio de columnas, este cambio de columna
termina en la columna uno (1) para cada conjunto de elementos
congruentes y por lo tanto de la misma clase residual; hasta que
son reducidos a la unidad y al ciclo 4, 2, 1.
Bajo cualquiera de los dos argumentos planteados, la
función de Collatz conduce a un número natural
hasta la unidad y luego al ciclo 4, 2, 1.
Anexo
DESARROLLO DE COLLATZ PARA CLASE RESIDUAL
2
Función C 2 = 30k + 2
Autor:
José Mujica