Euler's function, Euler's sieve

Euler's Totient Function | Euler's Sieve#

Overview#

The Euler's totient function $\phi_i$ represents the number of integers less than or equal to $i$ that are coprime with $i$. It is a non-completely multiplicative function.

Euler's sieve is a type of linear sieve. It has a time complexity of $O(UpperLimit)$ and can be used to linearly calculate multiplicative functions.

Principle#

Euler's Sieve#

Euler's sieve takes the current prime number $i$ and multiplies it with the previous prime numbers $Primes_1 \sim Primes_{cnt}$ to sieve out their multiples. Euler's sieve ensures that every composite number is sieved out by its smallest prime factor.

The core code is if(i % Primes[j] == 0) break;, which guarantees the linear time complexity of Euler's sieve.

Proof: When $i\mod Primes_j == 0$, there are two possibilities:

When $i$ is a prime number. This means that $i$ has been captured ($Primes_j == i$) and $i^2$ has been sieved out. Obviously, for a prime number $i$, the smallest prime factor of $i^2$ is $i$.
When $i$ is a composite number. This means that $Primes_j$ is the smallest prime factor of $i$. Then the prime factors of $i * Primes_j$ are $Primes_j$ and the prime factors of $i$. Obviously, $Primes_j < i$, so $Primes_j$ is the smallest prime factor of $i * Primes_j$ so far. However, the $Primes$ array is monotonically increasing, and the smallest prime factor of each subsequent $iPrimes_{j'}$ is no longer $Primes_{j'}$, but the previous $Primes_j$ (because $i \mod Primes_j == 0$, then $Primes_j$ is the smallest prime factor of $i$, and also the smallest prime factor of $iPrimes_j$), so it cannot be guaranteed that every composite number is sieved out by its smallest prime factor. Therefore, Break.

In addition, every composite number up to $UpperLimit$ will be sieved out. Obviously, every number up to $UpperLimit$ has a prime factor up to $UpperLimit$.

Euler's Totient Function#

The general expression for $\phi_i$: $\phi_i = i * \prod_{j=1}^{cnt_i}(1-\frac{1}{p_j} )$, using the principle of inclusion-exclusion:

Decompose $i$ into prime factors, $i=\prod_{j=1}^{cnt}p_i^{e_i}$. $p$ is a prime factor of $i$. Then the number of multiples of $p_j$ less than $i$ that are not coprime with $i$ is $\frac{n}{p_1} + \frac{n}{p_2} + ... \frac{n}{p_j}$. Subtract these numbers from $n$. Of course, there will be some overlapping cases, such as $\frac{n}{p_1p_2}$, so add them back. Using the principle of inclusion-exclusion, we get $\phi_i = i * \prod_{j=1}^{cnt}(1-\frac{1}{p_i} )$.

The Euler's totient function has some special properties. Consider $\phi_i$:

Obviously, when $i$ is a prime number, $\phi_i=i-1$.
When $i$ can be written in the form of $p^k$, where $p$ is a prime number, then $\phi_i = p^k - p^{k-1}$.

? Proof: Consider $p^k$, the numbers in $\phi_{p^k}$ must satisfy a requirement, that is, they do not contain the factor $p$. It is not easy to calculate directly, so let's calculate it backwards. The numbers in $p^k$ that contain the factor $p$ are $ p,2p,3p,4p, \ldots,pp,(p+1)*p,\ldots,(p^{k-1}-1)*p,p^{k-1}*p$, a total of $p^{k-1}$.
When $i$ can be written in the form of $mn$, where $m$ and $n$ are coprime, then $\phi_i = \phi_{m}\phi_{n}$. This is the partial multiplicative property of the Euler's function.

? Proof: $m$ and $n$ are coprime, which means that they do not have the same prime factors. So their unique factorizations are completely different. That is, $m = \prod_{j=1}^{cnt_m}p_j^{e_j}$, $n=\prod_{j=1}^{cnt_n}p_j^{e_j}$. Then $\phi_m = m*\prod_{j=1}^{cnt_m}(1-\frac{1}{p_j})$, $\phi_n = n*\prod_{j=1}^{cnt_n}(1-\frac{1}{p_j})$. Because the unique factorizations are completely different, it is obvious that $\phi_{mn} = \phi_m\phi_n$.

Based on the definition and properties of $\phi$, consider the recursive method to calculate $\phi_i$:

When $i$ is a prime number, $\phi_i=i-1$.
When $i$ is not a prime number:

Let $i = x * p$, where $p$ is a prime number.
- When $p$ is a factor of $x$, then $\phi_i=p*\phi_x$.
  
  ? Proof: This proof is a bit more complicated. Let $a$ be an element in the $\phi_x$ set. First, let's state a fact that is useful for the proof:
  
  ? · When $a$ is coprime with $x$, it is definitely coprime with $x*p$ ($p$ is the prime number mentioned earlier).
  
  ? Next, we need to prove that when $a$ is coprime with $x$, $a+x$ is also coprime with $x$. Obviously, $a,x$ are coprime $\Leftrightarrow gcd(a,x) =1$. So what we want to prove is $gcd(a+x,x)=1$. We can use proof by contradiction: (of course, this is just a variant of the Euclidean algorithm)
  
  ? Assume $gcd(a+x,x)=b$ (where $b \neq 1$). Let $a+x = k_1b,x=k_2b$. Then $a=(k_1-k_2)*b$. Obviously, $gcd((k_1-k_2)b,k_2b) = b$, so $gcd(a,x)>=b$.
  
  ? What is the use of proving this? We want to prove $\phi_i=p*\phi_x$. With the above conclusion, we know that each element $a$ in the $\phi_x$ set is coprime with $i$. Because $i=xp$, all numbers within $x$ that are $a,a+x,a+2x,\ldots,a+(p-1)x$ are coprime with $i$. There are a total of $\phi_x$ such $a$. Each $a$ can be extended to $p$ numbers coprime with $i$. Therefore, $\phi_i=p\phi_x$ is proven.
- When $p$ is not a factor of $x$, then $\phi_i=(p-1)*\phi_x$.
  
  ? Proof: Obviously, $p$ is coprime with $x$, so $\phi_i = \phi_x * \phi_p$, and it is known that $\phi_p = p-1$, so $\phi_i=(p-1)*\phi_x$ is obvious.

Implementation#

#define rep(x,y,z) for(int x=y,I=z;x<=z;++x)
inline void Euler_Sieve(){
    rep(i,2,lim){
        if(!isprime[i]) primes[++prime]=i,phi[i]=i-1;
        for(int j=1;i*primes[j]<=lim;j++){
            phi[i*primes[j]]=phi[i]*(primes[j]-1),isprime[i*primes[j]]=true;
            if(i%primes[j]==0) { phi[i*primes[j]]=phi[i]*primes[j]; break; }
        }
    }
}