0

Are there any efficient functions to evaluate Euler's totient function $\varphi(x)$ over a explicit range $(a,b)$ where $a,b\in\mathbb{R},0\leqslant a\leqslant b$ (and potentially greater than $x$)? i.e functions that return the count of values relatively prime to $x$ over an arbitrary, positive interval.

Ideally interested in any methods that aren't limited in range by memory constraints or that take forever to compute $\geqslant\mathcal{O}(x!)$.

Tuvasbien
  • 8,907
Ryan Pierce Williams
  • 533
  • 4
  • 12
  • How do I evaluate the above to find the count over a specific range (a, b)? – Ryan Pierce Williams Jan 08 '23 at 01:24
  • @Tuvasbien Like I described up above, I want the count of integers that are coprime to n over an arbitrary range (a,b) - including n < a < b. Euler's Totient function gives you the count <= x. As an explicit example: if I wanted to know the count of all the coprimes of 5 over the range (29, 32) the answer would be 3. – Ryan Pierce Williams Jan 08 '23 at 01:34
  • 2
    Each interval of length $x$ contains $\varphi(x)$ numbers coprime to $x$. So if you already have $\varphi(x)$ and count the coprimes in the remaining interval of length $<x$, you are done. That's $O(x)$ – Hagen von Eitzen Jan 08 '23 at 01:41
  • 1
    @HagenvonEitzen That's easy if x happens to be prime - but what of composites? – Ryan Pierce Williams Jan 08 '23 at 01:57

0 Answers0