Lennard-Jones clusters, minimum energy

# Lennard-Jones clusters, minimum energy ## Goal `cluster.py` exposes `cluster(n: int, time_budget: float, seed: int) -> list[tuple[float, float, float]]`: `n` atoms `(x, y, z)` anywhere in 3-D space. Minimise the Lennard-Jones energy E = sum over i < j of 4 (r_ij^-12 - r_ij^-6), r_ij = |x_i - x_j| in reduced units (pair well depth 1, sigma 1, so the pair minimum sits at r = 2^(1/6)). Fifteen values of `n` between 20 and 150 are the benchmark. Lennard-Jones clusters are the standard test bed for global optimisation of configurational problems (basin hopping was introduced on them, Wales and Doye 1997). Most putative global minima are Mackay icosahedra; the exceptions, an fcc truncated octahedron at `n = 38`, Marks decahedra at `n = 75, 76, 77, 102, 103, 104` and a tetrahedral structure at `n = 98`, are the classic hard cases because their basins are tiny compared with the icosahedral funnel. All eight are in this set. ## Metric metric = mean over n in NS of E(n) / record(n) Both energies are negative, so 1.0 means matching every record and above 1.0 means beating at least one (a lower, more negative energy gives a larger ratio). A cluster with `E >= 0` scores 0 for that `n`. The eval recomputes the energy itself from the returned coordinates; a wrong count, a non-finite coordinate, two coincident atoms (`r < 1e-9`) or a non-finite energy is a failed run. Nothing your solver reports is used. `ZT_EVAL_SEED` only changes the `seed` handed to `cluster`, so your method must be robust to its starting point. ## Records Best-known energies from the Cambridge Cluster Database "Table of Lennard-Jones Cluster Global Minima" (D. J. Wales and J. P. K. Doye, J. Phys. Chem. A 101, 5111 (1997) and the references it credits; https://www-wales.ch.cam.ac.uk/~wales/CCD/jon/structures/LJ/tables.150.html, fetched 2026-09-07), exactly as printed there (6 decimals). Every entry was recomputed from the database's own points file and agrees to within 1.2e-6. None is proven optimal: no LJ_N global minimum with `n > 4` has a proof. An energy below a record by more than 1e-5 is listed in `records_beaten`. | n | record E | point group | structure | first reported | |---|---|---|---|---| | 20 | -77.177043 | C2v | icosahedral | Hoare | | 26 | -108.315616 | Td | icosahedral | Hoare | | 31 | -133.586422 | Cs | icosahedral | Northby | | 38 | -173.928427 | Oh | fcc truncated octahedron | Gomez, Pillardy, Doye | | 55 | -279.248470 | Ih | Mackay icosahedron | Hoare | | 69 | -359.882566 | C5v | icosahedral | Wales, Barron, Leary | | 75 | -397.492331 | D5h | Marks decahedron | Doye | | 76 | -402.894866 | Cs | Marks decahedron | Doye | | 77 | -409.083517 | C2v | Marks decahedron | Doye | | 98 | -543.665361 | Td | tetrahedral | Leary | | 102 | -569.363652 | C2v | Marks decahedron | Doye | | 103 | -575.766131 | Cs | Marks decahedron | Doye | | 104 | -582.086642 | C2v | Marks decahedron | Doye | | 110 | -621.788224 | Cs | icosahedral | Northby | | 150 | -893.310258 | C3v | icosahedral | Northby | For the non-icosahedral `n` the same table lists the lowest icosahedral minimum, which is what an unbiased search usually finds first: `n = 38` -173.252378, `75` -396.282249, `76` -402.384580, `77` -408.518265, `98` -543.642957, `102` -569.277721, `103` -575.658879, `104` -582.038429. Those gaps (0.02 to 1.2 in energy, ratio 0.99996 to 0.997) are the signal in this benchmark. ## Constraints - Standard library only. No numpy, no scipy. The eval rejects other imports. - Respect `time_budget` (seconds, per call). The eval fails a call that runs past 1.25x + 3 s. - Deterministic given `seed`: use `random.Random(seed)`. ## Iterating - `ZT_EVAL_NS=38,75` runs a subset of n; `ZT_EVAL_PER_N_SECONDS=2` shortens the per-n budget. The default is all fifteen n at 7 s each (about 110 s). Run `python eval.py` in your workspace. - The per-n detail in the eval output shows which n are furthest from their record. ## Ideas that are known to matter (check the journal before repeating one) - The landscape has exponentially many minima; one descent from a lattice cut or a random start lands a few per cent above the record. Basin hopping (perturb, locally minimise, Metropolis accept at kT about 0.8) is what found most of these entries; a local minimiser that converges properly (L-BFGS or conjugate gradient in a few hundred pair-loop evaluations) is the core of it. - Seed with the right shape: a Mackay icosahedron with the outer shell filled by a greedy anti-Mackay/Mackay growth reaches the icosahedral minima directly, and `n = 55` and `n = 13` are complete icosahedra. For the hard `n`, start from a truncated octahedron (38), a Marks decahedron (75-77, 102-104) or the Leary tetrahedron (98); the icosahedral funnel will not find them in a 7 s budget. - Surface moves beat random kicks: remove the highest-energy atom and re-place it at the lowest energy surface site, then re-minimise. - The ratio only rounds to 1.0 once you are within about 1e-8 relative, so finish each minimum with a well-converged local optimiser. - The pure-Python pair loop is the bottleneck: cache differences, avoid function-call overhead, compute energy and forces in one pass, and skip pairs beyond a cutoff (about 2.5 sigma) during minimisation while keeping the full sum for the final energy. 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.