cp's OEIS Frontend

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.

%I A168339 #19 May 05 2023 07:48:07
%S A168339 8,13,17,20,20,24,28,27,31,32,34,36,36,40,41,44,46,45,51,50,51,55,54,
%T A168339 56,56,62,61,62,67,66,68,67,71,74,73,74,80,79,78,80,80,84,87,86,87,89,
%U A168339 93,92,94,93,99,98,100,100,101,104,108,107,106,108,108,114,113,116,115,116
%N 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.
%C A168339 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.
%C A168339 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.
%C A168339 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.
%e A168339 a(1)=8 because to create a rectangle with one hole inside, 8 squares are needed, as follows:
%e A168339 .HHH
%e A168339 .H H
%e A168339 .HHH
%e A168339 a(2)=13 because to create a rectangle with two holes inside, 13 squares are needed, as follows:
%e A168339 .HHHHH
%e A168339 .H H H
%e A168339 .HHHHH
%e A168339 a(3)=17 because to create a rectangle with three holes inside, 17 squares are needed, as follows:
%e A168339 .HHHHH
%e A168339 .H H H
%e A168339 .HH HH
%e A168339 .HHHHH
%e A168339 a(4)=20 because to create a rectangle with four holes inside, 20 squares are needed, as follows:
%e A168339 .HHHHHH
%e A168339 .H H HH
%e A168339 .HH H H
%e A168339 .HHHHHH
%e A168339 a(5)=20 because to create a rectangle with 5 holes inside, 20 squares are needed, as follows:
%e A168339 .HHHHH
%e A168339 .H H H
%e A168339 .HH HH
%e A168339 .H H H
%e A168339 .HHHHH
%t A168339 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 *)
%o A168339 (C)
%o A168339 #include <stdio.h>
%o A168339 main()
%o A168339 {
%o A168339 int holes,cost,c,n,m,maxholes,dimn,dimm;
%o A168339 for(holes=1; holes<=10000; holes++) {
%o A168339 cost=(1<<30);
%o A168339 for(n=1; cost>2*n+6; n++) {
%o A168339 for(m=1; m<=n; m++) {
%o A168339 maxholes=n*m-((n*m)/2);
%o A168339 if(maxholes<holes)continue;
%o A168339 c=2*(n+m+2)+n*m-holes;
%o A168339 if(c<cost) {
%o A168339 cost=c;
%o A168339 dimn=n;
%o A168339 dimm=m;
%o A168339 }
%o A168339 }
%o A168339 }
%o A168339 printf("%d %d %dX%d\n",holes,cost,dimn+2,dimm+2);
%o A168339 fflush(stdout);
%o A168339 }
%o A168339 } /* _R. H. Hardin_, Nov 27 2009 */
%Y A168339 Cf. A143082, A145288, A161357, A161358, A161359, A161369.
%Y A168339 Cf. A118797.
%K A168339 nice,nonn
%O A168339 1,1
%A A168339 _Zhining Yang_, Nov 23 2009
%E A168339 Edited, corrected and extended by _R. H. Hardin_ and _N. J. A. Sloane_, Nov 23 2009, Nov 24 2009, Nov 27 2009
%E A168339 Extended, with output of the Hardin program, by _R. J. Mathar_, Mar 05 2010