Inverse of $f(x) = \sum_{i=0}^x \lfloor 2 \pi i \rfloor$

Question

Is there a closed expression that could be used to compute the inverse of $f(x) = \sum_{i=0}^x \lfloor 2 \pi i \rfloor$? Or at least an algorithm with low computational complexity for high x?

Answer 1

If $y$ is in the range of $f$, then $$y=f\left(\left\lfloor\frac{1+\sqrt{1+\frac{4y}{\pi}}}{2}\right\rfloor\right).$$

To show this, we will use two crude estimates from above and below. If $n$ is irrational, then $n-1\lt\lfloor n\rfloor\lt n$. We will further loosen it to write $2k\pi-2\pi<2k\pi-1\lt \lfloor2k\pi\rfloor<2k\pi$.

If $y\in f(\mathbb N)$, then $f(w)=y$ for some (unique, as $f$ is strictly crescent) $w\in\mathbb N$. Using the first estimate $2k\pi-2\pi<\lfloor2k\pi\rfloor$, $$f(w)>2\pi\sum_1^w k-1=\pi w(w-1).$$

Similarly, the second estimate $\lfloor 2k\pi\rfloor <2k\pi$ outputs $f(w)<2\pi\sum_1^wk=\pi w(w+1).$ Completing squares in the new estimates shows us that $$\frac 12\left(\sqrt{1+\frac{4y}{\pi}}-1\right)<w<\frac 12\left(\sqrt{1+\frac{4y}{\pi}}+1\right)$$ and therefore $$w=\left\lfloor\frac{1+\sqrt{1+\frac{4y}{\pi}}}{2}\right\rfloor.$$