login
Minimal perimeter of polyomino with n square cells.
16

%I #56 Aug 06 2024 07:28:16

%S 0,4,6,8,8,10,10,12,12,12,14,14,14,16,16,16,16,18,18,18,18,20,20,20,

%T 20,20,22,22,22,22,22,24,24,24,24,24,24,26,26,26,26,26,26,28,28,28,28,

%U 28,28,28,30,30,30,30,30,30,30,32,32,32,32,32,32,32,32,34,34,34,34,34,34

%N Minimal perimeter of polyomino with n square cells.

%D F. Harary and H. Harborth, Extremal Animals, Journal of Combinatorics, Information & System Sciences, Vol. 1, No 1, 1-8 (1976).

%D W. C. Yang, Optimal polyform domain decomposition (PhD Dissertation), Computer Sciences Department, University of Wisconsin-Madison, 2003.

%H Reinhard Zumkeller, <a href="/A027709/b027709.txt">Table of n, a(n) for n = 0..10000</a>

%H Greg Malen, Érika Roldán, and Rosemberg Toalá-Enríquez, <a href="https://doi.org/10.1007/s00026-022-00631-1">Extremal {p, q}-Animals</a>, Ann. Comb. (2023). See Corollary 1.9 at p. 8.

%H Henri Picciotto, <a href="http://www.mathedpage.org/geometry-labs/">Geometry Labs</a>, Labs 8.1-8.3.

%H J. Yackel, R. R. Meyer and I. Christou, <a href="https://citeseerx.ist.psu.edu/pdf/4174091178f0abc27ab6404fa241575a1f16bdc4">Minimum-perimeter domain assignment</a>, Mathematical Programming, vol. 78 (1997), pp. 283-303.

%H Jason R. Zimba, <a href="http://jzimba.blogspot.com/2015/06/solution-to-perimeter-puzzle.html">Solution to Perimeter Problem</a>, Jan 23 2015

%F a(n) = 2*ceiling(2*sqrt(n)).

%F a(n) = 2*A027434(n) for n > 0. - _Tanya Khovanova_, Mar 04 2008

%e a(5) = 10 because we can arrange 5 squares into 2 rows, with 2 squares in the top row and 3 squares in the bottom row. This shape has perimeter 10, which is minimal for 5 squares.

%p interface(quiet=true); for n from 0 to 100 do printf("%d,", 2*ceil(2*sqrt(n))) od;

%t Table[2*Ceiling[2*Sqrt[n]], {n, 0, 100}] (* _Wesley Ivan Hurt_, Mar 01 2014 *)

%o (Haskell)

%o a027709 0 = 0

%o a027709 n = a027434 n * 2 -- _Reinhard Zumkeller_, Mar 23 2013

%o (Magma) [2*Ceiling(2*Sqrt(n)): n in [0..100]]; // _Vincenzo Librandi_, May 11 2015

%o (Python)

%o from math import isqrt

%o def A027709(n): return 1+isqrt((n<<2)-1)<<1 if n else 0 # _Chai Wah Wu_, Jul 28 2022

%Y Cf. A000105, A067628 (analog for triangles), A075777 (analog for cubes).

%Y Cf. A135711.

%Y Number of such polyominoes is in A100092.

%K easy,nonn

%O 0,2

%A Jonathan Custance (jevc(AT)atml.co.uk)

%E Edited by Winston C. Yang (winston(AT)cs.wisc.edu), Feb 02 2002