"""
=============================================================================
Sección Declarativa - Programa Principal

Descripción: Busca y clasifica los primeros k números perfectos analizando
los primos de Mersenne a partir de un exponente primo p.

Casos de prueba:
- p=2 -> Mersenne: 3 (Primo) -> Perfecto: 6
- p=3 -> Mersenne: 7 (Primo) -> Perfecto: 28
- p=11 -> Mersenne: 2047 (No primo) -> Salta

Recursos del programa principal:
- k (int): Cantidad de números perfectos a buscar.
- encontrados (int): Contador de números perfectos hallados.
- p (int): Exponente evaluado, comienza en 2.
=============================================================================
"""

# ==========================================
# DEFINICIÓN DE FUNCIONES
# ==========================================

def es_primo(numero):
    """
    Sección Declarativa
    Descripción: Determina si un número es primo iterando hasta su raíz cuadrada en busca de divisores.
    """
    # Centinela numérico: la parte entera de √numero.
    # Si un divisor potencial supera este valor, no existen
    # más factores posibles y la búsqueda concluye.
    centinela = int(numero ** 0.5)

    # Primer candidato de la secuencia: se empieza con 2.
    # Para numero = 2 o 3, centinela es 1, por lo que divisor (=2)
    # ya supera el centinela y el while no itera → primo.
    divisor = 2

    # CONDICIÓN COMPUESTA del while:
    # (divisor <= centinela) → cláusula de secuencia
    # (numero % divisor != 0) → cláusula de propiedad
    # El bucle continúa mientras haya candidatos por probar Y
    # ninguno haya dividido al número. Se detiene si divisor
    # supera √numero o si se encontró un divisor exacto.
    while (divisor <= centinela) and (numero % divisor != 0):

        # --- Generación del siguiente divisor potencial ---
        # La secuencia completa de candidatos es:
        # 2, 3, 5(=6·1-1), 7(=6·1+1), 11(=6·2-1), 13(=6·2+1), ...

        if divisor == 2:
            # De 2 se pasa a 3.
            divisor = 3

        elif divisor == 3:
            # De 3 se pasa al primer candidato 6k±1.
            # Se inicializa k=1, divisor=5 (=6·1-1), es_gemelo=True
            # indicando que 5 es el primer miembro del par (5, 7).
            k = 1
            divisor = 5
            es_gemelo = True

        elif es_gemelo:
            # El divisor actual es 6k-1. El siguiente es 6k+1,
            # que está a distancia 2. Ejemplo: de 5 a 7.
            divisor = divisor + 2
            es_gemelo = False

        else:
            # El divisor actual es 6k+1. Se avanza al siguiente par:
            # k se incrementa y el siguiente candidato es 6(k+1)-1.
            # Ejemplo: de 7 (=6·1+1) a 11 (=6·2-1).
            k = k + 1
            divisor = 6 * k - 1
            es_gemelo = True

    # INSPECCIÓN AL SALIR: ¿cuál condición del while falló?
    # Si divisor > centinela → se agotaron los candidatos sin
    # encontrar un divisor exacto → el número es primo.
    # Si divisor <= centinela → el while se detuvo porque
    # numero % divisor == 0 → el número no es primo.
    return True if divisor > centinela else False

def mersenne(p):
    """
    Sección Declarativa
    Descripción: Calcula el número de Mersenne para un exponente p.
    Retorna: (2^p) - 1.
    """
    return (2 ** p) - 1

def perfecto_desde_mersenne(p):
    """
    Sección Declarativa
    Descripción: Calcula el número perfecto a partir de un exponente.
    Precondición: mersenne(p) debe ser primo.
    Retorna: 2^(p-1) * (2^p - 1).
    """
    return (2 ** (p - 1)) * mersenne(p)

def suma_divisores_propios(n):
    """
    Sección Declarativa
    Descripción: Retorna la suma de los divisores de n, excluyendo a n.
    """
    suma_divisores = 1 # todo número es divisible por la unidad y no se requiere verificarlo
    ultimo = int(n ** 0.5)
    
    # Bucle que evalúa cada número desde 2 hasta ultimo-1 para hallar divisores exactos.
    for d in range(2, ultimo):
        if n % d == 0: suma_divisores += d + n // d

    # Verificación de ultimo
    if n % ultimo == 0: # ultimo es divisor
        suma_divisores += ultimo
        otro = n // ultimo
        if otro != ultimo: # n no es un cuadrado
            suma_divisores += otro

    return suma_divisores

# ==========================================
# SECCIÓN ALGORÍTMICA
# ==========================================

# 1) Prólogo
print("--- Buscador de Números Perfectos de Mersenne ---")
k = int(input("Ingrese la cantidad de números perfectos a buscar (k): "))

# 2) Desarrollo
encontrados = 0
p = 2 # El primer primo es 2

# 3) Epílogo (Integrado progresivamente en el Desarrollo para reportar hallazgos)
print("\nBuscando...")
while encontrados < k:
    # Primero verificamos si p es primo
    if es_primo(p):
        m = mersenne(p)
        # Luego verificamos si el número de Mersenne generado es primo
        if es_primo(m):
            perf = perfecto_desde_mersenne(p)
            
            # Verificación de integridad usando la definición matemática pura
            verificacion = (suma_divisores_propios(perf) == perf)
            
            encontrados += 1
            print(f"{encontrados:2d}) p: {p:3d} | Mersenne: {m:6d} | Perfecto: {perf:12d} | Verificado: {verificacion}")
            
    if p == 2:
        # De 2 se pasa a 3.
        p = 3

    elif p == 3:
        # De 3 se pasa al primer candidato 6k±1.
        # Se inicializa n=1, divisor=5 (=6·1-1), es_gemelo=True
        # indicando que 5 es el primer miembro del par (5, 7).
        n = 1 # n natural para búsqueda de gemelos 6.n-1 y 6.n+1
        p = 5
        es_gemelo = True

    elif es_gemelo:
        # El divisor actual es 6n-1. El siguiente es 6n+1,
        # que está a distancia 2. Ejemplo: de 5 a 7.
        p = p + 2
        es_gemelo = False

    else:
        # El divisor actual es 6n+1. Se avanza al siguiente par:
        # k se incrementa y el siguiente candidato es 6(n+1)-1.
        # Ejemplo: de 7 (=6·1+1) a 11 (=6·2-1).
        n = n + 1
        p = 6 * n - 1
        es_gemelo = True

input("Pulse Enter para terminar el programa")