# How to calculate Euler Totient Function up to a limit?

Totient(n) gives the amount of numbers beneath n that are coprime to n. Is it possible to concisely find Totient(n) where all numbers are beneath a limit x so that TotientLimit(n,x) would give the amount of numbers coprime to n up to x? For example:

TotientLimit(10,6) 1:Coprime to 10 2:Not coprime 3:Coprime to 10 4:Not coprime 5:Not coprime 6-9:above or equal to limit, excluded.

So TotientLimit(10,6) is equal to 2 because there are 2 numbers coprime to 10 that are lower than 6.

Is there a function for that? Thanks

-
There are algorithms, but I know of nothing significantly faster than testing each candidate against n up to x. Unfortunately the multiplicative property does not hold in a nice way for one to break down the problem and analyze it. If you do find a nice estimate, let me know; it will help me on a current project. Gerhard "Ask Me About Jacobsthal's Function" Paseman, 2012.02.16 – Gerhard Paseman Feb 17 '12 at 5:34
Of course, if you know phi(n) and just need a rough estimate, a linear approximation works well for x much larger than n. For x less than n, that is interesting territory. Gerhard "Ask Me About System Design" Paseman, 2012.02.16 – Gerhard Paseman Feb 17 '12 at 5:37

Just a simple counting argument. It is $x\phi (n)/n +O(1)$. There is an error term $O(1)$ coming from the case when $x$ is not a multiple of $n$.

-
Indeed. Have you any significant information on the behaviour of the error term? (I'm hoping to improve a bound related to mathoverflow.net/questions/37679/… .) Gerhard "Ask Me About System Design" Paseman, 2012.02.16 – Gerhard Paseman Feb 17 '12 at 6:06

It is about the same as finding $\phi(n)$, easy if you know the prime factorization. Let $x$ be a positive real number and $y$ the largest integer strictly less than $x$. If $n=p^aq^br^c$ then the count is $(1-\frac1p)(1-\frac1q)(1-\frac1r)y$ except that after you multiply out, you take the integer part of each term. For your example of $n=10$ it is $y-\lfloor\frac y2\rfloor-\lfloor\frac y5\rfloor+\lfloor\frac y{10}\rfloor$. In case $x=6$ and $y=5$, $$5-\lfloor\frac 52\rfloor-\lfloor\frac 55\rfloor+\lfloor\frac 5{10}\rfloor=5-2-1+0=2.$$

-
This is false. For instance $1$ is prime to $n$ even if $\phi(n)/n$ is much lower than $1$, so rounding down is insufficient. – Will Sawin Feb 17 '12 at 7:14
It is false if x is a real and the answer is non integral. Are there integers x and n for which the evaluation does not succeed, Will? Gerhard "Ask Me About System Design" Paseman, 2012.02.17 – Gerhard Paseman Feb 17 '12 at 18:28
I was assuming that $x$ is a non-negative integer and finding the count up to and including $x$. I'll fix that but then I don't see the issue. For $y=1$ and $n=10$ $1-0-0+0=1.$ – Aaron Meyerowitz Feb 17 '12 at 18:33
Even if you know the prime factorization, one needs to take care especially in the case that n has a not small (> 9) number of distinct prime factors. However, this is (contrary to my gaffe above) somewhat faster than certain forms of testing I mentioned. Gerhard "Ask Me About Slow Methods" Paseman, 2012.02.17 – Gerhard Paseman Feb 17 '12 at 18:33
Interesting question on the error in not doing any rounding. If there are $d$ factors then it is certainly less than $2^d$ in either direction. For absolute error it suffices to check $x$ up to $n$. I doubt that the error can exceed $d$ in either direction. – Aaron Meyerowitz Feb 17 '12 at 19:48