from functools import cache

LIMIT = 20000 # <- keep low (just don't ask for the decomposition of a big number and you'll be fine :3)
OP = 3 # <- raise this to make it funnier
# ^ the bigger the less interesting

@cache
def hyperop(n: int, a: int, b: int) -> int:
    """i stole this but idk where"""
    if n == 0:
        return b + 1
    if n == 1:
        return a + b
    if n == 2:
        return a * b
    if n == 3:
        return a ** b
    result: int = 1
    for _ in range(b):
        result = hyperop(n-1, a, result)
        if result > LIMIT: # if it's too big we need to discard it asap
            return LIMIT + 1
    return result

primerer: list[int] = []
no: dict[int, list[list[int]]] = {}

def check(v: int = 1, chain: list[int] | None = None):
    """it's a bit slow but it works"""
    if chain is None:
        chain = [v]
    for n in primerer:
        # print(f"{n} {'*' * (OP - 1)} {v}")
        t = hyperop(OP, n, v)
        new_chain = [n] + chain
        if t <= LIMIT:
            if t in no:
                if new_chain not in no[t]:
                    no[t].append(new_chain)
                    print("Duplicate!!")
                    print(f"{v=} {n=} {t=} {chain=} {no[t]=}")
            else:
                no[t] = [new_chain]
            check(t, new_chain)
        else:
            break # primerer is sorted, no need to raise it to even greater powers if it already fails
    
for i in range(2, LIMIT + 1):
    if i % 100 == 0:
        print(i)
    if i not in no:
        primerer.append(i)
        if hyperop(OP, 2, i) <= LIMIT or hyperop(OP, i, 2) <= LIMIT: # HYPEROPTIMIZER2000
            check()

def decompose(x):
    assert x <= LIMIT
    if x in no:
        return no[x][0]
    if x in primerer:
        return [x, 1]
    raise KeyError("?")

def recompose(x: list[int], y: int = 1):
    if not x:
        return y
    return recompose(x[:-1], x[-1] ** y)

# Usage: decompose(<your number>) gives a list, recompose(<list>) gives your number back
# keep your number below LIMIT
# Example: decompose(1331) >>> [11, 3, 1] ; recompose([11, 3, 1]) >>> 1331
# Since 11 ** 3 ** 1 = 1331

# list(filter(lambda x: x not in primerer, range(LIMIT))) is fun