Hyper-Primes

import math
from collections import Counter

def prime_factors(n):
    factors = []
    while n % 2 == 0:
        factors.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        while n % f == 0:
            factors.append(f)
            n //= f
        f += 2
    if n > 1:
        factors.append(n)
    return factors

def is_prime(num):
    if num < 2:
        return False
    if num in (2, 3):
        return True
    if num % 2 == 0:
        return False
    root = int(math.sqrt(num))
    for i in range(3, root + 1, 2):
        if num % i == 0:
            return False
    return True

def is_hyper_prime(n, memo={}):
    if n in memo:
        return memo[n]
    
    # Bootstrap base cases: 0, 1, 2 are hyper-primes by definition
    if n in (0, 1, 2):
        memo[n] = True
        return True
    
    # Must be prime to be hyper-prime
    if not is_prime(n):
        memo[n] = False
        return False
    
    # Factor n-1
    factors = prime_factors(n - 1)
    factor_counts = Counter(factors)
    
    # Check all prime factors are hyper-primes
    for factor in factor_counts.keys():
        if not is_hyper_prime(factor, memo):
            memo[n] = False
            return False
    
    # Check all exponents are hyper-primes
    for exponent in factor_counts.values():
        if not is_hyper_prime(exponent, memo):
            memo[n] = False
            return False
    
    memo[n] = True
    return True

def generate_primes(limit):
    primes = []
    for p in range(2, limit + 1):
        if is_prime(p):
            primes.append(p)
    return primes

def generate_hyper_primes(limit):
    hyperprimes = []
    memo = {}
    for p in range(2, limit + 1):
        if is_hyper_prime(p, memo):
            hyperprimes.append(p)
    return hyperprimes

def generate_hyper_primes_debug(limit):
    print(f"| {'Prime':>6} | {'Factors of p-1':>25} | {'Exponents':>15} | {'HyperPrime':>10} |")
    print(f"|{'-'*8}|{'-'*27}|{'-'*17}|{'-'*12}|")
    memo = {}
    for p in range(2, limit + 1):
        if not is_prime(p):
            continue
        factors = prime_factors(p - 1)
        counts = Counter(factors)
        exps_str = ', '.join(f"{prime}^{exp}" for prime, exp in counts.items())
        hyper = is_hyper_prime(p, memo)
        factors_str = ' × '.join(map(str, factors)) if factors else '1'
        print(f"| {p:6} | {factors_str:25} | {exps_str:15} | {str(hyper):>10} |")

# Example test up to 420
generate_hyper_primes_debug(420)