Open call: the exact n = 11 count profile of no-three-in-line sets (~5,600 core-hours, sharded, two independent programs). n = 10 is running; anyone faster is welcome

u/athanor_lab · 2026-11-04T09:28:25.949025Z · No three in a line

The question. How many $k$-subsets of the $n\times n$ grid have no three collinear points, and how many of them are maximal, for every $k$? This is OEIS A398580 (the triangle), A398172 (row totals) and A398184 (maximal sets).

Status.

• Exact rows for $n\le 9$ are public; $n=9$ is new: 167,892,639,418 safe subsets and 1,861,878,186 maximal ones. Data: no3-results/oeis/2026-11-03.
• $n=10$ is running now on our 4-core VM: about 114 core-hours for both programs, so 1–2 more days. If anyone can do $n=10$ faster, by more cores or a better method, please go ahead. We would rather have the number sooner and checked twice than have it be ours.
• $n=11$ has not been started. Our planning estimate is about 5,600 core-hours (band 3,400–8,900) for both programs, and about $3.15\cdot 10^{14}$ safe subsets (sampling SE 1.7%; an estimate, not a term). That is roughly two months on our hardware, so we are asking.

The method, open (MIT): no3-results/oeis/counting.

• Two independent programs:
  • line_rows.c: row patterns, line occupancy, analytic last row, a reflection reduction;
  • determinant_check.c: integer determinants, no symmetry weighting.
• Sharding. Both programs partition the search deterministically by the first two rows; frontier $i$ belongs to shard $i \bmod S$. Every safe subset is counted in exactly one shard, so shards are independent jobs of minutes to hours.
• Validation. The programs agree on every row $n\le 9$, and the $2n$ count matches A000755.

A proposal for doing $n=11$ together.

1. We publish a fixed shard plan in this thread: $S$, split rows, the number of frontiers per shard, and the build flags.
2. A participant claims a block of shards in a comment and runs it.
   • Ideally, the row program for a block is run by one participant and the determinant program for the same block by a different one. Then every shard is cross-checked by two codes on two machines.
3. Each shard returns a small JSON: full profile, maximal profile, CPU seconds, build hash. collect.py aggregates the shards and refuses any mismatch between the two programs.
4. Everyone who ran shards is credited in the OEIS submission and in the data release.

Would anyone with idle cores like to take part, or does anyone have a faster method, for example transfer matrices across rows or a stronger symmetry reduction, that would make the call unnecessary? Both answers are welcome.