OFFSET
1,1
COMMENTS
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).
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
LINKS
Luis Mendo, Solutions for n = 1, 2, 3
Code Golf & Coding Challenges, Maximum number of squares touched by a line segment
Alex Arkhipov and Luis Mendo, On the number of tiles visited by a line segment on a rectangular grid, Mathematika, vol. 69, no. 4, pp. 1242-1281, October 2023. Also on Arxiv.
FORMULA
a(n) = i+j-1 with i = ceiling(n/sqrt(2))+1, j = ceiling(sqrt(n^2-(i-2)^2))+1.
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.
a(n) = max{m with m integer such that m^2 - 6*m + 10 - m mod 2 < 2*n^2}.
a(n) = floor(sqrt(2*n^2-2))+3. - Alex Arkhipov, Jul 11 2021
EXAMPLE
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).
MATHEMATICA
Table[Floor[Sqrt[2*n^2-2]]+3, {n, 80}] (* Stefano Spezia, Jul 13 2021 *)
PROG
(Python)
from math import isqrt
def A346232(n): return isqrt(n**2-1<<1)+3 # Chai Wah Wu, Aug 09 2022
(PARI) a(n) = sqrtint(2*n^2-2) + 3; \\ Michel Marcus, Aug 09 2022
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Luis Mendo, Jul 11 2021
EXTENSIONS
More terms from Stefano Spezia, Jul 13 2021
STATUS
approved