#012 Número Triangular Altamente Divisible

Highly Divisible Triangular Number

Los números triangulares se generan sumando los números naturales consecutivos. El 7º número triangular es 1+2+3+4+5+6+7 = 28, que tiene 6 divisores: 1, 2, 4, 7, 14, 28.

¿Cuál es el primer número triangular que tiene más de 500 divisores?

● Divisores ● Función τ(n) ● Factorización prima

1 ¿Qué son los números triangulares?

Un número triangular es la suma de los primeros n números naturales. Se llaman así porque pueden representarse como triángulos de puntos:

T₁ = 1

T₂ = 1+2 = 3

T₃ = 1+2+3 = 6

T₄ = 1+2+3+4 = 10

Fórmula de Gauss

En lugar de sumar 1+2+3+...+n, usamos la fórmula de Gauss:

T n = n \times (n + 1) / 2 El n-ésimo número triangular

Ejemplo: T₇ = 7 × 8 / 2 = 56 / 2 = 28

2 ¿Cómo contamos divisores?

Un divisor de n es un número que divide a n sin dejar resto. Por ejemplo, los divisores de 28:

Divisores de 28

τ(28) = 6 divisores

¿Por qué en pares?

28 ÷ 1 = 28 → pares (1, 28)

28 ÷ 2 = 14 → pares (2, 14)

28 ÷ 4 = 7 → pares (4, 7)

Los divisores vienen en pares: d y n/d

Insight clave: Solo buscar hasta √n

Si buscamos divisores de 28, no necesitamos probar 1, 2, 3, ..., 28. Solo necesitamos probar hasta √28 ≈ 5.3 porque cada divisor d tiene un "par" n/d.

Probamos 1, 2, 3, 4, 5 y encontramos los pares automáticamente. Esto reduce O(n) a O(√n).

Primeros números triangulares y sus divisores

n	Tₙ = n(n+1)/2	Divisores	τ(Tₙ)
1	1	1	1
2	3	1, 3	2
3	6	1, 2, 3, 6	4
4	10	1, 2, 5, 10	4
5	15	1, 3, 5, 15	4
6	21	1, 3, 7, 21	4
7	28	1, 2, 4, 7, 14, 28	6 ← primero con >5

Respuesta

76,576,500

Número triangular #

12,375

T₁₂₃₇₅ = 12375 × 12376 / 2 = 76,576,500
Tiene exactamente 576 divisores (primero con más de 500).

2 Fuerza Bruta - Contando divisores

La estrategia directa: generar cada número triangular y contar sus divisores hasta encontrar uno con más de 500.

¿Cómo contamos divisores eficientemente?

Hay dos formas de contar divisores. La primera es probar todos los números de 1 a n:

# O(n) - MUY LENTO para números grandes
count = 0
for i in range(1, n + 1):
    if n % i == 0:
        count += 1

Pero los divisores vienen en pares. Si d divide a n, entonces n/d también lo divide. Por eso solo necesitamos buscar hasta √n:

# O(√n) - MUCHO MÁS RÁPIDO
count = 0
i = 1
while i * i <= n:     # Solo hasta √n
    if n % i == 0:
        count += 2    # Encontramos un PAR (i, n/i)
        if i * i == n:
            count -= 1  # Cuadrado perfecto: no contar dos veces
    i += 1

Python

def count_divisors(n):
    """
    Cuenta los divisores de n usando la optimización √n.

    Los divisores vienen en pares: si d divide a n, entonces n/d también.
    Por ejemplo, para n=28:
      - 1 divide a 28, y 28/1 = 28 también divide
      - 2 divide a 28, y 28/2 = 14 también divide
      - 4 divide a 28, y 28/4 = 7 también divide

    Solo necesitamos buscar hasta √28 ≈ 5.3
    """
    count = 0
    i = 1

    # Buscamos divisores solo hasta √n
    while i * i <= n:
        if n % i == 0:
            # Encontramos un par de divisores: i y n/i
            count += 2

            # Si i = √n exacto, no contar dos veces
            # Ejemplo: 36 = 6×6, el 6 solo cuenta una vez
            if i * i == n:
                count -= 1
        i += 1

    return count

def find_triangular_with_divisors(target):
    """
    Encuentra el primer número triangular con más de 'target' divisores.

    Tₙ = n × (n+1) / 2  (fórmula de Gauss)
    """
    n = 1

    while True:
        # Calcular el n-ésimo número triangular
        triangular = n * (n + 1) // 2

        # Contar sus divisores
        divisors = count_divisors(triangular)

        # ¿Encontramos el objetivo?
        if divisors > target:
            return triangular, n, divisors

        n += 1

