Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
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

2 Answers 2

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.$$

share|improve this answer
    
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

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$.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.