cp's OEIS Frontend

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.

%I A085577 #59 Aug 11 2025 16:28:59
%S A085577 1,1,2,4,6,8,10,13,17,20,25,29,34,40,45,52,58,65,73,80,89,97,106,116,
%T A085577 125,136,146,157,169,180,193,205,218,232,245,260,274,289,305,320,337,
%U A085577 353,370,388,405,424,442,461,481,500,521,541,562,584,605,628,650
%N 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.
%C A085577 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.
%C A085577 Equivalently, maximal number of 5-celled Greek crosses that can be packed into an n+2 X n+2 chessboard.
%C A085577 A233735(n+2) is a lower bound on a(n).
%C A085577 Conjecture: if n == 4 (mod 5), then a(n)=(n^2+4)/5. - _Erich Friedman_, Apr 19 2015
%C A085577 More general conjecture: if n != 5, then a(n) = ceiling(n^2/5). - _Rob Pratt_, Jul 10 2015
%C A085577 Conjecture holds for n <= 70. - _Giovanni Resta_, Jul 29 2015
%H A085577 Giovanni Resta, <a href="/A085577/b085577.txt">Table of n, a(n) for n = 1..70</a>
%H A085577 Kival Ngaokrajang, <a href="/A233735/a233735.pdf">Packings of A233735(n) Greek crosses.</a> [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.]
%H A085577 Popular Computing (Calabasas, CA), <a href="/A233735/a233735_1.pdf">Problem 175: Knights Away</a>, Vol. 5, (No. 50, May 1977), pp. PC50-18 to PC50-19.
%F A085577 a(n) approaches n^2/5 as n -> infinity.
%F A085577 From _Colin Barker_, Oct 15 2016: (Start)
%F A085577 Conjectures:
%F A085577 a(n) = 2*a(n-1) - a(n-2) + a(n-5) - 2*a(n-6) + a(n-7) for n > 8.
%F A085577 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)
%e A085577 For example, a(3) = 2:
%e A085577   ..o
%e A085577   ...
%e A085577   o..
%e A085577 a(9)=17 (from _Erich Friedman_, Apr 18 2015):
%e A085577   .o....o..
%e A085577   ...o....o
%e A085577   o....o...
%e A085577   ..o....o.
%e A085577   ....o....
%e A085577   .o....o..
%e A085577   ...o....o
%e A085577   o....o...
%e A085577   ..o....o.
%t A085577 (* 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 *)
%Y A085577 Main diagonal of A085576.
%Y A085577 Cf. A233735.
%K A085577 nonn,nice
%O A085577 1,3
%A A085577 _N. J. A. Sloane_, Jul 08 2003; entry revised Apr 19 2015
%E A085577 a(14)-a(30) from _Rob Pratt_, Jul 10 2015
%E A085577 a(31)-a(57) from _Giovanni Resta_, Jul 29 2015