# Buscar el primero con más de 500 divisores
result, n, num_divisors = find_triangular_with_divisors(500)

print(f"Primer número triangular con >500 divisores:")
print(f"  T₍{n}₎ = {result:,}")
print(f"  Tiene {num_divisors} divisores")

# Verificación
print(f"\nVerificación: {n} × {n+1} / 2 = {n * (n+1) // 2:,}")

// Output aparecerá aquí

Análisis de complejidad

Tiempo

O(k × √Tₖ)

k ≈ 12375, √T ≈ 8752

Espacio

O(1)

Solo variables contadoras

✓ Búsqueda hasta √n ✓ Divisores en pares ✓ Fórmula de Gauss ✓ Cuadrados perfectos

3 Optimización con la Función Tau τ(n)

La función tau τ(n) cuenta los divisores de n. Tiene una propiedad matemática poderosa basada en la factorización prima.

La fórmula mágica de τ(n)

Si conocemos la factorización prima de n:

n = p₁ a₁ \times p₂ a₂ \times ... \times pₖ aₖ Factorización en primos

Entonces el número de divisores es:

τ(n) = (a₁ + 1) \times (a₂ + 1) \times ... \times (aₖ + 1) Producto de exponentes incrementados

Ejemplo: τ(28)

28 = 2² × 7¹

τ(28) = (2+1) × (1+1)

τ(28) = 3 × 2 = 6

Los 6 divisores: 2⁰7⁰=1, 2¹7⁰=2, 2²7⁰=4, 2⁰7¹=7, 2¹7¹=14, 2²7¹=28

¿Por qué funciona?

Cada divisor de n es una combinación de potencias de sus primos.

Para n = 2² × 7¹, cada divisor elige:

• Potencia de 2: 0, 1, o 2 (3 opciones)
• Potencia de 7: 0 o 1 (2 opciones)
• Total: 3 × 2 = 6 combinaciones

Propiedad clave: τ es multiplicativa para coprimos

Si gcd(a, b) = 1 (a y b no comparten factores primos), entonces:

τ(a × b) = τ(a) × τ(b)

Para Tₙ = n × (n+1) / 2, como n y n+1 son siempre coprimos, podemos calcular τ por separado.

Python — Con factorización prima

def prime_factorization(n):
    """
    Devuelve la factorización prima de n como dict {primo: exponente}.

    Ejemplo: prime_factorization(28) → {2: 2, 7: 1}
             porque 28 = 2² × 7¹
    """
    factors = {}
    d = 2

    while d * d <= n:
        while n % d == 0:
            factors[d] = factors.get(d, 0) + 1
            n //= d
        d += 1

    # Si queda algo, es un primo grande
    if n > 1:
        factors[n] = 1

    return factors

def tau_from_factors(factors):
    """
    Calcula τ(n) desde la factorización prima.

    τ(n) = (a₁+1) × (a₂+1) × ... × (aₖ+1)
    donde n = p₁^a₁ × p₂^a₂ × ... × pₖ^aₖ
    """
    result = 1
    for exponent in factors.values():
        result *= (exponent + 1)
    return result

def tau(n):
    """Cuenta los divisores de n usando factorización prima."""
    return tau_from_factors(prime_factorization(n))

