0
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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 $\endgroup$ Feb 17, 2012 at 5:34
  • $\begingroup$ 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 $\endgroup$ Feb 17, 2012 at 5:37

2 Answers 2

1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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 $\endgroup$ Feb 17, 2012 at 6:06
1
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$
    – Will Sawin
    Feb 17, 2012 at 7:14
  • $\begingroup$ 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 $\endgroup$ Feb 17, 2012 at 18:28
  • $\begingroup$ 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.$ $\endgroup$ Feb 17, 2012 at 18:33
  • $\begingroup$ 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 $\endgroup$ Feb 17, 2012 at 18:33
  • $\begingroup$ 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. $\endgroup$ Feb 17, 2012 at 19:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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