mobius.py

"""
The Mobius function μ(n) is an important function in number theory.

Definition:
- μ(n) = 1 if n is a square-free positive integer with an even number of prime factors.
- μ(n) = -1 if n is a square-free positive integer with an odd number of prime factors.
- μ(n) = 0 if n has a squared prime factor (i.e., n is not square-free).

A number is square-free if it is not divisible by any perfect square other than 1.

Examples:
- μ(1) = 1 (by definition, 1 has zero prime factors, which is even)
- μ(2) = -1 (2 has one prime factor: 2, which is odd)
- μ(6) = 1 (6 = 2 × 3, two distinct prime factors, which is even)
- μ(12) = 0 (12 = 2² × 3, has a squared factor 2²)
- μ(30) = -1 (30 = 2 × 3 × 5, three distinct prime factors, which is odd)

Time complexity: O(sqrt(n))
Space complexity: O(1)

Programmed by [Your Name]
* 2026-01-24 Initial implementation
"""


def mobius(n):
    """
    Calculate the Mobius function μ(n) for a given positive integer n.
    
    Args:
        n (int): A positive integer
        
    Returns:
        int: The Mobius function value (1, -1, or 0)
        
    Raises:
        ValueError: If n is not a positive integer
        
    Examples:
        >>> mobius(1)
        1
        >>> mobius(2)
        -1
        >>> mobius(6)
        1
        >>> mobius(12)
        0
        >>> mobius(30)
        -1
    """
    if not isinstance(n, int) or n < 1:
        raise ValueError("n must be a positive integer")
    
    # Special case: μ(1) = 1
    if n == 1:
        return 1
    
    prime_factor_count = 0
    
    # Check for factor 2
    if n % 2 == 0:
        prime_factor_count += 1
        n //= 2
        # If 2 appears more than once, n is not square-free
        if n % 2 == 0:
            return 0
    
    # Check for odd factors from 3 onwards
    i = 3
    while i * i <= n:
        if n % i == 0:
            prime_factor_count += 1
            n //= i
            # If this prime appears more than once, n is not square-free
            if n % i == 0:
                return 0
        i += 2
    
    # If n > 1, then it's a prime factor
    if n > 1:
        prime_factor_count += 1
    
    # Return 1 if even number of prime factors, -1 if odd
    return 1 if prime_factor_count % 2 == 0 else -1


if __name__ == "__main__":
    # Test examples
    test_cases = [1, 2, 3, 6, 12, 30, 42, 105, 210]
    
    print("Mobius Function Examples:")
    print("-" * 40)
    for num in test_cases:
        result = mobius(num)
        print(f"μ({num:3d}) = {result:2d}")