Python Coding Test Course, Implementing Euler's Phi Function

Hello! Today we will learn how to implement Euler’s Totient Function in Python. In this article, we will explore the definition and properties of the Euler’s Totient Function and explain how to implement it efficiently step by step.

1. What is Euler’s Totient Function?

The Euler’s Totient Function φ(n) is a function that represents the number of integers between 1 and n that are coprime to n. In other words, φ(n) means the number of integers that do not share any divisors with n. For example:

φ(1) = 1 (1 is coprime only with itself)
φ(2) = 1 (only 1 is coprime with 2)
φ(3) = 2 (1 and 2 are coprime with 3)
φ(4) = 2 (1 and 3 are coprime with 4)
φ(5) = 4 (1, 2, 3, and 4 are coprime with 5)

2. Properties of Euler’s Totient Function

Euler’s Totient Function has several important properties:

If n is a prime p, then φ(p) = p – 1
If n is a prime power p^k, then φ(p^k) = p^k(1 – (1/p))
If n is the product of two integers a and b, then φ(ab) = φ(a) * φ(b) * (1 – (1/gcd(a,b)))

2.1 Example

If you want to find the value of Euler’s Totient Function φ(n) for a given number n, you need to find the prime factors of n. For example, if n = 12 is given, the prime factors are 2 and 3, and you can calculate φ(12) using the φ values of these two primes.

3. How to Implement Euler’s Totient Function

Now, let’s learn how to implement φ(n) efficiently. The basic approach is to check each number and count the number of coprime integers, but this is inefficient and needs improvement.

3.1 Sieve of Eratosthenes Method

One efficient way to implement Euler’s Totient Function is to use the concept of the Sieve of Eratosthenes. Here is the logic to calculate φ(n):

def euler_totient(n):
    # Initialize a pair array from 1 to n
    phi = list(range(n + 1))
    
    # Use the Sieve of Eratosthenes to calculate the Euler's Totient Function values
    for i in range(2, n + 1):
        if phi[i] == i:  # If i is prime
            for j in range(i, n + 1, i):
                phi[j] *= (i - 1)
                phi[j] //= i
    return phi

3.2 Code Analysis

The above code works as follows:

Initialize the φ array from 1 to n. That is, φ[i] is initially set to i.
For each number i from 2 to n, check if i is prime. If so, update the φ array.
Set j to the multiples of i to update the φ value of that multiple.

4. Time Complexity Analysis

The time complexity of this algorithm is O(n log log n). This is similar to the Sieve of Eratosthenes, allowing for very efficient computation of φ(n). This algorithm can be used for small n, but it also maintains sufficiently fast performance for larger n.

5. Example

Here’s an example of using this algorithm to calculate and output the Euler’s Totient values up to n = 10:

if __name__ == "__main__":
    n = 10
    result = euler_totient(n)
    print(f"Euler's Totient values up to n = {n}: {result[1:]}")

5.1 Sample Output

Euler's Totient values up to n = 10: [1, 1, 2, 2, 4, 4, 6, 6, 8, 4]

6. Conclusion

In this article, we explored the definition, properties, and implementation method of Euler’s Totient Function. It’s impressive that by utilizing the Sieve of Eratosthenes instead of classical methods, we can efficiently find φ(n). I hope you will continue to learn about other algorithms and data structures to solve more complex problems.

7. References

Thank you for joining us! We will see you next time with more informative algorithm lectures.

Python Coding Test Course, Implementing Euler’s Phi Function