Conjetura de Collatz


Para todos aquellos interesados en Inteligencia Artificial empezaré a escribir una serie de posts que considero les darán una idea más clara de las áreas a las que pueden enfocarse. El primero será la conjetura de Collatz tambien conocida como 3n+1 ó Conjetura de Ulam.

La conjetura de collatz hace referencia a una función que equivale a una sucesión evaluada en N, la cual siempre obtiene como resultado: 4, 2, 1, 4, 2, 1, 4, 2, 1…, sea cual sea el valor evaluado en ella.

En la cual si elegimos un numero natural cualquiera y lo aplicamos a F según el condicionante de la función, (esto es si es impar aplicamos 3Ni +1, y si es par Np/2), y esto lo hacemos de nuevo con el valor obtenido y sucesivamente, llegara así un momento en que el valor obtenido sea 4, 2, 1, 4, 2, 1, 4, 2, 1…,. Se ha comprobado hasta valores astronómicos computacionalmente, se toma como cierto para todo N, pero no se ha demostrado hasta la fecha.

Esta función enuncia la llamada Conjetura de Collatz en honor a su creador, la cual queremos demostrar que es cierta para todo N.

Aunque formalmente no demuestra nada, existen diversos grupos de computación que se dedican a calcular las secuencias de números cada vez más grandes. En noviembre de 2005 se comprobó la conjetura para todas las secuencias de números menores que 258. Esta es una evidencia intuitiva fuerte a favor de la veracidad del resultado, a pesar de no aportar nada formalmente hablando.

Se puede deducir, de la discusión anterior, que la Conjetura de Collatz sería verdadera si fuera posible probar que para cada número entero N mayor que 2 existe un término en la sucesión que es menor que N. Los argumentos usados para los pares y los impares de la forma 4m+1 para el caso se pueden repetir en general, sin embargo queda por probar que para los números de la forma 4m+3 es posible encontrar un número menor en la sucesión correspondiente.

A continuación se muestran algunas gráficas del algoritmo programado:

N = 500, Pasos = 111

N = 5000, Pasos = 29

Se puede notar que tenemos más iteracciones o pasos cuando N es impar por ejemplo para 50000 se requieren 128 pasos para llegar a 1 y para 5,000,000,009 se requieren 186 pasos.

Puedes probarlo con un pequeño formulario en PHP y la llamada al algoritmo.

Hasta un próximo post

Anuncios

Acerca de silvercorp

Blog personal de Ye§i creado el 18/Ag/06 enfocado al diseño gráfico, tecnología y programación.

Publicado el junio 26, 2012 en Inteligencia Artificial. Añade a favoritos el enlace permanente. Deja un comentario.

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

A %d blogueros les gusta esto: