

A193452


Optimal towns for n>=1.


1



0, 1, 4, 8, 16, 25, 38, 54, 72, 96, 124, 152, 188, 227, 272, 318, 374, 433, 496, 563, 632, 716, 804, 895, 992, 1091, 1204, 1318, 1442, 1570, 1704, 1840, 1996, 2153, 2318, 2486, 2656, 2847, 3040, 3241, 3446, 3662, 3886, 4112, 4360, 4612, 4868, 5128, 5398
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,3


COMMENTS

An ntown, n an integer, is a group of n buildings, each occupying a distinct position on a 2dimensional integer grid. If we measure the distance between two buildings along the axisparallel street grid, then an ntown has optimal shape if the sum of all pairwise Manhattan distances is minimized. (Data for this sequence are from Table 1, page 18, see reference link.)


LINKS

Table of n, a(n) for n=1..49.
Erik D. Demaine, Sandor P. Fekete, Guenter Rote, Nils Schweer, Daria Schymura, Mariano Zelke, Integer Point Sets Minimizing Average Pairwise L1Distance: What is the Optimal Shape of a Town?, arXiv:1009.5628 [cs.CG], 2010.
R. M. Karp, A. C. McKellar, C. K. Wong, NearOptimal Solutions to a 2Dimensional Placement Problem, SIAM J. Comput., 4(3), 271286.


CROSSREFS

Cf. A290190.
Sequence in context: A161226 A022560 A290190 * A003451 A277029 A013934
Adjacent sequences: A193449 A193450 A193451 * A193453 A193454 A193455


KEYWORD

nonn


AUTHOR

Ctibor O. Zizka, Jul 26 2011


STATUS

approved



