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

Comments

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.

Links

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

Formula

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.

Example

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.

Prog

(PARI) 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

Crossrefs

Cf. A001481, A328803.

Sequence in context: A207383 A191362 A137422 * A139139 A077872 A300453

Adjacent sequences: A386835 A386836 A386837 * A386839 A386840 A386841

Keyword

nonn

Author

Miles Englezou, Aug 05 2025

Status

approved