Coprime Lattice Points in a Disc: A Möbius Formula and an O(sqrt M) Algorithm for the Sequences A304651, A175341 and A124254

Let P(M) be the number of pairs (x, y) in Z^2 with gcd(x, y) = 1 and x^2 + y^2 <= M. This paper addresses three related OEIS sequences: A304651 (which is P(n)), A175341 (which is P(n^2)), and A124254 (which counts coprime pairs 1 <= x <= y with x^2 + y^2 < n^2). The current OEIS implementations rely on O(M) or O(n^2) recurrences, or brute-force enumeration. We prove the exact Möbius inversion formula P(M) = 4 * sum_{k <= sqrt(M)} mu(k) * G(floor(M / k^2)), where G(q) counts the lattice points (x, y) with x >= 1, y >= 0, and x^2 + y^2 <= q. We establish the explicit identities A175341(n) = P(n^2) and A124254(n) = P(n^2 - 1) / 8 for n >= 2, proving the combinatorial conjecture regarding the forest-and-trees problem in A124254. Furthermore, we present an algorithm that evaluates P(M) in O(sqrt(M) * log M) vectorized operations using O(sqrt(M)) memory. The approach utilizes a segmented Möbius sieve, prefix sums of the Möbius function, a small-argument table for G(q), and a fast sublinear convex hull walk for large arguments. The formula has been numerically verified against all published terms and independent GCD counts up to M = 10^8. In Python 3.12, computing P(10^8) = 190,985,984 takes just 0.0025 s, P(10^14) takes 1.5 s, and A175341(3 * 10^7) = 1,718,873,385,377,192 is computed in 4.5 s.