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

Author

Miles Englezou, Aug 05 2025

Keywords

• nonn

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.

Examples

			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.
		

Links

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

Crossrefs

Cf. A001481, A328803.

Programs

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

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.