cp's OEIS Frontend

A346232 Maximum number of squares in a square grid whose interiors can be touched by a (possibly skew) line segment of length n.

%I A346232 #57 Oct 18 2023 10:06:07
%S A346232 3,5,7,8,9,11,12,14,15,17,18,19,21,22,24,25,27,28,29,31,32,34,35,36,
%T A346232 38,39,41,42,43,45,46,48,49,51,52,53,55,56,58,59,60,62,63,65,66,68,69,
%U A346232 70,72,73,75,76,77,79,80,82,83,85,86,87,89,90,92,93,94,96,97
%N A346232 Maximum number of squares in a square grid whose interiors can be touched by a (possibly skew) line segment of length n.
%C A346232 In order to derive the formulas below, the following two facts are useful. Let i, j be arbitrary nonnegative integers. (1) A segment with length slightly greater than sqrt(i^2+j^2) can touch i+j+3 squares, if it is aligned from (0,0) to (i,j) and then shifted a little. (2) For a given length, it suffices to consider segments aligned from (0,0) to either (i,i) or (i,i+1) (other orientations result in a smaller number of squares touched).
%C A346232 The sequence is increasing, with a(n+1)-a(n) equal to 1 or 2. There can be no more than two consecutive increments equal to 1. Increments equal to 2 always appear isolated, except at the initial sequence terms (3,5,7). - _Luis Mendo_, Jul 29 2021
%H A346232 Luis Mendo, <a href="/A346232/a346232.png">Solutions for n = 1, 2, 3</a>
%H A346232 Code Golf & Coding Challenges, <a href="https://codegolf.stackexchange.com/q/231176/36398">Maximum number of squares touched by a line segment</a>
%H A346232 Alex Arkhipov and Luis Mendo, <a href="https://londmathsoc.onlinelibrary.wiley.com/doi/full/10.1112/mtk.12223">On the number of tiles visited by a line segment on a rectangular grid</a>, Mathematika, vol. 69, no. 4, pp. 1242-1281, October 2023. Also on <a href="https://arxiv.org/abs/2201.03975">Arxiv</a>.
%F A346232 a(n) = i+j-1 with i = ceiling(n/sqrt(2))+1, j = ceiling(sqrt(n^2-(i-2)^2))+1.
%F A346232 a(n) = i+j-1 with i = ceiling((sqrt(2*n^2-1)+1)/2)+1, j = ceiling(sqrt(n^2-(i-2)^2))+1.
%F A346232 a(n) = max{m with m integer such that m^2 - 6*m + 10 - m mod 2 < 2*n^2}.
%F A346232 a(n) = floor(sqrt(2*n^2-2))+3. - _Alex Arkhipov_, Jul 11 2021
%e A346232 For n = 1, a line segment with its center close to a square vertex and oriented at 45 degrees with respect to the grid touches 3 squares (see image linked above).
%t A346232 Table[Floor[Sqrt[2*n^2-2]]+3,{n,80}] (* _Stefano Spezia_, Jul 13 2021 *)
%o A346232 (Python)
%o A346232 from math import isqrt
%o A346232 def A346232(n): return isqrt(n**2-1<<1)+3 # _Chai Wah Wu_, Aug 09 2022
%o A346232 (PARI) a(n) = sqrtint(2*n^2-2) + 3; \\ _Michel Marcus_, Aug 09 2022
%Y A346232 Cf. A001951, A049472.
%Y A346232 "Inverse" of A346693.
%K A346232 nonn,easy
%O A346232 1,1
%A A346232 _Luis Mendo_, Jul 11 2021
%E A346232 More terms from _Stefano Spezia_, Jul 13 2021