login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 7
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,1

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.

LINKS

Table of n, a(n) for n=1..66.

EXAMPLE

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

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 *)

PROG

(C program from R. H. Hardin)

#include <stdio.h>

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<holes)continue;

c=2*(n+m+2)+n*m-holes;

if(c<cost) {

cost=c;

dimn=n;

dimm=m;

}

}

}

printf("%d %d %dX%d\n", holes, cost, dimn+2, dimm+2);

fflush(stdout);

}

}

CROSSREFS

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

Cf. A118797.

Sequence in context: A057486 A188198 A129410 * A070112 A070113 A178968

Adjacent sequences:  A168336 A168337 A168338 * A168340 A168341 A168342

KEYWORD

nice,nonn

AUTHOR

Zhining Yang, Nov 23 2009

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 - R. J. Mathar, Mar 05 2010

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 4 15:50 EDT 2020. Contains 336202 sequences. (Running on oeis4.)