# check1426.py -- independent re-count of the staircase ladder (Theorem 3, Proposition 7, Theorem 8) at levels x in {11,13,17,19}. # Written from the note's definitions only (not from natal-cap-08-staircase.js). Prints N, actual removals, survivors, # sum cap1, sum cap2 (=cap_0), the cap_K ladder with the first-12-scour-prime pool, K*, and the certified floor. import sys, math, time 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 def level(x, K_pool=12): t0=time.time() wheel=[p for p in primes_upto(x)]; W=1 for p in wheel: W*=p small=[p for p in wheel if p>=7] # comb N_x comb=[r for r in range(W) if r%30 in (11,17) and all(r%p not in (0,p-2) for p in small)] N=len(comb); assert N==2*math.prod(p-2 for p in small) sq=int(math.isqrt(W)); scour=[q for q in primes_upto(sq) if q>x] # march: fresh strikes alive=bytearray([1])*W for r in comb: alive[r]=0 # mark comb slots as 0 = alive-comb; use separate array isslot=bytearray(W) for r in comb: isslot[r]=1 struck=bytearray(W) fresh={}; selfs={} for q in scour: f=0; sf=0 for r in range(0,W,q): # r ≡ 0 mod q if isslot[r] and not struck[r]: struck[r]=1; f+=1; sf+= (r==q) for r in range(q-2,W,q): # r ≡ -2 mod q if isslot[r] and not struck[r]: struck[r]=1; f+=1; sf+= (r==q-2) fresh[q]=f; selfs[q]=sf removed=sum(fresh.values()); survivors=N-removed assert survivors==sum(1 for r in comb if not struck[r]) # caps tmax=(W+1)//scour[0]; spf=spf_table(tmax) pool=scour[:K_pool] def s_of(q): return 1 if q%30 in (11,13,17,19) else 0 sumcap1=0; ladder=[0]*(K_pool+1) for q in scour: assert selfs[q]<=s_of(q) # Phi*(t,q) = #{2<=m<=t : spf(m)>=q} 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) cap1=cA+cB+s_of(q); sumcap1+=cap1 # cap_K: side conditions on v=qm plus first K pool primes below q fp=[qq for qq in pool if qqlen(fp) same as K=len(fp)) for K in range(0,K_pool+1): if K<=depth: cnt[K]+=1 capK=[c+s_of(q) for c in cnt] assert cap1>=capK[0], (q,cap1,capK[0]) for K in range(K_pool): assert capK[K]>=capK[K+1] assert fresh[q]<=capK[K_pool], (q,fresh[q],capK) for K in range(K_pool+1): ladder[K]+=capK[K] Kstar=next((K for K in range(K_pool+1) if ladder[K]