login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A085577 Size of maximal subset of the n^2 cells in an n X n grid such that there are at least 3 edges between any pair of chosen cells. 3
1, 1, 2, 4, 6, 8, 10, 13, 17, 20, 25, 29, 34, 40, 45, 52, 58, 65, 73, 80, 89, 97, 106, 116, 125, 136, 146, 157, 169, 180, 193, 205, 218, 232, 245, 260, 274, 289, 305, 320, 337, 353, 370, 388, 405, 424, 442, 461, 481, 500, 521, 541, 562, 584, 605, 628, 650 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,3

COMMENTS

Equivalently, no pair of chosen cells are closer than a knight's move apart. This is a one-error-correcting code in the Lee metric.

Equivalently, maximal number of 5-celled Greek crosses that can be packed into an n+2 X n+2 chessboard.

A233735(n+2) is a lower bound on a(n).

Conjecture: if n == 4 (mod 5), then a(n)=(n^2+4)/5. - Erich Friedman, Apr 19 2015

More general conjecture: if n != 5, then a(n) = ceil(n^2/5). - Rob Pratt, Jul 10 2015

Conjecture holds for n <= 70. - Giovanni Resta, Jul 29 2015

LINKS

Giovanni Resta, Table of n, a(n) for n = 1..70

Kival Ngaokrajang, Packings of A233735(n) Greek crosses. [Note that it is possible to pack 17 Greek crosses into an 11 X 11 grid (see EXAMPLES), so these arrangements are not always optimal.]

Popular Computing (Calabasas, CA), Problem 175: Knights Away, Vol. 5, (No. 50, May 1977), pp. PC50-18 to PC50-19.

FORMULA

a(n) approaches n^2/5 as n -> infinity.

From Colin Barker, Oct 15 2016: (Start)

Conjectures:

a(n) = 2*a(n-1)-a(n-2)+a(n-5)-2*a(n-6)+a(n-7) for n>8.

G.f.: x*(1-x+x^2+x^3-x^5+x^6-x^9+2*x^10-x^11) / ((1-x)^3*(1+x+x^2+x^3+x^4)). (End)

EXAMPLE

For example, a(3) = 2:

..o

...

o..

a(9)=17 (from Erich Friedman, Apr 18 2015):

.o....o..

...o....o

o....o...

..o....o.

....o....

.o....o..

...o....o

o....o...

..o....o.

MATHEMATICA

(* Warning: this program gives correct results up to n=70, but must not be used to extend the sequence beyond that limit. *) a[n_] := a[n] = If[n <= 9, {1, 1, 2, 4, 6, 8, 10, 13, 17}[[n]], n^2 - 4*n + 8 - a[n-4] - a[n-3] - a[n-2] - a[n-1]]; Table[a[n], {n, 1, 70}] (* Jean-Fran├žois Alcover, Nov 24 2016 *)

CROSSREFS

Main diagonal of A085576.

Cf. A233735.

Sequence in context: A056827 A024172 A233735 * A121832 A253241 A302979

Adjacent sequences:  A085574 A085575 A085576 * A085578 A085579 A085580

KEYWORD

nonn,nice

AUTHOR

N. J. A. Sloane, Jul 08 2003; entry revised Apr 19 2015

EXTENSIONS

a(14)-a(30) from Rob Pratt, Jul 10 2015

a(31)-a(57) from Giovanni Resta, Jul 29 2015

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 September 16 18:45 EDT 2019. Contains 327117 sequences. (Running on oeis4.)