Exact Evaluation of the Summatory Divisor-Sum Function and Related Quotient Sums in Time Near n1/3: Stern--Brocot Hull Walks with Floor-Sum Moments

Let sigma(k) be the sum of divisors of k and S(n) be the summatory divisor-sum function, defined as the sum of k * floor(n/k) for k from 1 to n (OEIS A024916). Standard algorithms evaluate isolated values of S(n) using the Dirichlet hyperbola method in O(sqrt(n)) operations. This paper extends the Stern-Brocot walk along the lower convex hull of lattice points above the hyperbola uv = n to higher moments. Along every hull edge, the sums of q, yq, and q^2 (where q = floor(n/y)) are obtained in closed form from three floor sums of a primitive step, computed once per edge direction via a Euclid-type recursion in O(log n) steps. This simultaneously returns D(n) and S(n) in O(n^(1/3)) operations, yielding the first sublinear algorithm for this sequence. It also computes the sum of remainders (OEIS A004125) and the sum of squared quotients. The Python 3.12 implementation is verified against brute force and baseline evaluations up to n = 10^18. The exact values of S(10^k) for k <= 18 are provided.