A visible point is a point $(a, b)\in \mathbb{Z}^2,$ with $gcd(a,b)=1$. It is well-known that the number $V(N)$ of visible points with $0<a, b \leq N$ is asymptotic to $N^2/\zeta(2)$, but suppose I really want to compute it exactly. Can it be done in polynomial time (polynomial in $\log N,$ that is)? 


If one wants to be more modest, can it be computed in time sublinear in $N?$ Or even linear in $N?$ It *can* be computed in time $O(N^{1+\epsilon})$, for any $\epsilon>0$, since we can compute the totient function in sub-polynomial time.



Complexity of computing the number of visible points
There is an algorithm for computing $F(N) = \# \{ (a,b) : 1 \leq a, b \leq N, \gcd(a,b) = 1 \}$ in time $O(N^{5/6 + \epsilon})$. This relies on the algorithm of Deleglise and Rivat (see [their paper here](https://projecteuclid.org/euclid.em/1047565447)) that computes $M(x) = \sum\_{n \leq x} \mu(n)$ in time $O(x^{2/3} (\log \log x)^{1/3})$.


The idea is to use
$$
 F(N) = \sum\_{a=1}^{N} \sum\_{b=1}^{N} \sum\_{d | \gcd(a,b)} \mu(d) = \sum\_{d=1}^{N} \mu(d) \left\lfloor \frac{N}{d}\right\rfloor^{2}.
$$
Now, break this sum up into the terms with $1 \leq d \leq N^{\alpha}$ and the terms with $N^{\alpha} < d \leq N$. The first term
$$
 \sum\_{d=1}^{N^{\alpha}} \mu(d) \left\lfloor \frac{N}{d} \right\rfloor^{2}
$$
can be computed easily in time $O(N^{\alpha + \epsilon})$, since all $\mu(d)$ for $d \leq N^{\alpha}$ can be computed in time $O(N^{\alpha} \log \log(N))$ (see [this preprint](https://arxiv.org/pdf/1610.08551v1.pdf)). For the range $N^{\alpha} < d \leq N$, let $k = \lfloor N/d \rfloor$. We get the sum
$$
 \sum\_{k=1}^{\lfloor N^{1-\alpha} \rfloor} k^{2} \sum\_{\substack{e \\ \lfloor N/e \rfloor = k}} \mu(e) = \sum\_{k=1}^{\lfloor N^{1-\alpha} \rfloor} k^{2} (M(b\_{k}) - M(a\_{k})).
$$
Here $a\_{k}$ and $b\_{k}$ are the smallest and largest positive integers $N$ for which $\lfloor N/e \rfloor = k$, respectively. There are $O(N^{1-\alpha})$ terms in the sum above, and each can be computed in time $O(N^{2/3+\epsilon})$. The total running time $O(N^{\alpha + \epsilon} + N^{5/3 - \alpha + \epsilon})$ is minimized when $\alpha = 5/6$ and gives $O(N^{5/6 + \epsilon})$.


