La conjetura de Collatz
Elijamos un número natural, digamos n, y realicemos los siguientes cálculos:
- Si n es par dividámoslo por 2
- Si n es impar multipliquémoslo por 3 y sumémosle 1 al resultado
Con el número obtenido repitamos el proceso, y así sucesivamente. Hagámoslo con un ejemplo:
n = 6
La secuencia que obtenemos es:
6, 3, 10, 5, 16, 8, 4, 2, 1
Vemos que en unos cuantos pasos hemos llegado al número 1. Pues eso mismo es lo que dice la conjetura de Collatz (también conocida como conjetura 3n + 1, conjetura de Ulam o problema de Siracusa):
Conjetura de Collatz
Para cualquier número natural n realicemos los siguientes cálculos:
- Si n es par dividámoslo por 2
- Si n es impar multipliquémoslo por 3 y sumémosle 1 al resultado
Repitiendo el proceso con los números obtenidos la secuencia siempre acabará en 1
Ya hemos visto la secuencia que obtenemos comenzando por 6. Si escogemos n = 11 obtenemos:
11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1
Una secuencia algo más larga, pero que también termina en 1. Y con n = 27, un número ciertamente pequeño, obtenemos una secuencia considerablemente grande: 111 pasos
27, 82, 41, 124, 62, 31, 94, 47, 142, 71, 214, 107, 322, 161, 484, 242, 121, 364, 182, 91, 274, 137, 412, 206, 103, 310, 155, 466, 233, 700, 350, 175, 526, 263, 790, 395, 1186, 593, 1780, 890, 445, 1336, 668, 334, 167, 502, 251, 754, 377, 1132, 566, 283, 850, 425, 1276, 638, 319, 958, 479, 1438, 719, 2158, 1079, 3238, 1619, 4858, 2429, 7288, 3644, 1822, 911, 2734, 1367, 4102, 2051, 6154, 3077, 9232, 4616, 2308, 1154, 577, 1732, 866, 433, 1300, 650, 325, 976, 488, 244, 122, 61, 184, 92, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1
Imaginad las secuencias que obtendríamos con números grandes.
Este resultado sigue siendo una conjetura ya que no se tiene demostración alguna de su veracidad ni nadie ha encontrado ni contraejemplo ni demostración que demuestre su falsedad. Se ha comprobado que para números hasta 258 la secuencia siempre acaba en 1, es decir, la conjetura es cierta para esos números, pero eso no nos sirve como demostración. Sólo nos podría servir para intuir que podría ser cierto, pero la intuición a veces puede fallar, y si no recordar el caso de la conjetura de Polya.
Si alguien se atreve con el problema y obtiene algún resultado interesante que no dude en comunicárnoslo.
Fuente: Wikipedia (inglés): Collatz conjecture
Actualización: Dos apuntes interesantes:
- Interesante forma de atacar el problema la propuesta por Asier. Puede que desarrollándola no se llegue a nada concluyente, pero es bastante original.
- Enric ha creado un programa para calcular las sucesiones de números que aparecen al comenzar por cualquier número. Tenéis que entrar aquí y escribir http://www.enric.es/php/conjetura-collatz/?f=número-que-queráis. Hasta 1000000000000 lo da bien. A partir de ahí llega al ciclo 4, 2, 1 y lo repite indefinidamente. Y 2000000000010 es el último número para el que ocurre eso. A partir de ahí aparecen números tan grandes que el programa muestra INF de forma indefinida. De todas maneras es muy interesante.
neok | 29 de Noviembre de 2006 | 14:35
Supongo que para la demostración es fácil ver que sólo hace falta demostrar que partiendo desde cualquier impar realizando una o varias operaciones, de las que les tocan a los impares (x3 +1), se puede llegar a un número par.
Ahora demostrar eso, ¡uff! Debe ser chungo.
Albert | 29 de Noviembre de 2006 | 15:08
Si a alguien le gusta la programación, el primer problema de el repositorio de ACM de valladolid va sobre esto:
http://acm.uva.es/p/v1/100.html
Saludos
Naka Cristo | 29 de Noviembre de 2006 | 16:08
Neok, si x impar 3*x+1 es par, lo que hace falta es que en algún número de iteraciones obtengas un valor menor
Asier | 29 de Noviembre de 2006 | 16:21
Es un problema de los que me gustan, por lo sencillo del enunciado y lo fácil que es para entender. Y lo bueno es que aun está sin demostrar
Por cierto neok, para cualquier impar 3x + 1 da siempre par
neok | 29 de Noviembre de 2006 | 16:33
Asier y Naka, cierto me había hecho un lío, pensaba en número par como el número 2n.
mimetist | 29 de Noviembre de 2006 | 17:04
Hace tiempo estuve haciendo mis indagaciones con esta conjetura (yo la conocía por otro nombre)… y todas las sucesiones tienen que pasar por el número 16 para poder llegar a 1.
Lo podéis comprobar de forma constructiva:
Para llegar a 1 hay que partir de 2/2 o 3x+1 (pero esta última nunca puede ser 1 para x mayor que 0), por tanto para llegar a 1 es necesario pasar por el dos. Con el 2 se vuelve a hacer la prueba… y llegaréis a que el 16 es el primer número que se puede obtener de dos formas.
Lek | 29 de Noviembre de 2006 | 17:38
Mimetist, es tu opción de gloria. Hace tiempo pediste un problema no resuelto, ¿no?
Y mira que parece una tontería… pero nada… se me resiste así a la primera intuición
mimetist | 29 de Noviembre de 2006 | 20:21
jajaja, pero este es uno de esos que no hay por donde cogerlos…
En algún sitio leí que sólo hay unas 9 o 10 personas en todo el mundo con los conocimientos necesarios para poder atacar el problema… así que imagínate la profundidad que tiene que tener la cuestión.
Yo miro el problema y veo hasta fractales xD, de forma constructiva tenemos un árbol que empieza a ramificarse en el 16, supongo que se podría hacer algo comprobando que todo número está unido a otro inferior siguiendo algún camino y que tampoco se forman bucles dentro de la ramificación…
Pero sinceramente, no tengo ni idea de como intentar ni lo uno ni lo otro xD
A ver si ^DiAmOnD^ tiene alguna idea, que ya tiene la carrera terminada!! jejeje
Asier | 29 de Noviembre de 2006 | 22:28
Buenas, le he estado dando algunas vueltas al problema y creo haber encontrado si no una demostración estricta, sí una prueba bastante clara que al menos a mí me satisface. Está relacionado con el cáculo de probabilidades. Os lo explico a ver qué os parece:
Partiendo de cualquier número, llegamos a uno par, bien sea el número inicial o tras hacer hacer 3x + 1.
Para un número par aleatorio, la probabilidad de que su mitad sea también par es de 1/2 (esto es evidente). A ese número obtenido tras dividir el número par y que tiene probabilidad 1/2 de ser par o impar lo llamaremos x.
A partir de aquí las posibilidades son estas:
SITUACIÓN INCIAL:
(1) x PAR –> :2 –> SITUACIÓN INICIAL
(2) x IMPAR –> 3x+1 –> :2 –> SITUACIÓN INICIAL
Como vemos siempre volvemos enseguida a la situación inicial donde la probabilidad de tener un número par o impar es 1/2. Dado que esto es así, significa que a la larga pasaremos tantas veces por (1) como por (2). Es exactamente igual que cuando tiramos una moneda al aire, puede salir varias veces seguidas cruz pero a la larga el número de caras y cruces siempre tiende a igualarse.
Ahora, si os fijais bien, y dado que los ‘caminos’ (1) y (2) son equiprobables, vemos que la operación :2 se efectuará dos veces por cada vez que se efectua 3x+1. Es decir, a la larga estamos dividiendo dos veces por cada vez que hacemos 3x+1. Y dividir dos veces por dos es como hacer :4 lo cual hace que acabemos descendiendo porque digamos que :4 ‘gana’ a 3x+1.
Qué os parece?
^DiAmOnD^ | 29 de Noviembre de 2006 | 23:49
mimetist la verdad es que tengo pocas ideas de cómo afrontar esto por mucho que acabara la carrera hace unos años. El problema es demasiado complicado como para afrontarlo de una manera fiable sólo con los conocimientos de la carrera.
Asier no sé si llegarías a algo concreto con ese razonamiento. Lo que no se te puede quitar es que tienes ideas verdaderamente interesante.
Por cierto, ¿cómo quedó aquel tema de la conjetura de Legendre? ¿Algún otro avance?
Albert | 30 de Noviembre de 2006 | 0:14
Asier me gusta tu razonamiento y no le veo ningún error. Lo que pasa es que no sé si una demostración probabilística és algo que los matemáticos aceptarian; la lógica probabílistica no la conozco. Yo no lo he visto nunca, pero creo que es una gran idea.
Saludos.
galois | 30 de Noviembre de 2006 | 2:02
El razonamiento de Asier si demostrara algo sería que es más probable que un número cumpla la conjetura de Collatz, pero como es bien sabido no siempre sale el 50% de caras y de cruces en una tanda de tiradas de monedas.
Alejandro | 30 de Noviembre de 2006 | 4:21
Una vez dijo Paul Erdos q faltan muchos años de desarrollo de las matematicas para q se pueda plantear una solucion a este problema. Con una frase asi creo q solo intentaria resolver el problema quien desconoce al mejor de nuestros tiempo.
Tu planteo Asier da la idea q desciende la serie, pero no salva al quizas el problema mas importante de esta conjetura (o al menos para mi lo es) q es la presencia de algun ciclo.
Wolfaint | 30 de Noviembre de 2006 | 4:49
Yo note otra cosa
Segun mimetist la “cadena”(como yo la llamo) pasa siempre por 16 para llegar a uno.. pero segun he visto(hice unos 4 numeros mas…) siempre pasa por numeros pares, hasta llegar a 10.. dividiendose..
como aki
160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1
Note, ke entre mas grande se hacia el numero, derrepente se creaba una nueva “repeticion” en mi “cadena” .. creandose asi un ciclo .. agregandose, si el numero fuera muy grande
320, 620, 1040, 2080.. etc.. pero solo en los grandes, por ejemplo en el 27 solo llega a aparecer el ciclo desde 160, pero un numero mas grande(no he hayado el numero en cuestion) empezara a mostrar apartir de el( llamemoslo x) el 320, y luego apartir de “y” sera 620.. asi si sakamos el 25(por decirlo, no tengo tiempo de sakarlo) sera solo 160, … y si sakamos 23 sera 80.
No se si me explico,… apenas empiezo en esto de matematicas “online” soy mas de pizarron.. xD..
Lek | 30 de Noviembre de 2006 | 17:25
En realidad, hasta 16 se puede llegar desde 5 ó desde 32… quizá sea el mejor punto para empezar
Asier | 2 de Diciembre de 2006 | 2:37
Buenas, me alegro de que os haya gustado mi razonamiento…
galois yo no digo que “siempre sale el 50% de caras y de cruces” sino que a la larga, y en este caso sí que disponemos de tantas ‘tiradas’ como necesitemos, la proporción tiende a ser 50%. Con lo cual acabamos dividiendo más veces que multiplicando, razón por la que converge.
Alejandro es cierto que no demuestro la imposibilidad de que haya ciclos, salvo el ciclo final 1 - 4 - 2 - 1. He conseguido (aparte) demostrar que no puede haber ciclos cortos de tipo:
x –> 3x+1 –> :2^k –> x
x –> 3x+1 –> :2^k –> 3x+1 –> :2^k –> x
pero demostrarlo para ciclos de cualquier tamaño parece bastante más complicado.
Diamond en cuanto a la conjetura de Legendre, como te comenté encontré un contraejemplo para una de las afirmaciones que hacía en la demostración, con lo cual demostrado no está pero creo que hice un planteamiento interesante y tal vez cuando tenga algo más de tiempo lo retome…
Por cierto, y para todos: me he fijado en que para la secuencia que viene desarrollada en el ejemplo, n = 27, si quitamos todos los pares, que son más de la mitad, entre los impares hay muchos primos, concretamente estos 24:
31, 41, 37, 71, 107, 137, 103, 233, 263, 593, 167, 251, 283, 479, 719, 1619, 911, 1367, 577, 433, 61, 23, 53, 5
casualidad? podría ser una pista? os sugiere algo?
Enric | 2 de Diciembre de 2006 | 15:21
No sé si ya había algo para calcular los numeros de Collatz, pero he hecho una pequeña utilidad para si alguien quiere hacerlo.
Está en http://www.enric.es/php/conjetura-collatz y se puede introducir el numero que se quiera añadiendo ?f=NUMERO
Espero que sirva
Trackback | 3 Dic, 2006
El lado más cachondo de la gofioesfera. » Blog Archive » La conjetura de Collatz
Lek | 4 de Diciembre de 2006 | 10:33
Tenemos otro programador, Diamond y Neok… es que yo toy vago
A Enric le ha quedado más bonita, también, jejeje
Asier | 6 de Diciembre de 2006 | 1:07
A ver qué os parece este razonamiento para ir avanzando:
“Si para cualquier número inicial demuestro que en la secuencia aparecerá otro número menor, entonces la conjetura queda demostrada”.
Con esto nos olvidamos de todos los pares dado que el siguiente número de la secuencia será su mitad.
Para los impares tenemos que pueden dividirse en dos conjuntos:
1.- Impares tipo 4k+1
2.- Impares tipo 4k-1
Para los impares tipo 4k+1 mirad lo que ocurre:
4k+1 —> 12k+4 —> 6k+2 —> 3k+1 < 4k+1
Por lo tanto nos olvidamos también de estos impares. Ya hemos descartado todos los pares y la mitad de los impares.
¿os animais con los impares tipo 4k-1?
^DiAmOnD^ | 7 de Diciembre de 2006 | 0:13
Vaya, Asier, sigues con tus ideas interesantes. La verdad es que tiene muy buena pinta este tema. He estado echando un ojo a los 4k+1 (k par en los dos casos que has descrito, ¿no?) y no parece ser muy sencillo de comprobar.
Supongamos que comprobamos que también se cumple tu hipótesis para estos números. Entonces habría que usar inducción, ¿no?
Asier | 7 de Diciembre de 2006 | 9:51
Para abarcar todos los impares hay que tomar k = 1,2,3,4,5…. en los dos casos.
Para impares de tipo 4k+1 ya he demostrado que siempre llegamos a un número inferior (independientemente de k). Ahora solamente habría que demostrarlo para impares tipo 4k-1 (ó 4k+3, que es lo mismo).
El método es el de inducción, sí, porque si siempre obtengo en la secuencia un número menor, puedo tomar ese número menor como el inicial y volveré a obtener otro aun menor, con lo cual quedaría todo demostrado, es decir, que la secuencia desciende y que no habrá ciclos.
Ana María | 28 de Diciembre de 2006 | 18:03
Me parece que los razonamientos de asier son, sin desmerecer a nadie, los más interesantes. ¿Sabéis a día de hoy los resultados parciales obtenidos en el problema 3n+1?
Ana María | 28 de Diciembre de 2006 | 18:17
Siendo sincera, llevo muchos años dedicándole tiempo a este problema que me apasiona. Dedicándole gran parte de mi tiempo de ocio, y también algunos huecos en el trabajo, he llegado a algunos resultados. Os puede parecer altivez, pero la línea de asier es la que yo seguí, y dado que, casi con total seguridad le he dedicado al problema mucho más tiempo que asier, mis resultados hasta el momento van mucho más lejos. No los cuento porque siempre tiene una la esperanza de que tu propia línea o plan te conduzca a la solución; y aunque nunca llegue a ser así -lo más probable-, los resultados parciales pueden en un momento dado llegar a ser dignos de publicación.
Carlos | 1 de Enero de 2007 | 21:00
Parece que los impares 4k-1 llegan al 16 a través del 10. Por lo tanto todos llegan al 40. Aquí es donde se diferencian porque unos llegan a 40 por medio de 80 y otros por medio de 13.
Fabricio | 19 de Febrero de 2007 | 23:47
creo que la solución es esta gran conjetura está en una relación que existe entre lo que yo llamaría pares puros, que son de este tipo 2^n.(dos elevado a la n) y la función 3x+1 (con xEIN). he represantado y comparado los resultados en excel, y hay una ligera relación en que la función 3x+1 en determinado momento convierte a los números del tipo 2n+1 en 2^n(dos elevado a la n), es decir si represento a todos los números impares obtenidos al alplicar 3x+1,ontengo en su lista los números del tipo 2^n, pero en forma intercalada, es decir, en vez de obtener 4,8,16,32,64,128; obtengo 4,16,64,256,.que son el resultado de aplicar 3x+1 a los impares,,los número que llevan a que la sucesión termine en 1 son los exponentes de 2^n.
los pares puros y pares impuros (pares impuros son del tipo 2^n*primo) convergen al final en lo que yo llamo cociente de pares puros, 2^n/2^n.
creo que mi explicación es no fue muy explícita pero, sólo he estudiado el problmas en tres días abandonado mi estudio(soy estudiandnte de agrimensura UNNE),,,,simpre me ha gustado la matemática, y simpre me he sentido desafiado por todo tipo de problemas,, la verdad mi entrenamiento es muy pobre debido a que en mi carrera solo tuve álgebra,álgebra linea y geomtría,análisis matemático, pero conozco la tería de los números y leí el ibro de enzo gentile….creanme una gran relacion en el comportamiento de estas dos funcions discretas, 2^n y 3x+1, ya que si lo que buscan es su solución, se vana encotrar con los pares puros en impuros.
Trackback | 21 Feb, 2007
Gaussianos » Problemas de programación
Agustín Morales | 2 de Marzo de 2007 | 23:33
Hola, he visto una página curiosa:
http://matematicainsolita.8m.com/
En ella hay descargas de lo que el autor dice ser la demostración de la conjetura de Collatz. El caso es que uno no tiene tiempo ni capacidad para revisar los documentos que tan amablemente nos ofrece el autor para su descarga. Uno se ve tentado de dejar de leer cuando también nos presenta una demostración del UT de Fermat mucho más asequible que la de Wiles, así como la demostración a otras conjeturas que el eleva rapidamente a Teoremas en unas pocas lineas. Pero viendo los planteamientos que hace no me parecen muy descabellados y me pregunto si al menos la forma de atacar el problema pueda ser interesante.
Alejandro | 3 de Marzo de 2007 | 19:25
Lei mal en la web aportada por Agustín (
http://matematicainsolita.8m.com/)
o el autor “demuestra” q el teorema de pitagoras es falso??
GNeras | 4 de Marzo de 2007 | 13:52
Sííí, eso dice, y tiene mucha gracia.
Porque dice que el teorema de Pitagoras es falso, y en la demostración de que es falso acaba demostrando que es cierto.
Acaba diciendo que 40V + 64C + 25S no es igual a 36C + 60C +25S.
Pero esto no es lo que tendría que ser el teorema de Pitagoras, lo único que interesa es el 25S que es iqual en las dos expresiones, por lo tanto, la demostración de que no es cierto demuestra que es cierto (25S = 25S).
No sé si lo dicen en serio, pero tiene gracia.