The Gauss Circle Sequences A000328, A000603 and A057655: Exact Values by a Provably Correct Stern--Brocot Hull Walk

Let N(M) be the number of lattice points inside the closed disc x^2+y^2 <= M (OEIS A057655). The classic sequences A000328 and A000603 represent N(n^2) and the number of non-negative solutions respectively, traditionally computed via direct column summation in O(sqrt(M)) steps. We present a modified Stern-Brocot hull walk algorithm that evaluates N(M) exactly by following the upper convex hull of the lattice points of the disc. Unlike traditional implementations that carry a continuous stack of ancestors, our descent is completely restarted at every hull vertex from the basis vectors (1,1) and (1,0). Every run of the descent is computed in closed form: the longest run of one kind is extracted as the integer root of a quadratic norm form, and the shortest run of the other kind is obtained as the minimum of a convex quadratic. We prove that the sum of the abscissas of the two current Stern-Brocot vectors at least doubles in every round of the descent, bounding the number of rounds per vertex by log_2(2x_0) + 2. Incorporating Andrews' theorem on the number of vertices, we provide the first complete proof that the entire evaluation terminates in O(M^(1/3) log^2 M) exact arithmetic operations. The framework is verified numerically against independent stack-based baselines up to M=10^18. In Python 3.12, the classical Gauss constant A000328(10^9) is computed in 7.8 s, and A000328(10^10) is returned in 49 s. The full source code is publicly available.