def find_triangular_optimized(target):
    """
    Encuentra el primer número triangular con más de 'target' divisores.

    Optimización: Tₙ = n × (n+1) / 2

    Como n y (n+1) son coprimos, τ(n × (n+1)) = τ(n) × τ(n+1)
    Y como uno de ellos es par, dividimos por 2 primero.
    """
    n = 1

    # Precalculamos τ(n) que será τ(n+1) en la siguiente iteración
    tau_n = tau(1)

    while True:
        # n y n+1 son coprimos
        # Uno es par, debemos dividir entre 2
        if n % 2 == 0:
            # n es par, dividimos n/2
            tau_current = tau(n // 2)
            tau_next = tau(n + 1)
        else:
            # n+1 es par, dividimos (n+1)/2
            tau_current = tau(n)
            tau_next = tau((n + 1) // 2)

        # τ(Tₙ) = τ(n/2 o n) × τ((n+1) o (n+1)/2)
        num_divisors = tau_current * tau_next

        triangular = n * (n + 1) // 2

        if num_divisors > target:
            return triangular, n, num_divisors

        n += 1

# Ejecutar
result, n, num_divisors = find_triangular_optimized(500)

print(f"Primer número triangular con >500 divisores:")
print(f"  T₍{n}₎ = {result:,}")
print(f"  Tiene {num_divisors} divisores")

# Mostrar la factorización
print(f"\nFactorización de {result:,}:")
factors = prime_factorization(result)
factorization_str = " × ".join(f"{p}^{e}" for p, e in sorted(factors.items()))
print(f"  {result:,} = {factorization_str}")
print(f"  τ = " + " × ".join(f"({e}+1)" for e in sorted(factors.values(), reverse=True)) + f" = {num_divisors}")

// Output aparecerá aquí

Comparación de rendimiento

Método	Complejidad	Tiempo típico
Contar divisores O(n)	O(k × Tₖ)	>1 minuto
Contar divisores O(√n)	O(k × √Tₖ)	~1 segundo
Factorización + τ	O(k × √n)	~0.3 segundos

✓ Función τ(n) ✓ Factorización prima ✓ Función multiplicativa ✓ Coprimos (gcd=1)

4 La Leyenda de Gauss y la Belleza Matemática

Detrás de cada fórmula elegante hay una historia. Esta es la historia de cómo un niño de 7 años descubrió un patrón que usamos 250 años después.

La Historia: Gauss y el Maestro Büttner (1786)

En una escuela de Brunswick, Alemania, el maestro J.G. Büttner quería mantener ocupados a sus alumnos. Les ordenó sumar todos los números del 1 al 100. Esperaba paz y silencio durante una hora.

Carl Friedrich Gauss, de apenas 7 años, puso su pizarra sobre la mesa en menos de un minuto con una sola respuesta: 5050.

"Ligget se" (Ahí está), dijo Gauss en bajo alemán.

El Insight: Ver lo que otros no ven

Mientras sus compañeros sumaban 1+2+3+4+... laboriosamente, Gauss vio un patrón:

Escribimos la suma dos veces, una hacia adelante y otra hacia atrás:

S = 1 + 2 + 3 + ... + 98 + 99 + 100

S = 100 + 99 + 98 + ... + 3 + 2 + 1

2S = 101 + 101 + 101 + ... + 101 + 101 + 101

Cada columna suma 101, y hay 100 columnas.

2S = 100 × 101 = 10100

S = 5050

T n = n(n+1) / 2 La fórmula de Gauss para números triangulares

¿Por qué n(n+1)/2?

• n pares: Cada número i se empareja con (n+1-i)
• Suma del par: i + (n+1-i) = n+1 siempre
• Total: n pares × (n+1) = n(n+1)
• Dividir por 2: Contamos cada número dos veces

Demostración Visual: Dos Triángulos Forman un Rectángulo

Dos triángulos idénticos (T₄ = 10 cada uno) forman un rectángulo de 4 × 5 = 20 cuadrados.

2 × T₄ = 4 × 5 = 20

T₄ = 4 × 5 / 2 = 10 ✓

Esta es la esencia de la fórmula: un triángulo es exactamente la mitad de un rectángulo n × (n+1).

La Conexión Profunda: τ(n) y Números Triangulares

Para este problema, necesitábamos combinar dos ideas matemáticas elegantes:

1. Gauss: T_n = n(n+1)/2

n y (n+1) son siempre coprimos (no comparten factores).

2. τ multiplicativa

Si gcd(a,b)=1, entonces τ(ab) = τ(a) × τ(b)

Esto significa que podemos calcular τ(T_n) como:

τ(T_n) = τ(n/2) × τ(n+1) si n es par
τ(T_n) = τ(n) × τ((n+1)/2) si n es impar

Calculamos τ de números más pequeños (n o n+1) en lugar del número triangular completo.

El Legado: Del Aula a los Algoritmos

Gauss se convirtió en uno de los matemáticos más influyentes de la historia. Llamado el "Príncipe de las Matemáticas", contribuyó a casi todas las ramas:

Teoría de Números

Aritmética modular, reciprocidad cuadrática

Estadística

Distribución gaussiana (campana)

Álgebra

Eliminación gaussiana

"La matemática es la reina de las ciencias, y la teoría de números es la reina de las matemáticas."
— Carl Friedrich Gauss

Lección para Programadores

La historia de Gauss nos enseña algo fundamental: antes de escribir un bucle, busca el patrón.

En este problema, la diferencia entre O(n) y O(1) no es solo velocidad—es la diferencia entre calcular ciegamente y entender la estructura matemática.

El mejor código no es el más corto ni el más rápido. Es el que demuestra que entendiste el problema.

✓ Historia de Gauss ✓ Demostración visual ✓ Pensamiento matemático ✓ Patrones antes que bucles