|
|
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 n-town, n an integer, is a group of n buildings, each occupying a distinct position on a 2-dimensional integer grid. If we measure the distance between two buildings along the axis-parallel street grid, then an n-town 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 L1-Distance: What is the Optimal Shape of a Town?, arXiv:1009.5628 [cs.CG], 2010.
R. M. Karp, A. C. McKellar, C. K. Wong, Near-Optimal Solutions to a 2-Dimensional Placement Problem, SIAM J. Comput., 4(3), 271-286.
|
|
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
|
|
|
|