A346232 Maximum number of squares in a square grid whose interiors can be touched by a (possibly skew) line segment of length n.
3, 5, 7, 8, 9, 11, 12, 14, 15, 17, 18, 19, 21, 22, 24, 25, 27, 28, 29, 31, 32, 34, 35, 36, 38, 39, 41, 42, 43, 45, 46, 48, 49, 51, 52, 53, 55, 56, 58, 59, 60, 62, 63, 65, 66, 68, 69, 70, 72, 73, 75, 76, 77, 79, 80, 82, 83, 85, 86, 87, 89, 90, 92, 93, 94, 96, 97
Offset: 1
Examples
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).
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.
Programs
-
Mathematica
Table[Floor[Sqrt[2*n^2-2]]+3,{n,80}] (* Stefano Spezia, Jul 13 2021 *) -
PARI
a(n) = sqrtint(2*n^2-2) + 3; \\ Michel Marcus, Aug 09 2022
-
Python
from math import isqrt def A346232(n): return isqrt(n**2-1<<1)+3 # Chai Wah Wu, Aug 09 2022
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
Extensions
More terms from Stefano Spezia, Jul 13 2021
Comments