Lattice Points of the q-Ball in Time O(N2/(3q)log²N): Fast Algorithms for A175363 and A175364

The sequences A175363 = C_3(n) and A175364 = C_3(n^2), where C_q(N) is the number of integer pairs (x,y) satisfying |x|^q + |y|^q <= N, are traditionally defined by sums of Theta(N^(1/q)) integer roots. We compute C_q(N) in O(N^(2/(3q)) * log^2 N) operations on O(log N)-bit integers: O(n^(2/9) * log^2 n) for A175363 and O(n^(4/9) * log^2 n) for A175364, compared to the classical Theta(n^(1/3)) and Theta(n^(2/3)) direct methods. By symmetry, the count reduces to the lattice points under a concave arc. The upper hull of these points has O(N^(2/(3q))) vertices by Andrews' theorem, the column sums along a hull edge are given in closed form, and the next edge is the steepest admissible primitive vector. This vector is found by a Stern-Brocot descent whose runs are located by exponential search with exact integer predicates, including an exact test for the sign of the derivative. All claims are proved. On one core in Python 3.12, A175363(10^24 + 12345) takes 56.68 s with the direct method and 1.399 s with the new method (40.5 times faster); the method computes A175363(10^33 + 12345) in 212.1 s. A175364(10^12 + 12345) takes 53.06 s directly and 1.548 s with the method (34.3 times faster), and A175364(10^16 + 12345) (where N is approximately 10^32) takes 130.2 s. For q = 4 and N = 10^28 + 12345 the times are 4.765 s and 0.251 s (19.0 times), and N = 10^36 + 12345 takes 7.616 s. All values agree with the direct method wherever both were run.