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
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
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(maxholes -
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
Comments