Implementación de algoritmos de teoría de números/Conjetura de Collatz

De Wikilibros, la colección de libros de texto de contenido libre.
Ir a la navegación Ir a la búsqueda

La conjetura de Collatz es una conjetura de teoría de números, debida a Lothar Collatz, que fue quien la propuso en 1937. La conjetura también es conocida como conjetura 3n + 1. La conjetura puede ser descrita como sigue. Tómese cualquier entero positivo n. Si n es par, divídase por 2 para obtener n / 2. Si n es impar, multiplíquese por 3 y súmese 1 para obtener 3n + 1. Repítase el proceso indefinidamente. La conjetura dice que independientemente del número por el que se empiece, siempre se alcanzará el 1, concretamente la secuencia 4,2,1 que se repetirá indefinidamente.

Descripción formal[editar]

Sea la siguiente operación, aplicable a cualquier número entero positivo:

  • Si el número es par, se divide entre 2.
  • Si el número es impar, se multiplica por 3 y se suma 1.

Formalmente, esto equivale a una función , que en notación de aritmética modular queda expresada como:

Ahora, se forma una sucesión mediante la aplicación de esta operación repetidamente, comenzando por cualquier entero positivo, y tomando el resultado de cada paso como la entra del siguiente.

En notación:

(esto es: es el valor de aplicado a recursivamente veces; ).

La conjetura de Collatz es: El proceso alcanzará eventualmente el número 1, independiente del entero positivo que haya sido elegido inicialmente.

El menor i tal que ai = 1 se denomina tiempo de parada total de n. La conjetura asegura que n tiene un tiempo de parada total bien definido. Si, para algún n, tal que i no exista, se dirá que n tiene un tiempo de parada infinito y la conjetura es falsa.

Implementaciones[editar]

En lenguaje C:

void collatz(long int n) {
        while (n > 1) {
                printf("%d", n);
                if ((n % 2) == 1)
                        n = 3 * n + 1;
                else
                        n = n / 2;
        }
        printf("%d", n);
}

En lenguaje Python:

def collatz(n):
	result = [n]
	while n > 1:
		if (n % 2) == 0:
			n = n/2
		else:
			n = n*3 + 1		
		result.append(n)
	print(result)

En lenguaje Java (procedimiento recursivo):

static void collatz(int n) {
	System.out.println(n);
	if (n>1) {
		if (n%2==0)
			collatz(n/2);
		else
			collatz(3*n+1);
	}
}

En lenguaje Haskell:

collatz :: (Integral a)=>a->[a]
collatz 1 = [1]
collatz n
	| even n = n:collatz (div n 2)
	| otherwise = n:collatz (3*n + 1)

En lenguaje MATLAB:

function c = collatz(n)
    c(1) = n;
    r = 2;
    while n ~= 1
        if ~mod(n,2)
            c(r) = n/2;
        else
            c(r) = 3*n + 1;
        end
        n = c(r);
        r = r + 1;
    end
end