lunes, 4 de abril de 2011

La conjetura de Collatz

Vamos elegir un número entero positivo cualquier, a modo de semilla, y calcularemos la serie de números obtenida siguiendo la siguente regla:
  • Si el número es par, el siguiente número de la serie se obtiene dividiéndolo por dos.
  • Si el número es impar, el siguiente número se calcula multiplicándolo por 3 y sumándole uno
La fractal de Collatz en el entorno de la recta real

Veamos unos ejemplos:

$$n=3\to 10, 5, 16, 8, 4, 2, 1, 4, 2, 1,... $$
$$n=4\to 2, 1, 4, 2, 1,... $$
$$n=5\to 16, 8, 4, 2, 1, 4, 2, 1,...$$
$$n=6\to 3, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1,...$$
$$n=7\to 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1,... $$
Aham... parece que toda semilla acaba llegando al 1, y después se repite la secuencia 4,2,1,4,2,1,... La conjetura de Collatz dice que sí, aunque nunca ha sido demostrada. Existen diversos grupos de computación que se dedican a calcular las secuencias de números cada vez más grandes. Recientemente (noviembre de 2005) se comprobó la conjetura para todas las secuencias de números menores que 258. ¿Te atreves a demostrarlo? :p

De forma analítica, la función de función de Collatz se puede expresar como:

$$ f(n) = [1+(-1)^n] \cdot \frac{n}{4}+ [1-(-1)^n] \cdot \frac{3n+1}{2}$$

Si no os lo creéis ;) hacemos unos cálculos para comprobarlo:
  • Si n es par, entonces $$(-1)^n=1 \to f(n) = \frac{n}{2}$$
  • Si n es impar, entonces $$(-1)^n=-1 \to f(n) = 3n+1$$
que coincide con la definición de la serie. Por ejemplo, podemos ver que f(7) = 22, f(22) = 11, etc.

A modo de curiosidad, a partir de la traslación de la función de Collatz a los números reales podemos obtener la fractal de Collatz que os mostramos arriba.

No hay comentarios: