Unit equilateral triangles in an equilateral triangle, minimum container side

# Unit equilateral triangles in an equilateral triangle, minimum container side ## Goal `pack.py` exposes `pack(n: int, time_budget: float, seed: int) -> list[tuple[float, float, float]]`: `n` unit equilateral triangles `(cx, cy, theta)`, where `(cx, cy)` is the centre (centroid) and `theta` is the direction, in **radians**, from the centre to the first vertex; the vertices are `(cx, cy) + (1/sqrt(3)) (cos(theta + 2 pi k / 3), sin(theta + 2 pi k / 3))` for `k = 0, 1, 2`, so `theta = pi/2` is an upward-pointing triangle and `theta = -pi/2` a downward one. Interiors must be pairwise disjoint (touching is fine). The container is the smallest **upward-pointing** equilateral triangle that holds every vertex you return; the eval derives its side `s` from your placements, you never report it. Minimise `s`. This is "Triangles in Triangles" from Erich Friedman's Packing Center. `s(n)` is the side of the smallest equilateral triangle containing `n` unit equilateral triangles. `s(k^2) = k` is trivial and `s(5) = 1 + sqrt(3)` is proven (Friedman, 1997); the page says "most of these have not been proven". The 24 instances here are the values of `n` between 6 and 50 whose record is a non-trivial construction and is not marked proven. Several rows were improved as recently as April-June 2026. Beat any row and you have a new Packing Center record. ## Metric metric = mean over the 24 instances of best_known(n) / s(n) `s(n)` is computed by pushing the three edges of an upward-pointing equilateral triangle in until each touches one of your `3n` vertices; by Viviani's theorem the height of that triangle is minus the sum of the three edge offsets, and `s = height / (sqrt(3)/2)`. A packing that matches a record scores `1.0` on that `n` (a hair under it where the record is only known as a truncated decimal, see the table) and anything better scores above `1.0`. The eval validates every triangle before it measures anything: finite numbers, and no pair of triangles overlapping by more than `EPS = 1e-9`, tested with the separating axis theorem on the six edge normals, the same geometry and tolerance as this repository's square-packing packs. Touching is fine and penetration up to `EPS` is forgiven. A wrong answer on any `n` is a failed run. `ZT_EVAL_SEED` only changes the `seed` handed to your solver, so your method must be robust to its starting point. The container's orientation is fixed (pointing up) but yours is not: rotate and translate the whole packing freely; only the minimal enclosing upward triangle is measured. ## Records Source: https://erich-friedman.github.io/packing/triintri/, read 2026-09-07. Where the page gives a closed form the eval evaluates it in full precision. Where it gives only a decimal with a trailing `+` (its notation for a truncated value, e.g. `3.992+` means `3.992 <= s < 3.993`), the eval uses the printed digits verbatim: reproducing the true record then scores at most about `0.9998` on that `n`, and `records_beaten` is only flagged when you get below the printed digits. None of these rows is marked proven on the page. | n | best known s | exact form (per the page) | found by | |---|---|---|---| | 6 | 2.977+ | 13/8 + 3 sqrt(13)/8 | Maurizio Morandi, August 2008 | | 10 | 3.5 | 7/2 | Erich Friedman, 1997 | | 11 | 3.722+ | 9/4 + 9 sqrt(21)/28 | Erich Friedman, 1997 | | 12 | 3.879+ | 2 + 2 cos(pi/9) | David W. Cantrell, July 2007 | | 13 | 3.992+ | none given (truncated decimal) | Maurizio Morandi, May 2008 | | 17 | 4.465+ | none given (truncated decimal) | Maurizio Morandi, May 2008 | | 18 | 4.5 | 9/2 | Erich Friedman, 1997 | | 19 | 4.666+ | 14/3 | Maurizio Morandi, May 2008 | | 20 | 4.861+ | 33/8 + 9 sqrt(21)/56 | Maurizio Morandi, May 2008 | | 21 | 4.923+ | none given (truncated decimal) | Maurizio Morandi, May 2008 | | 22 | 4.996+ | none given (truncated decimal) | Maurizio Morandi, May 2008 | | 26 | 5.406+ | none given (truncated decimal) | Joah Frenzley, April 2026 | | 29 | 5.666+ | 17/3 | David W. Cantrell, July 2007 | | 30 | 5.75 | 23/4 | Maurizio Morandi, May 2008 | | 31 | 5.90766+ | none given (truncated decimal) | Thomas Schadt, June 2026 | | 32 | 5.94593+ | none given (truncated decimal) | Maurizio Morandi, May 2026 | | 33 | 5.99759+ | none given (truncated decimal) | Maurizio Morandi, June 2026 | | 37 | 6.333+ | 19/3 | Ian Watson, April 2026 | | 38 | 6.42823+ | none given (truncated decimal) | Thomas Schadt, June 2026 | | 41 | 6.666+ | 20/3 | Emerson Connelly, May 2026 | | 42 | 6.75 | 27/4 | Emerson Connelly, May 2026 | | 43 | 6.8 | 34/5 | Emerson Connelly, May 2026 | | 44 | 6.93076+ | none given (truncated decimal) | Thomas Schadt, June 2026 | | 50 | 7.32732+ | 7 + sqrt(21)/14 | Maurizio Morandi, May 2026 | Not included, for the record: `s = k` for `n = k^2 - 2, k^2 - 1, k^2` (the trivial tiling; the page lists these as "Trivial"), `s(5) = 1 + sqrt(3)` (proven), and `n = 27, 28` (`s = 11/2`, Friedman 1997) and `n = 39, 40` (`s = 13/2`, Friedman, April 2026), which share a packing with a larger `n` and were left out to keep the set to 24. Also `n = 45, 46` (Morandi, May-June 2026: `6.95922+`, `6.99837+`), left out only for size. ## Constraints - Standard library only. No numpy, no scipy. The eval rejects other imports. - Respect `time_budget` (seconds, per call). The eval kills a call at `1.25 * time_budget + 3 s`. - Deterministic given `seed`: use `random.Random(seed)`. ## Iterating quickly - `ZT_EVAL_NS=6,10 python eval.py` runs a subset of the instances. - `ZT_EVAL_PER_N_SECONDS=1 python eval.py` shortens the per-`n` budget (default 4 s, so the full 24-instance eval takes about 100 s of solver time). ## Ideas that are known to matter (check the journal before repeating one) - The rational records (`7/2`, `9/2`, `14/3`, `17/3`, `23/4`, `19/3`, `20/3`, `27/4`, `34/5`) are the trivial tiling of a side-`k` triangle with one or two rows re-packed by triangles shifted half a unit or flipped: `k` triangles of a row can be replaced by `k + 1` up-and-down triangles in a strip of height `sqrt(3)/2` only with slack, so the trick is a row of height slightly more than `sqrt(3)/2` that holds one extra triangle. Write the families down before searching. - The remaining records use triangles rotated by angles other than multiples of 60 degrees wedged into corners; the `2 + 2 cos(pi/9)` record for `n = 12` is the model case. - Simulated annealing on `(cx, cy, theta)` with a penalty for overlap plus the container side (the three edge offsets are cheap to update incrementally), shrinking the container whenever the packing is feasible, is what produced the 2026 records; restart often. - Finish every candidate with a feasibility projection that pushes overlapping pairs apart along their separating axis, then re-measure the container. Write one honest line in `NOTES.md`: the idea, and which `n` it helped. Simpler is better: all else equal prefer the shorter solver, and treat removing code for an equal score as a win. Log every experiment, including discards, in your results.tsv.