A346693 Minimum integer length of a segment that touches the interior of n squares on a unit square grid.

1, 1, 1, 2, 2, 3, 3, 4, 5, 6, 6, 7, 8, 8, 9, 10, 10, 11, 12, 13, 13, 14, 15, 15, 16, 17, 17, 18, 19, 20, 20, 21, 22, 22, 23, 24, 25, 25, 26, 27, 27, 28, 29, 30, 30, 31, 32, 32, 33, 34, 34, 35, 36, 37, 37, 38, 39, 39, 40, 41, 42, 42, 43, 44, 44, 45, 46, 46, 47, 48

Offset: 1

Author

Luis Mendo, Aug 02 2021

Keywords

• nonn
• easy

Comments

This sequence, {a(n)}, is the "inverse" of A346232, {b(n)}, in the following sense: a(n) = min{L positive integer with b(L)>=n} and b(n) = max{S positive integer with a(S) <= n}.

The sequence is nondecreasing.

Except for the initial run of 3 equal values, it is formed by runs of 1 or 2 equal values, with an increment of 1 between consecutive runs.

There can be no more than 3 different consecutive terms.

A run of 2 equal values always has 2 different terms before and 2 different terms after the run, except for the initial terms (1, 1, 1, 2, 2, 3, 3).

Examples

			A segment of length 1 can touch a maximum of 3 squares (segment close to a square vertex and oriented at 45 degrees; see image in A346232), therefore a(1) = a(2) = a(3) = 1.
A segment of length 2 can touch a maximum of 5 squares, therefore a(4) = a(5) = 2.
A segment of length 3 can touch a maximum of 7 squares, therefore a(6) = a(7) = 3.
		

Links

• 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, arXiv:2201.03975 [math.MG], 2022-2023.

Crossrefs

Cf. A346232.

Programs

Mathematica

Table[If[n<=3,1,Ceiling[Sqrt[(n-3)^2/2+1]]],{n,70}] (* Stefano Spezia, Aug 03 2021 *)

Formula

a(n) = 1 for n <= 3; a(n) = ceiling(sqrt((n-3)^2/2+1)) for n >= 4.