Exact Evaluation of Sum_k floor(n/k^p) in O(n^(1/(p+2)) log n) Operations: A Convex Hull Walk for the Sequences A013936 and A013937

For an integer p >= 2, let S_p(n) be the summatory function of floor(n/k^p) over k >= 1, which counts the number of integer pairs (j,k) with j * k^p <= n. The case p=2 corresponds to the OEIS sequence A013936, and p=3 corresponds to A013937. Traditional formulas listed in the OEIS require O(n^(1/p)) operations, and classical Dirichlet hyperbola-type grouping partitions the domain into O(n^(1/(p+1))) terms. We prove an exact structural decomposition identity that evaluates S_p(n) in O(n^(1/(p+2)) log n) arithmetic operations on integers of O(log n) bits, establishing the first method to break the O(n^(1/(p+1))) hyperbola barrier. The tail of the sum is represented as a lattice point count of a convex region bounded by the curve y = (n+1)/x^p in a bounded box. We implement a deterministic lower convex hull walk driven by exact integer predicates, counting the encapsulated lattice points via Pick's theorem and bounding the total number of hull vertices via Andrews' theorem on convex lattice polygons. The framework is verified against direct enumeration and baseline grouping methods up to n=10^28. In Python 3.12, the sublinear algorithm evaluates the exact value of S_2(10^26) in 109 s (improving upon the 190 s grouping baseline) and S_3(10^30) in 14 s (against 104 s for grouping). The full source code and cross-verification logs are provided.