A328803 -id:A328803 - cp's OEIS frontend

A386838 Minimum number of unit squares that a straight line drawn from (0,0) to (x,y) passes through on the square lattice where x^2 + y^2 = A001481(n). If A001481(n) can be written as a sum of two squares in two or more ways, x and y are chosen such that a(n) is the least value.

0, 0, 1, 0, 2, 2, 0, 3, 4, 0, 4, 3, 4, 0, 5, 6, 4, 7, 0, 6, 6, 8, 6, 0, 5, 8, 8, 9, 10, 0, 8, 8, 6, 10, 11, 8, 0, 9, 10, 12, 9, 12, 7, 0, 10, 10, 13, 12, 14, 12, 12, 0, 11, 10, 8, 13, 14, 14, 0, 12, 15, 12, 16, 12, 16, 12, 9, 16, 0, 13, 14, 15, 12, 18, 16, 18, 17, 0, 14

Offset: 1

Miles Englezou, Aug 05 2025

nonn

a(n) is the minimal area of the graph formed under the requirement that the straight line (0,0) to (x,y) passes through an enclosed space on the square lattice, with the graph drawn using only vertical and horizontal edges.

Every nonnegative integer n appears in this sequence. Proof: Since 2*n^2 = n^2 + n^2 then by the first formula in the formula section n + n - gcd(n,n) = n. To prove that a(m) = n when A001481(m) = 2*n^2, we have to prove that x = n and y = n is the choice such that a(m) is minimal. Let r and s be two other numbers such that 2*n^2 = r^2 + s^2. Let r > n: consequently s < n, 1 <= gcd(r,s) <= s, and s - gcd(r,s) >= 0. If r + s - gcd(r,s) <= n, then s - gcd(r,s) < 0. But s - gcd(r,s) >= 0. Therefore r + s - gcd(r,s) >= r > n, and a(m) = n.

			a(4) = 0 since A001481(4) = 4 and 4 = 2^2 + 0^2. A straight line from (0,0) to (2,0) stays on the x axis and therefore passes through no unit squares.
a(5) = 2 since A001481(5) = 5 and 5 = 2^2 + 1^2. A straight line from (0,0) to (2,1) passes through two unit squares. It looks like this:
      _ _ (2,1)
     |_|_|
(0,0)
a(6) = 2 since A001481(6) = 8 and 8 = 2^2 + 2^2. A straight line from (0,0) to (2,2) passes through two unit squares. It looks like this:
        _ (2,2)
      _|_|
     |_|
(0,0)
a(16) = 6 since A001481(16) = 29 and 29 = 5^2 + 2^2. A straight line from (0,0) to (5,2) passes through six unit squares. It looks like this:
          _ _ _ (5,2)
      _ _|_|_|_|
     |_|_|_|
(0,0)
a(14) = 0 since A001481(14) = 25 and 25 = 5^2 + 0^2 = 4^2 + 3^2. x + y - gcd(x,y) is minimal for x = 5 and y = 0 and is equal to zero, therefore a(14) = 0.

Miles Englezou, Table of n, a(n) for n = 1..10000

Cf. A001481, A328803.

a(n) = my(f, S, T = []); (f(n) = my(P = []); for(x=0, sqrtint(n), my(y2 = n - x^2); if(issquare(y2), my(y = sqrtint(y2)); if(x <= y, P = concat(P, [[x, y]])))); return(P)); S = f(n); if(#S == 0, return(0), for(k = 1, #S, T = concat(T, S[k][1] + S[k][2] - gcd(S[k][1], S[k][2]))); return(vecmin(T))) \\ function will also return 0 for n not in A001481 so any loop of a(n) must filter n

For x and y defined in the title, a(n) = x + y - gcd(x,y).
a(n) = 0 when A001481(n) is square.
a(n) = k when A001481(n) = 2*k^2, for k >= 0.
a(n) = A328803(n) - gcd(x,y) for A001481(n) = x^2 + y^2 with exactly one decomposition into a sum of two squares.

A328801 Least k such that there exists a square of side length sqrt(A001481(n)) with vertices in a k X k square array of points.

Original entry on oeis.org

2, 3, 3, 4, 5, 4, 5, 6, 5, 6, 7, 7, 6, 7, 8, 9, 9, 7, 8, 9, 10, 10, 8, 9, 11, 10, 11, 12, 9, 10, 11, 13, 12, 13, 13, 10, 11, 12, 14, 13, 14, 15, 11, 12, 13, 15, 14, 16, 15, 16, 12, 13, 14, 17, 15, 17, 16, 13, 14, 17, 15, 18, 16, 18, 17, 19, 19, 14, 15, 16, 17

Offset: 2

Peter Kagey, Oct 27 2019

			For n = 8, there is a square with side length sqrt(A001481(8)) = sqrt(10) and vertices in the a(8) X a(8) = 5 X 5 square array of points.
o o o * o
* o o o o
o o o o o
o o o o *
o * o o o
However, there is no square with side length sqrt(10) and vertices in a smaller square array points.

Peter Kagey, Table of n, a(n) for n = 2..10000

Cf. A001481, A108279.

A328793 is the analog for a triangular grid.

a(n) = A328803(n) + 1.

A328804 The maximum value of j + k where j and k are positive integers with j^2 + k^2 = A001481(n).

Original entry on oeis.org

0, 1, 2, 2, 3, 4, 3, 4, 5, 4, 5, 6, 6, 7, 6, 7, 8, 8, 6, 7, 8, 9, 9, 7, 10, 10, 9, 10, 11, 8, 11, 10, 12, 11, 12, 12, 9, 10, 13, 13, 12, 13, 14, 14, 11, 12, 14, 13, 15, 14, 15, 11, 12, 15, 16, 16, 16, 15, 12, 17, 16, 14, 17, 15, 17, 16, 18, 18, 17, 18, 15, 16

Offset: 1

Peter Kagey, Oct 27 2019

nonn

			For n = 14, A001481(14) = 25 = 0^2 + 5^2 = 3^2 + 4^2, so a(14) = max{0+5, 3+4} = 7.

Peter Kagey, Table of n, a(n) for n = 1..10000

Cf. A000161, A001481, A328803.

from itertools import count, islice
from sympy.solvers.diophantine.diophantine import diop_DN
from sympy import factorint
def A328804_gen(): # generator of terms
    return map(lambda n: max((a+b for a, b in diop_DN(-1,n))), filter(lambda n:(lambda m:all(d&3!=3 or m[d]&1==0 for d in m))(factorint(n)), count(0)))
A328804_list = list(islice(A328804_gen(),30)) # Chai Wah Wu, Sep 09 2022

cp's OEIS Frontend

A386838 Minimum number of unit squares that a straight line drawn from (0,0) to (x,y) passes through on the square lattice where x^2 + y^2 = A001481(n). If A001481(n) can be written as a sum of two squares in two or more ways, x and y are chosen such that a(n) is the least value.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A328801 Least k such that there exists a square of side length sqrt(A001481(n)) with vertices in a k X k square array of points.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A328804 The maximum value of j + k where j and k are positive integers with j^2 + k^2 = A001481(n).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Python