A394840 Minimum number of triangular cells in a connected polyiamond enclosing an interior hole of exactly n empty triangular cells.

9, 11, 13, 15, 17, 16, 17, 19, 21, 20, 21, 23, 22, 23, 25, 24, 25, 27, 26, 27, 29, 28, 29, 28, 29

Offset

1,1

Comments

A polyiamond is a connected figure of edge-joined equilateral triangles on the triangular lattice. Each cell has exactly 3 edge-neighbors. A "hole" is a maximal connected component of empty cells completely surrounded by occupied cells and not reachable from the exterior. Both the shell (occupied cells) and the hole must be connected.

The sequence is non-monotonic: a(6) < a(5), a(10) < a(9), a(13) < a(12), a(16) < a(15), a(19) < a(18), a(22) < a(21), a(24) < a(23). Drops occur when a more compact hole shape becomes available with smaller perimeter.

Triangular grid analog of A283056 (square grid), where a(n) = A027709(n) + 3. The additive constant "+3" appears in both formulas, suggesting a topological invariant across regular planar tilings.

Proof sketch. Let S be a minimum shell enclosing hole H with |H| = n cells and p = A067628(n) the minimum perimeter of H. (1) By minimality, the adjacency graph of S is a tree (any cycle would allow removing a cell while preserving enclosure), so S union H is simply connected. (2) By the discrete isoperimetric inequality on the triangular lattice, the outer perimeter of S union H satisfies L_out >= A067628(n + |S|). (3) The strict inequality 6n > (p-2)^2 (from the definition of A067628), combined with a parity argument (perimeter and cell count share parity), forces |S| >= 2p + 3 in the non-drop case and |S| >= 2p + 4 at drop positions.

Computed using a SAT solver (CaDiCaL via PySAT) with CEGAR for shell and hole connectivity. Top-down search proves optimality: SAT at k cells, UNSAT at k-1.

Links

Table of n, a(n) for n=1..25.

Peter Exley, Solver code, data, and figures, GitHub.

Formula

a(n) = 2*A067628(n) + 3 + [A067628(n) < A067628(n-1)] for n >= 1, where [P] is the Iverson bracket and A067628(0) = 0 by convention.

Example

For n=1, the hole is a single triangle, so a(1)=9.
For n=2, the hole is a 2-iamond (rhombus), so a(2)=11.
For n=3, the hole is a 3-iamond (trapezoid), so a(3)=13.
For n=4, the hole is a 4-iamond (diamond), so a(4)=15.
For n=5, the hole is a 5-iamond (chevron), so a(5)=17.
For n=6, the hole is a compact 6-iamond (hexagon), so a(6)=16. This is the first drop: a(6) < a(5) because the hexagonal hole has smaller perimeter than the optimal 5-iamond.

Crossrefs

Cf. A067628 (minimum edge-perimeter of n-cell polyiamond), A283056 (square grid analog), A070764 (number of polyiamonds with holes), A327896 (minimum tiles for polyiamond with n separate holes), A027709 (minimum perimeter of n-cell polyomino).

Sequence in context: A070699 A065454 A334688 * A248629 A396179 A383500

Adjacent sequences: A394837 A394838 A394839 * A394841 A394842 A394843

Keyword

nonn,more

Author

Peter Exley, Apr 04 2026

Status

approved