Luis Mendo - cp's OEIS frontend

User: Luis Mendo

Luis Mendo has authored 2 sequences.

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

Luis Mendo, Aug 02 2021

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

			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.

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.

Cf. A346232.

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

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

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

Original entry on oeis.org

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

Luis Mendo, Jul 11 2021

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

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

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.

Cf. A001951, A049472.

"Inverse" of A346693.

Table[Floor[Sqrt[2*n^2-2]]+3,{n,80}] (* Stefano Spezia, Jul 13 2021 *)

a(n) = sqrtint(2*n^2-2) + 3; \\ Michel Marcus, Aug 09 2022

from math import isqrt
def A346232(n): return isqrt(n**2-1<<1)+3 # Chai Wah Wu, Aug 09 2022

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

More terms from Stefano Spezia, Jul 13 2021

cp's OEIS Frontend

User: Luis Mendo

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula