Conjetura de Collatz


Este tipo de conjeturas ha despertado siempre una serie de sentimientos varios en mi. Uno de ellos es el hecho de que el ser humano no haya conseguido medios o capacidad de demostrar tesis tan sencillas de plantear y entender como estas. Por otro lado me hace pensar que todavía hay mucho terreno que recorrer en estos terrenos a primera vista sencillos. Por último me da cierto bienestar el ver que no se ha conseguido demostrar, ya que a veces me encuentro con problemas que piden demostraciones de cosas que a primera vista son simples, y te sientes un poco idiota cuando no eres capaz de hacerlo.

Esta conjetura, como digo, se plantea muy simplemente. Dice que para cualquier número n, si realizamos la iteración siguiente, siempre llegaremos a 1:

Si\quad n\equiv 0\mod 2 \quad n = \frac{n}{2}\\    Si\quad n\equiv 1\mod 2 \quad n = 3n+1

Esto quiere decir que si n es par, entonces lo dividimos por 2. Si n es impar, entonces lo multiplicamos por 3 y le sumamos 1. La conjetura dice que si repetimos esto lo suficiente, siempre llegaremos a 1. Se ha probado con ordenadores para números muy grandes y no se ha encontrado ningún contraejemplo, pero falta una demostración rigurosa de la veracidad o falsedad de esta conjetura.

Una de las curiosidades de esta conjetura es la forma que tienen los números más grandes a los que se llega para cada n. Evidentemente n va subiendo al multiplicar por 3 y sumar 1, y luego bajando al dividir por 2. Esto significa, si siempre llega a 1, que habrá un valor máximo en el camino de cada número. Si calculamos esos números, vemos una curiosa distribución que no parece nada azarosa.

Como siempre, hemos programado una pequeña prueba casera. En C, tenemos un programa que calcula los 10000 primeros números y hace el recorrido, quedándose con los máximos:

#include <stdio.h>

int main() {
	long long int n[10001];
	int i;
	long long int max[10001];
	for(i=1;i<=10000;i++) {
		n[i] = i;
		max[i] = 0;
	}
	for (i=1;i<=10000;i++) {
		while(n[i]!=1) {
			if (n[i]%2 == 0) n[i] /= 2;
			else n[i] = 3*n[i]+1;
			if (n[i]>max[i]) max[i] = n[i];
		}
	}
	FILE *f = fopen("plots.log","w");
	for(i=1;i<=10000;i++) {
		fprintf(f,"%i %Ld\n",i,max[i]);
	}
	fclose(f);
	return 0;
}

El programa guarda los datos en un archivo plots.log. Podemos fácilmente hacer el ploteado por puntos con Matlab o con el software que queramos (que no una con lineas cada punto o no se verá nada).

>> load plots.log
>> x = plots(:,1);
>> y = plots(:,2);
>> x = x';
>> y = y';
>> plot(x(1),y(1),'r*');
>> hold on;
>> axis([0 10000 0 100000]);
>> for i=2:10000
> plot(x(i),y(i),'r*');
> end

Y el resultado es:

beauty

¡Tará! Curioso, ¿verdad? No esperaríamos que fuese tan lineal.

Anuncios
Esta entrada fue publicada en Matemáticas, Opinión y etiquetada , , , , , , , . 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