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.

%I A386838 #31 Aug 14 2025 00:51:25
%S A386838 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,
%T A386838 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,
%U A386838 12,15,12,16,12,16,12,9,16,0,13,14,15,12,18,16,18,17,0,14
%N 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.
%C A386838 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.
%C A386838 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.
%H A386838 Miles Englezou, <a href="/A386838/b386838.txt">Table of n, a(n) for n = 1..10000</a>
%F A386838 For x and y defined in the title, a(n) = x + y - gcd(x,y).
%F A386838 a(n) = 0 when A001481(n) is square.
%F A386838 a(n) = k when A001481(n) = 2*k^2, for k >= 0.
%F A386838 a(n) = A328803(n) - gcd(x,y) for A001481(n) = x^2 + y^2 with exactly one decomposition into a sum of two squares.
%e A386838 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.
%e A386838 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:
%e A386838       _ _ (2,1)
%e A386838      |_|_|
%e A386838 (0,0)
%e A386838 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:
%e A386838         _ (2,2)
%e A386838       _|_|
%e A386838      |_|
%e A386838 (0,0)
%e A386838 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:
%e A386838           _ _ _ (5,2)
%e A386838       _ _|_|_|_|
%e A386838      |_|_|_|
%e A386838 (0,0)
%e A386838 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.
%o A386838 (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
%Y A386838 Cf. A001481, A328803.
%K A386838 nonn
%O A386838 1,5
%A A386838 _Miles Englezou_, Aug 05 2025