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,4

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).

Links

Table of n, a(n) for n=1..70.

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.

Formula

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

Example

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.

Mathematica

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

Crossrefs

Cf. A346232.

Sequence in context: A283371 A116579 A156253 * A265436 A060151 A285902

Adjacent sequences: A346690 A346691 A346692 * A346694 A346695 A346696

Keyword

nonn,easy

Author

Luis Mendo, Aug 02 2021

Status

approved