#014 Secuencia Collatz más Larga

1 La Conjetura de Collatz

También llamada "problema 3n+1", es uno de los problemas abiertos más famosos de las matemáticas. Nadie ha demostrado que siempre llegue a 1, pero tampoco se ha encontrado un contraejemplo.

n \to n / 2 Si n es par

n \to 3n + 1 Si n es impar

Ejemplo: Secuencia comenzando en 13

● Impar (×3+1) ● Par (÷2) ● Fin

¿Por qué es un problema abierto?

La secuencia es caótica. Números cercanos pueden tener comportamientos muy diferentes:

26 → 11 pasos

27 → 111 pasos (¡10x más!)

Erdős ofreció $500 por una demostración. Dijo: "Las matemáticas aún no están listas para este tipo de problemas."

El Problema: Trabajo Repetido

Si calculamos las secuencias para 13, 26, 40, 80... ¡repetimos mucho trabajo!

El Insight: Memoización

Si ya calculamos que collatz(40) = 9 pasos, ¿por qué calcularlo de nuevo?

Memoización = guardar resultados para no recalcular. Es la base de la programación dinámica.

Número inicial

837,799

Longitud de cadena

525 pasos

2 Fuerza Bruta (Sin Caché)

La solución directa: para cada número del 1 al 999,999, calcular la longitud de su secuencia completa. Problema: repetimos muchísimos cálculos.

Python — Fuerza bruta (lento)

def collatz_length(n):
    """
    Calcula la longitud de la secuencia Collatz para n.
    SIN memoización - recalcula todo cada vez.
    """
    length = 1  # Contamos el número inicial

    while n != 1:
        if n % 2 == 0:
            n = n // 2      # Par: dividir entre 2
        else:
            n = 3 * n + 1   # Impar: multiplicar por 3 y sumar 1
        length += 1

    return length

# Para demostrar, usamos un límite pequeño (10,000 en vez de 1,000,000)
# porque sin caché es MUY lento
LIMIT = 10_000

max_length = 0
max_start = 0

for start in range(1, LIMIT):
    length = collatz_length(start)
    if length > max_length:
        max_length = length
        max_start = start

print(f"Límite: {LIMIT:,}")
print(f"Número con cadena más larga: {max_start}")
print(f"Longitud de la cadena: {max_length}")
print()
print("⚠️ Con 1,000,000 esto tardaría ~30 segundos")
print("   porque recalculamos los mismos valores miles de veces")

// Output aparecerá aquí

¿Por qué es lento?

Cuando calculamos collatz_length(26), pasamos por 40, 20, 10, 5, 16, 8, 4, 2, 1.

Pero cuando calculamos collatz_length(40), ¡repetimos exactamente lo mismo desde 40!

# Trabajo repetido:

collatz(26): 26 → 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

collatz(40): 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

collatz(80): 80 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

Análisis de complejidad

Tiempo

O(n × L)

n números × L pasos promedio por secuencia

Espacio

O(1)

Solo variables locales

L puede ser muy grande (hasta ~500 para n < 1M) y muchas secuencias comparten sufijos.

3 Memoización: Recordar para no Repetir

La idea es simple: cuando calculemos collatz(40) = 9, lo guardamos. La próxima vez que lleguemos a 40, devolvemos 9 directamente.

¿Qué es la Memoización?

Memoización viene de "memo" (memorando). Es una técnica de optimización que:

Guarda el resultado de funciones costosas
Devuelve el resultado guardado cuando se llama con los mismos argumentos

Es útil cuando una función:

Es pura (mismo input → mismo output)
Se llama muchas veces con los mismos argumentos
Es costosa de calcular

Así funciona el caché:

1

→ 1

2

→ 2

4

→ 3

8

→ 4

16

→ 5

5

→ 6

10

→ 7

20

→ 8

40

→ 9

13

→ 10

■ Cache hits: cuando calculamos 26, llegamos a 40 y ya sabemos que son 9 pasos más.

Python — Con diccionario (caché manual)

