La conjetura de Collatz

En 1937 el matemático alemán Lothar Collatz conjeturó un problema bastante curioso y
simple, pero hasta nuestros días aún no tiene solución.  Se trata de una función recurrente que siempre termina en 1; ésta función se define cuanto sigue

C_k(n) = \begin{cases} n/2 & \mbox{si } n \equiv 0 \mod 2 \\ 3n+1 & \mbox{si } n \equiv 1 \mod 2\end{cases}

Por ejemplo, si el número es 3, entonces C_1(3)=3(3)+1=10, luego
repetimos C_1(10)=C_2(3)=10/2=5 , volvemos a aplicar la función C_1(5)=C_3(3)=3(5)+1=16. De aquí, solo Lothar Collatz.jpgdividimos entre 2, pues lo último es una potencia de 2, entonces, pueden comprobar, que en otras cuatro iteraciones el resultado es 1.

Es trivial que si n=2^m entonces C_m(n)=1.

En nuestra función, la única forma de disminuir a 1 es dividiendo entre 2, por esta cuestión se debe encontrar alguna k tal que C_k(n)=2^m, por tanto C_{k+m}(n)=1. Veamos primero si es siempre posible encontrar potencias de dos en la iteración: por el pequeño teorema de Fermat 2^{3-1}\equiv 1 \mod 3, lo que implica, por propiedad, que 2^{2t}=3q+1.

Ahora bien, supongamos que n sea un entero impar, denotemos \alpha a la función de iterar dos veces la función de Collatz: \alpha(n)=\frac{3n+1}{2}. Si aplicamos asimismo de forma reiterada [pueden comprobar] queda

\alpha^k(n)=\bigg(\cfrac{3}{2}\bigg)^kn+\displaystyle\cfrac{1}{2}\sum_{i=0}^{k-1}\bigg(\cfrac{3}{2}\bigg)^{i} \ \ \ \ \ \ (1)

Nuevamente, por la fórmula de la serie geométrica se reduce a

\bigg(\cfrac{3}{2}\bigg)^kn+(\cfrac{1}{2})\cfrac{(\frac{3}{2})^k-1}{\frac{3}{2}-1}=\bigg(\cfrac{3}{2}\bigg)^kn+(\cfrac{1}{2})\cfrac{(\frac{3}{2})^k-1}{\frac{1}{2}}=\bigg(\cfrac{3}{2}\bigg)^k(n+1)-1

Como se ha afirmado, toda potencia de dos termina en 1. Por lo que nos resta sustituir en la fórmula obtenida:

2^m=\bigg(\cfrac{3}{2}\bigg)^k(n+1)-1

Despejando, se tiene

\bigg(\cfrac{2}{3}\bigg)^{k}(2^m+1)=n+1 \ \ \ \ \ \ (2)

Si la conjetura es cierta, entonces todo entero positivo par puede escribirse de la forma \bigg(\cfrac{2}{3}\bigg)^{k}(2^m+1). Es fácil ver que si m es impar, 2^m+1 es un número de la forma 3^rs. De aquí para adelante es un poco más complicada la resolución del problema.

_ _

En la expresión dada en (1) no siempre los resultados serán impares, pares, impares, …; como es el caso de los números de la forma 2^st, \ s>1 (t impar), ya que en la siguiente iteración se vuelve a dividir entre dos. Por esta razón es conveniente la generalización:

\cfrac{3^kn+3^{k-1}+3^{k-2}2^{j-l_0}+\cdots+3^02^{j}}{2^j} \ \ \ \ \ \ (3)

La idea, como puntualizaba, es encontrar potencias de dos en la iteración. Verbigracia, para el 7 se puede encontrar la siguiente

\cfrac{3^5(7)+3^4+3^32+3^22^2+3^12^4+3^02^7}{2^7}=2^4

Anuncios
Esta entrada fue publicada en Curiosidades, Números Naturales, Teoría de Números. Guarda el enlace permanente.

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s