Apollonian

• Grows an integral Apollonian circle packing from its root quadruple in exact integers, checks Descartes on every quadruple it makes, identifies the strip packing's line-tangent circles as the Ford circles, and prints the curvature census.
• A circle is the triple (k, k x, k y): curvature, and the centre scaled by it. A line is k = 0 with (k x, k y) its outward unit normal. Every entry is an integer for every packing here.
• The one move is the reflection v' = 2(v_1 + v_2 + v_3) - v applied to all three coordinates at once, which swaps the two circles tangent to the other three; it needs no square root, so the whole run is integer arithmetic.
• Six exact integer identities hold on every quadruple, all of them the bilinear form B(u, v) = (sum u_i)(sum v_i) - 2 sum u_i v_i on the four columns: B(k, k) = B(k, kx) = B(k, ky) = B(kx, ky) = 0 and B(kx, kx) = B(ky, ky) = -4. The first is Descartes; the rest are the position half of the same theorem, and the reflection preserves all six because it lies in the form's orthogonal group.
• The two roots are the strip packing (0, 0, 2, 2), two lines a unit apart with the unit-diameter circles at x = 0 and x = 1 between them, and the bounded packing (-1, 2, 2, 3), whose outer circle is the unit circle.
• The tree is the standard one: from the root every swap is taken, from any later quadruple every swap but the one just undone, and a branch stops when the new curvature passes T. Each node is one new circle, so the census is the node count and the root quadruple is not in it.

THE STRIP

• The strip packing is periodic in x, so the census is taken on one period: the two swaps at the root that replace a line are kept and the two that translate are dropped, which leaves exactly the circles whose centre has 0 < x < 1. The two root circles at x = 0 and x = 1 are the only ones of the whole packing on the boundary and are never counted, so strayed tests the strict inequality, k x <= 0 || k x >= k.
• A circle of the packing is tangent to the line y = 0 exactly when k y = 1, and to y = 1 exactly when k y = k - 1, so the line-tangent census is read off the integers with no geometry.
• Both line tests are for circles of positive curvature: the line y = 1 is (0, 0, 1) and would pass k y = 1, the line y = 0 is (0, 0, -1) and would pass k y = k - 1. The tree never hands a line to either test, since a line is only ever replaced.
• ford walks the Stern-Brocot tree of Farey pairs in exact integers and checks at every mediant that the reflection returns (k, k x, k y) = (2 r^2, 2 p r, 1) for the mediant p/r of the parents a/b and c/d, that the quadruple (0, 2 b^2, 2 d^2, 2 r^2) satisfies Descartes, that the other root of that quadratic is 2 (b - d)^2, and that the two parents are tangent, (a d - b c)^2 = 1.
• The same walk sums floor(Q/b) over the nodes of (0, 1), adds the node 0/1 at brightness Q, and compares the total with Q(Q + 1)/2, the Farey stack's brightness on [0, 1).

RUN

• cargo run --release -p apollonian
• The verbs ford, strip, census and design run one section each; about fourteen seconds in total, census twelve of them. Prints only, writes nothing.
• N(T) in every table is the node count, so the root quadruple is excluded: four circles in the bounded column, one in the strip column.

WITNESSES

• ford: at b <= 4000 the walk makes 4863601 mediants against sum_{b <= 4000} phi(b) - 1 = 4863601, with 0 broken quadruples, 0 coordinate misses and 0 non-tangent parents; brightness 8002000 against 4000 * 4001 / 2. Same at b <= 50, 200 and 1000: 773, 12231, 304191 nodes and 1275, 20100, 500500 brightness.
• strip: 20770674 circles to T = 2097152, tree depth 1023, 0 broken quadruples, 0 duplicate circles on the T <= 2048 control (2448 circles, 2448 distinct), and 0 circles outside 0 < k x < k. Curvatures fall in the residues 0, 2, 8, 18 mod 24, at 4144636, 6223160, 6241134 and 4161744.
• Of those, 318963 have k y = 1 and every one of them is a Ford circle: k/2 a perfect square b^2, k x a multiple 2 a b with gcd(a, b) = 1 and 0 <= a <= b, 0 off-Ford. The same run reads 318963 tangent to the far line.
• strip on the decade grid: N(T) is 2, 48, 950, 19298, 390478, 7899138 at T = 10^1 .. 10^6, exponent by ratio 1.3802, 1.2965, 1.3078, 1.3061, 1.3060.
• The line-tangent count at curvature at most 2 Q^2 is sum_{b <= Q} phi(b) - 1 at Q = 32, 181 and 1024: 323, 10059 and 318963, and the top-tangent count is the same by the strip's reflection symmetry.
• strip on the octave grid, exponent as the ratio log(N(T_2)/N(T_1)) / log(T_2/T_1): 1.2925, 1.2722, 1.2716, 1.2925, 1.3073, 1.3011, 1.3064, 1.3050, 1.3056 over the octave grid to T = 2097152.
• census: the bounded packing (-1, 2, 2, 3) to T = 10^7 gives 555198593 circles, depth 3162, 0 broken quadruples and 67163 distinct circles against 67163 counted on the T <= 10^4 control. N(T) is 5, 165, 3325, 67163, 1359167, 27463391, 555198593 at T = 10^1 .. 10^7.
• The same census's exponent by ratio is 1.5185, 1.3043, 1.3053, 1.3061, 1.3055, 1.3057, and the flat reading log N(T)/log T is 1.2492 at T = 10^7, still climbing.
• The bounded packing's curvatures fall in the eight residues 2, 3, 6, 11, 14, 15, 18, 23 mod 24.
• design: base^delta at the literature delta misses every integer for 2 <= base <= 100, the nearest being 52^delta = 174.005426001, then 68, 89, 49, 23, 20; the worst gap is 0.488109816 at base 47.
• The same verb reads the miss as a dimension: the nearest design dimension in the window is log 351/log 89 = 1.305694144, off delta by 0.000007416, then log 247/log 68 = 1.305694579 at 0.000007851.