A168339 a(n) is the least number of squares needed to form n edge-disjoint 1 X 1 holes inside a rectangle of squares with a solid border.

8, 13, 17, 20, 20, 24, 28, 27, 31, 32, 34, 36, 36, 40, 41, 44, 46, 45, 51, 50, 51, 55, 54, 56, 56, 62, 61, 62, 67, 66, 68, 67, 71, 74, 73, 74, 80, 79, 78, 80, 80, 84, 87, 86, 87, 89, 93, 92, 94, 93, 99, 98, 100, 100, 101, 104, 108, 107, 106, 108, 108, 114, 113, 116, 115, 116

Offset: 1

Author

Zhining Yang, Nov 23 2009

Keywords

• nice
• nonn

Comments

Let the resulting rectangle have size k X l, with a(n) = kl-n. If the border is removed, we have a rectangle of size x X y, where x = k-2, y = l-2. The inner rectangle contains b squares, where b = xy-n = a(n) - 2x - 2y - 4. For k, l, x, y, b see A143082, A145288, A161357, A161358, A161359.

The problem therefore reduces to choosing positive numbers x and y such that floor((xy+1)/2) >= n and (x+2)*(y+2) is minimized.

The largest number of 1 X 1 holes which can put inside an r X r square with a solid border is (for r>=1) 0,0,1,2,5,8,13,18,25,..., which is essentially A000982.

Examples

			a(1)=8 because to create a rectangle with one hole inside, 8 squares are needed, as follows:
.HHH
.H H
.HHH
a(2)=13 because to create a rectangle with two holes inside, 13 squares are needed, as follows:
.HHHHH
.H H H
.HHHHH
a(3)=17 because to create a rectangle with three holes inside, 17 squares are needed, as follows:
.HHHHH
.H H H
.HH HH
.HHHHH
a(4)=20 because to create a rectangle with four holes inside, 20 squares are needed, as follows:
.HHHHHH
.H H HH
.HH H H
.HHHHHH
a(5)=20 because to create a rectangle with 5 holes inside, 20 squares are needed, as follows:
.HHHHH
.H H H
.HH HH
.H H H
.HHHHH
		

Crossrefs

Cf. A143082, A145288, A161357, A161358, A161359, A161369.

Cf. A118797.

Programs

C

#include 
main()
{
int holes,cost,c,n,m,maxholes,dimn,dimm;
for(holes=1; holes<=10000; holes++) {
cost=(1<<30);
for(n=1; cost>2*n+6; n++) {
for(m=1; m<=n; m++) {
maxholes=n*m-((n*m)/2);
if(maxholesR. H. Hardin, Nov 27 2009 */

Mathematica

A168339 = Reap[For[holes = 1, holes <= 10000, holes++, cost = 2^30; For[n = 1, cost > 2*n + 6, n++, For[m = 1, m <= n, m++, maxholes = n*m - Quotient[n*m, 2]; If[maxholes < holes, Continue[]]; c = 2*(n + m + 2) + n*m - holes; If[c < cost, cost = c; dimn = n; dimm = m]]]; Sow[cost]; If[cost > 120, Break[]]]][[2, 1]] (* Jean-François Alcover, May 15 2017, translated from R. H. Hardin's program *)

Extensions

Edited, corrected and extended by R. H. Hardin and N. J. A. Sloane, Nov 23 2009, Nov 24 2009, Nov 27 2009

Extended, with output of the Hardin program, by R. J. Mathar, Mar 05 2010