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

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

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 $f:\mathbb {N} \mapsto \mathbb {N}$, que en notación de aritmética modular queda expresada como:

$f(n)={\begin{cases}n/2&{\text{if }}n\equiv 0{\pmod {2}}\\3n+1&{\text{if }}n\equiv 1{\pmod {2}}.\end{cases}}$

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 entrada del siguiente.

En notación:

$a_{i}={\begin{cases}n&{\text{for }}i=0\\f(a_{i-1})&{\text{for }}i>0\end{cases}}$

(esto es: $a_{i}$ es el valor de $f$ aplicado a $n$ recursivamente $i$ veces; $a_{i}=f^{i}(n)$).

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 a_i = 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.

Implementación en distintos lenguajes de programación

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);
}

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)

Java

(versión recursiva)

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

Haskell

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

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

JavaScript

function collatz(n) {
    while(n !== 1) { 
        if(n % 2 == 0) // Si es par 
            n = n / 2 
        else
            n = (n * 3) + 1 
    }
}