Paradigm Pinball

factors.py

from math import isqrt


nonprimes = set()
primes = [2]
prev_n = 2


def ensure_primes(n):
    global prev_n
    if n <= prev_n:
        return
    subroot = True
    for p in primes:
        end = n // p
        if end < p:
            subroot = False
            break
        for i in range(p, end + 1):
            nonprimes.add(p * i)
    for p in range(prev_n + 1, n + 1):
        if p in nonprimes:
            continue
        primes.append(p)
        if subroot:
            end = n // p
            if end < p:
                subroot = False
            else:
                for i in range(p, end + 1):
                    nonprimes.add(p * i)
    prev_n = n


def factors(n):
    fctrs = []
    cutoff = isqrt(n)
    ensure_primes(cutoff)
    for p in primes:
        if p > cutoff:
            break
        while n % p == 0:
            fctrs.append(p)
            n //= p
            cutoff = isqrt(n)
    fctrs.append(n)
    return fctrs


def explore(target, max_mul, max_depth):
    assert max_depth >= 1
    for mul in range(max_mul + 1):
        fctrs = factors(mul * 2 ** 32 + target)
        all = []
        for fctr in fctrs:
            if fctr < 300:
                all.append(fctr)
            elif max_depth == 1:
                break
            else:
                subfctrs = explore(fctr, max_mul, max_depth - 1)
                if not subfctrs:
                    break
                all += subfctrs
        else:
            return all
    return None


if __name__ == "__main__":
    print(sorted(explore(0x020c020c, 20, 3) or []))