

A325946


Maximum number of intercardinal adjacencies among all ncelled polyplets.


0



0, 1, 3, 6, 8, 11, 14, 17, 20, 23, 26, 30, 33, 36, 39, 43, 46, 49, 53, 56, 60, 63, 66, 70, 73, 77, 80, 84, 87, 91, 94, 98, 101, 105, 108, 112, 116, 119, 123, 126, 130, 133, 137, 141, 144, 148, 151, 155, 159, 162, 166, 170, 173, 177, 180, 184, 188, 191, 195, 199, 202, 206, 210, 213, 217, 221, 224, 228, 232, 235, 239, 243, 246, 250, 254
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,3


COMMENTS

A123663 provides the maximum number of cardinal adjacencies among ncelled polyominoes. The sequence under consideration here provides the maximum number of intercardinal (edgetoedge and vertextovertex) adjacencies among all ncelled polyplets.
Both A123663 and this sequence are used by landscape ecologists and geographic information system (GIS) professionals to determine quantitative measures over time of landscape erosion in high density coastal areas.
For initial terms n <= 20, M_O(n) is known to be optimal; for n > 20, the optimality of M_O(n) is probable.  Nicholas P. Taliceo, Jul 12 2021


LINKS



FORMULA

By empirical observation a splitrule formula with 15 conditions generates the sequence M = 0, 1, 3, 6, 8, 11, ... correctly for small n  this includes comparison with configurations known to be optimal (n < 20) and with computer generated searches for optimal configurations (n < 500):
M_O(n) = 4n  14p + 10  e
where
n = number of tiles in the polyplet t
p = Max{p>=1 : n >= 7p^210p+4}
e = 0, if n = 7p^2  10p + 4
e = 1, if 7p^2  10p + 4 < n <= 7p^2  9p + 3
e = 2, if 7p^2  9p + 3 < n <= 7p^2  8p + 2
e = 3, if 7p^2  8p + 2 < n <= 7p^2  7p + 2
e = 4, if 7p^2  7p + 2 < n <= 7p^2  6p + 1
e = 5, if 7p^2  6p + 1 < n <= 7p^2  5p + 1
e = 6, if 7p^2  5p + 1 < n <= 7p^2  4p + 1
e = 7, if 7p^2  4p + 1 < n <= 7p^2  3p
e = 8, if 7p^2  3p < n <= 7p^2  2p
e = 9, if 7p^2  2p < n <= 7p^2  p
e = 10, if 7p^2  p < n <= 7p^2
e = 11, if 7p^2 < n <= 7p^2 + p
e = 12, if 7p^2 + p < n <= 7p^2 + 2p
e = 13, if 7p^2 + 2p < n <= 7p^2 + 3p
e = 14, if n > 7p^2 + 3p
This splitrule formula is derived geometrically using an approach described in the Example section.
Subsequently we have proved that M_O can be represented analytically by a single expression: M_O(n) = 4nceiling(sqrt(28n12)).
We have proved the important estimate M_O(n) <= M(n) <= 2*(2n2*ceiling(sqrt(n))) where 2n2*ceiling(sqrt(n)) is A123663. This upper bound is not sharp for small n. The relative difference between M_O(n) and 2*(2n2*ceiling(sqrt(n))) is less than 3% for at least 145 <= n <= 10^7 tiles and the relative difference goes to zero. For practical uses like GIS, our formula will have very small relative error if, in fact, it does not describe the sequence exactly.


EXAMPLE

For n = 12, the optimal configuration is a "regular octagon" of side length two (i.e., the symmetric, crossshaped configuration with rows of length 2, 4, 4, and 2). This yields 30 intercardinal adjacencies.
In general, when n = 7p^2  10p + 4 the n tiles can be arranged into the shape of a regular octagon with side length p and 28p^2  54p + 26 intercardinal adjacencies. We conjecture these are optimal.
Moreover, we believe all of the intermediary cases are generated by a family of archetypes where one moves from a regular octagon to a "stretched octagon" to a "small corners octagon" and then to the next largest regular octagon. This geometric approach gives rise to the split rule formula described above.


PROG

(Python) # See N. P. Taliceo link.


CROSSREFS

The Aggregation Index is cataloged as A123663.


KEYWORD

nonn


AUTHOR



STATUS

approved



