A374505 Maximum number of unit squares aligned with unit-spaced horizontal lines that can be enclosed by a circle of diameter n.

0, 0, 1, 4, 8, 14, 21, 29, 40, 52, 65, 81, 97, 116, 135, 156, 180, 203, 229, 258, 286, 317, 350, 383, 419, 455, 495, 536, 575, 620, 664, 711, 761, 808, 860, 916, 966, 1024, 1079, 1140, 1200, 1261, 1326, 1391, 1458, 1528, 1595, 1666, 1741, 1814, 1892, 1972

Offset: 0

Author

David Dewan, Jul 09 2024

Keywords

• nonn

Comments

It is conjectured that this construction gives the maximal number of axis-parallel unit squares that can be packed into a circle of diameter n.

From the Erich Friedman website the best known maximum number of unit squares enclosed by a circle of diameter n are for n >= 2: 1, 4, 8, 14, 21, 30, ... (this sequence has not been included in OEIS because the terms have not been proven optimal). The unit squares in this case are not required to be axis-parallel. However, the example of 30 axis-parallel squares enclosed in a circle of radius < 3.5 shows that if holes are allowed, better packings are possible than with the restricted case. - Andrew Howroyd, Jul 14 2024

Examples

			For a circle with diameter = 4:
With center of circle at y = 0 (on line between rows) it encloses 6 squares.
With center of circle at y = 2 - sqrt(3) ~= 0.268 it encloses 8 squares (maximal).
With center of circle at y = 1/2 (in middle of row) it encloses 7 squares.
So a(4) = 8.
		

Links

• David Dewan, Table of n, a(n) for n = 0..2000
• David Dewan, Computing Maximal Unit Squares in a Circle.
• Erich Friedman, Squares in Circles.

Crossrefs

Cf. A124484, A256588 (unexpectedly similar).

Programs

Mathematica

a[n_] := (
  distances = N[Map[Sqrt[n^2 - #^2]/2 &, Range[n - 1]]];
  topDeltas1 = Flatten[Map[# - distances &, Range[n/2]]];
  topDeltas2 = Select[topDeltas1, 0 < # <= .5 &];
  topDeltas3 = Map[{#, 1} &, topDeltas2];
  btmDeltas1 = Flatten[Map[distances - # &, Range[n/2]]];
  btmDeltas2 = Select[btmDeltas1, 0 <= # < .5 &];
  btmDeltas3 = Map[{#, -1} &, btmDeltas2];
  allDeltas4 = Join[topDeltas3, btmDeltas3, {{0, 0}}];
  allDeltas5 = SortBy[allDeltas4, {First, -Last[#] &}] ;
  cumulativeChanges = Accumulate[allDeltas5[[All, 2]]];
  startSqrs = 2 Sum[Floor[2 Sqrt[(n/2)^2 - k^2]], {k, n/2}];
  Return[startSqrs + Max[cumulativeChanges]]  )
Map[a[#] &, Range[0, 51]]      (* this sequence *)
Map[a[#] &, Range[0, 102, 2]]  (* A124484, by radius *)

Formula

a(2*n) <= A124484(n).