Is there a fast way , or a direct function to give the count of numbers less than $x$ and co-prime to $x$ . for example if $x$ = 3 ; then $n = 2$ and if $x$ = 8 ; then $n = 4$.
How many numbers less than $x$ are co-prime to $x$
-
2[Euler's totient function](http://en.wikipedia.org/wiki/Euler's_totient_function) – 2012-08-25
4 Answers
The relevant function is the Euler Totient function and the link contains several ways to compute it.
Yes there is. First of all, you have to prime factorize your $x$, any put it in exponential form. Suppose you have the number $x = 50$. The prime factorization is $5^2 * 2^1$. Now take each number seperately. Take the bases and subtract 1 from all of them. $5-1=4$. $2-1=1$. Now evaluate the each base/exponent combination after subtracting the exponent by 1. $5^{2-1}=5$. $2^{1-1}=1$. Now multiply your answers. $(4)(1)(5)(1) = 20$.
If you want to try out your examples, $3=3^1$. So your answer would be $(3-1)(3^{1-1}) = (2)(1) = 2.$ For your other example, $8=2^3. n=(2-1)(2^{3-1})=(1)(4)=4$.
I guess in general, prime factorize your $x$ to $a_1^{b_1}*a_2^{b_2}* ... * a_n^{b_n}$ and your answer will be $((a_1-1)(a_1^{b_1-1}))*((a_2-1)(a_2^{b_2-1}))*...*(a_n-1)(a_n^{b_n-1})$
You can also use the inclusion-exclusion principle. Example: $1001=7\cdot 11\cdot 13$ has three distinct prime factors, 7, 11, and 13. among numbers from 1 to 1001, there are $143=11\cdot 13$ multiples of 7, $91=7\cdot 13$ multiples of 11, $77=7\cdot 11$ multiples of 13, 13 multiples of 77, 11 multiples of 91, 7 multiples of 143, and 1 multiple of 1001. Therefore $\phi(1001)=1001-(143+91+77)+(13+11+7)-1=720$
Here is a cool proof that I learnt on how to compute the Euler Totient Function $\varphi$ that uses probability theory. On one hand, $\varphi(x)/x$ is the probability that a number selected between $1$ and $x$ is coprime to $x$ while we can alternatively compute the probability as follows:
A number between $1$ and $x$ is coprime to $x$ iff it is coprime to each of its prime factors. Given a prime factor $p$ of $x$, the probability that a number selected between $1$ and $p$ is coprime to $p$ is
$\frac{p-1}{p}.$
Since the events of selecting when a number is coprime to each prime factor are independent, we can multiply the probabilities together to get the total probability being $\prod_{p|x} (p-1)/p$. Equating this with the result before gives you the pretty formula
$\varphi(x) = x\prod_{p|x} \frac{p-1}{p}.$