# compare1426.py -- the two comparisons the proposal names: (1) the tail cap's closed form with Rosser-Schoenfeld # (pi(t) < 1.25506 t/ln t, t>1; pi(t) > t/ln t, t>=17) versus Dusart's sharper upper bound # (pi(t) <= t/ln t (1 + 1.2762/ln t), t>1; Dusart, Math. Comp. 68 (1999)); (2) Fan-Pomerance's Phi(t,y) < 0.6 t/log y # (y <= sqrt t) applied per head prime, versus the exact Phi* the cap uses. Exact Phi*(t,q) = #{2<=m<=t : spf(m)>=q}. import math, sys def primes_upto(n): s=bytearray([1])*(n+1); s[0]=s[1]=0 for i in range(2,int(n**0.5)+1): if s[i]: s[i*i::i]=bytearray(len(s[i*i::i])) return [i for i in range(n+1) if s[i]] def spf_table(n): spf=list(range(n+1)) for i in range(2,int(n**0.5)+1): if spf[i]==i: for j in range(i*i,n+1,i): if spf[j]==j: spf[j]=i return spf RS_up=lambda t: 1.25506*t/math.log(t) DU_up=lambda t: t/math.log(t)*(1+1.2762/math.log(t)) def RS_low(t): return t/math.log(t) if t>=17 else None for x in [11,13,17,19]: W=math.prod(primes_upto(x)); sq=math.isqrt(W); scour=[q for q in primes_upto(sq) if q>x] spf=spf_table((W+1)//scour[0]) pi=lambda t: sum(1 for p in primes_upto(int(t)) ) if t>=2 else 0 P=primes_upto((W+1)//scour[0]+1); import bisect pic=lambda t: bisect.bisect_right(P,int(t)) s_of=lambda q: 1 if q%30 in (11,13,17,19) else 0 tail=[q for q in scour if q**3>W+1]; head=[q for q in scour if q**3<=W+1] ex_t=sum(pic((W-1)//q)+pic((W+1)//q)-2*pic(q-1)+s_of(q) for q in tail) rs=sum(2*(RS_up((W+1)/q)-(RS_low(q-1) if RS_low(q-1) else pic(q-1)))+1 for q in tail) du=sum(2*(DU_up((W+1)/q)-(RS_low(q-1) if RS_low(q-1) else pic(q-1)))+1 for q in tail) # head: exact cap1 and Fan-Pomerance bound 2*0.6*t/ln(y) with y = q-1 (Phi(t,y) counts n<=t with P^-(n)>y, includes n=1), # applicable when y <= sqrt(t): here q <= sqrt((W-1)/q) iff q^3 <= W-1. ex_h=0; fp_h=0; napp=0 for q in head: tA=(W-1)//q; tB=(W+1)//q cA=sum(1 for m in range(2,tA+1) if spf[m]>=q); cB=sum(1 for m in range(2,tB+1) if spf[m]>=q) ex_h+=cA+cB+s_of(q) y=q-1 if y*y<=tA: napp+=1; fp_h+=0.6*tA/math.log(y)-1+0.6*tB/math.log(y)-1+s_of(q) else: fp_h+=cA+cB+s_of(q) # FP not applicable: keep exact print(f"x={x}: tail primes {len(tail)}: exact {ex_t} RS {rs:.0f} Dusart {du:.0f} (ratios RS/exact {rs/ex_t:.3f}, Dusart/exact {du/ex_t:.3f}) | head primes {len(head)} (FP applicable {napp}): exact cap1 {ex_h} FP-bound {fp_h:.0f} ratio {fp_h/ex_h:.3f}", flush=True)