# Caché: diccionario que guarda {número: longitud_secuencia}
cache = {1: 1}  # Caso base: collatz(1) = 1 paso

def collatz_length_memo(n):
    """
    Calcula la longitud de la secuencia Collatz con memoización.
    Si ya calculamos este número, devolvemos el resultado guardado.
    """
    # ¿Ya lo calculamos?
    if n in cache:
        return cache[n]

    # Calcular el siguiente número en la secuencia
    if n % 2 == 0:
        next_n = n // 2
    else:
        next_n = 3 * n + 1

    # La longitud es 1 + longitud del resto de la secuencia
    length = 1 + collatz_length_memo(next_n)

    # Guardar en caché para futuras consultas
    cache[n] = length

    return length

# Ahora podemos usar el límite completo
LIMIT = 1_000_000

max_length = 0
max_start = 0

for start in range(1, LIMIT):
    length = collatz_length_memo(start)
    if length > max_length:
        max_length = length
        max_start = start

print(f"Número con cadena más larga: {max_start:,}")
print(f"Longitud de la cadena: {max_length}")
print(f"\nEntradas en caché: {len(cache):,}")
print(f"(Sin caché habríamos calculado millones de pasos extra)")

// Output aparecerá aquí

Python — Con @cache (forma pythónica)

from functools import cache

@cache  # ¡Magia! Python guarda automáticamente los resultados
def collatz_length(n):
    """
    Con @cache, Python automáticamente:
    1. Revisa si ya llamamos a collatz_length(n)
    2. Si sí, devuelve el resultado guardado
    3. Si no, calcula, guarda, y devuelve
    """
    if n == 1:
        return 1

    if n % 2 == 0:
        return 1 + collatz_length(n // 2)
    else:
        return 1 + collatz_length(3 * n + 1)

# Encontrar el máximo
LIMIT = 1_000_000

max_start = max(range(1, LIMIT), key=collatz_length)
max_length = collatz_length(max_start)

print(f"Número con cadena más larga: {max_start:,}")
print(f"Longitud de la cadena: {max_length}")

# Ver estadísticas del caché
info = collatz_length.cache_info()
print(f"\nEstadísticas del caché:")
print(f"  Hits (reutilizados): {info.hits:,}")
print(f"  Misses (calculados): {info.misses:,}")
print(f"  Hit ratio: {info.hits / (info.hits + info.misses) * 100:.1f}%")

// Output aparecerá aquí

Comparación de rendimiento

Método	Tiempo (1M números)	Memoria
Sin caché	~30 segundos	O(1)
Con memoización	~0.5 segundos	O(n) caché

La memoización es un trade-off: usamos más memoria para ahorrar tiempo. En este caso, ~2MB de caché nos ahorra ~30 segundos.

¿Cuándo usar memoización?

✓ Usar cuando:

La función es pura (sin efectos secundarios)
Se llama con los mismos argumentos múltiples veces
El cálculo es costoso
Tienes memoria suficiente para el caché

✗ No usar cuando:

Cada llamada tiene argumentos únicos
El cálculo es trivial (O(1))
La memoria es limitada

@cache vs @lru_cache

@cache

Guarda todo para siempre. Ideal cuando la memoria no es problema.

from functools import cache

@lru_cache(maxsize=N)

Guarda los últimos N resultados (Least Recently Used). Ideal cuando la memoria es limitada.

from functools import lru_cache

✓ Memoización ✓ @cache decorator ✓ Trade-off tiempo/memoria ✓ Subproblemas solapados

Longest Collatz Sequence

1 La Conjetura de Collatz

Ejemplo: Secuencia comenzando en 13

¿Por qué es un problema abierto?

El Problema: Trabajo Repetido

El Insight: Memoización

2 Fuerza Bruta (Sin Caché)

¿Por qué es lento?

Análisis de complejidad

3 Memoización: Recordar para no Repetir

¿Qué es la Memoización?

Así funciona el caché:

Comparación de rendimiento

¿Cuándo usar memoización?

@cache vs @lru_cache