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