830: Euler's Totient Function φ(n)

Difficulty: 4 Level: Advanced Count integers in [1, n] coprime to n — and compute it for all values up to N in O(N log log N) with a sieve.

The Problem This Solves

Euler's totient function φ(n) counts how many integers in [1, n] share no common factor with n. For a prime p, φ(p) = p-1 (all integers below p are coprime to it). For n = p^k, φ(n) = p^(k-1)(p-1). For general n, φ is multiplicative: φ(mn) = φ(m)φ(n) when gcd(m,n) = 1. φ(n) appears everywhere in number theory and cryptography. RSA key generation relies on φ(n) where n = p·q — specifically, the fact that a^φ(n) ≡ 1 (mod n) for all a coprime to n (Euler's theorem). Diffie-Hellman and ElGamal work in groups whose order is φ(p) = p-1 for prime p. Primitive roots and discrete logarithms are defined relative to φ. This example implements both a single-value O(√n) computation and an O(N log log N) sieve for computing φ(k) for all k up to N simultaneously.

The Intuition

Single value: factor n into prime powers using trial division. Apply the formula: φ(n) = n · ∏(1 - 1/p) for each distinct prime factor p of n. In integer arithmetic: multiply by (p-1) and divide by p for each prime factor. Sieve: analogous to the Sieve of Eratosthenes. Start with `phi[i] = i`. For each prime p (those with `phi[p] == p` still, unmarked), apply the totient factor to all multiples: `phi[k] = phi[k] / p * (p - 1)`. This is O(N log log N), same as the prime sieve. The sieve approach is essential when you need φ for many values — computing each independently would cost O(N √N).

How It Works in Rust

// Single value: O(√n)
fn euler_totient(mut n: u64) -> u64 {
 let mut result = n;
 let mut p = 2u64;
 while p * p <= n {
     if n % p == 0 {
         // p is a prime factor — apply (1 - 1/p)
         while n % p == 0 { n /= p; }
         result -= result / p; // result = result * (p-1) / p
     }
     p += 1;
 }
 if n > 1 {
     // Remaining factor is prime
     result -= result / n;
 }
 result
}

// Sieve for all values up to limit: O(N log log N)
fn totient_sieve(limit: usize) -> Vec<u64> {
 let mut phi: Vec<u64> = (0..=limit as u64).collect(); // phi[i] = i initially

 for p in 2..=limit {
     if phi[p] as usize == p {
         // p is prime (not yet modified by any smaller prime)
         let mut k = p;
         while k <= limit {
             phi[k] -= phi[k] / p as u64; // phi[k] *= (p-1)/p
             k += p;
         }
     }
 }
 phi
}

The key insight in `euler_totient`: `result -= result / p` implements `result *= (p-1)/p` in integer arithmetic without fractions — divide first, then subtract, to maintain exactness. This works because `p | result` at that point (since `p | n` originally). In the sieve: `phi[p] as usize == p` detects primes exactly like the Sieve of Eratosthenes detects composites — but by checking if the initial value was preserved. For RSA: `phi[n] = (p-1) * (q-1)` directly, but understanding the general formula matters for understanding why RSA works with composite moduli.

What This Unlocks

RSA key generation: compute the private exponent `d ≡ e⁻¹ (mod φ(n))` — requires knowing φ(n) = (p-1)(q-1).
Primitive root finding: a generator of (Z/nZ)* exists iff φ(n) = 1, 2, or φ(p^k) for prime p — totient structure determines group structure.
Euler's theorem applications: for any a coprime to n, a^φ(n) ≡ 1 (mod n) — used to reduce large modular exponentiations.

Key Differences

Concept	OCaml	Rust
Integer division exactness	`/` truncates (same as Rust)	`/` truncates — `result -= result / p` works identically
Prime detection in sieve	`phi.(p) = p` comparison	`phi[p] as usize == p` — same logic, explicit cast
Mutable sieve array	`Array.make (n+1) 0` with loop	`(0..=limit as u64).collect()` initializes with identity values
Trial division loop	`while p p <= n` with `ref n`	`while p p <= n` with `mut n` — shadowing the parameter
u64 vs int	`Int64` or native int (63-bit)	`u64` — explicit width, no overflow surprises

/// Euler's Totient Function φ(n).
///
/// φ(n) = count of k in [1,n] with gcd(k,n) = 1.
/// Formula: φ(n) = n × ∏_{p|n} (1 - 1/p).

/// Single value: O(√n).
fn totient(mut n: u64) -> u64 {
    let mut result = n;
    let mut p = 2u64;
    while p * p <= n {
        if n % p == 0 {
            while n % p == 0 {
                n /= p;
            }
            result -= result / p; // result *= (p-1)/p
        }
        p += 1;
    }
    if n > 1 {
        result -= result / n; // remaining prime factor
    }
    result
}

/// Totient sieve: compute φ(i) for all i in [0, limit]. O(n log log n).
fn totient_sieve(limit: usize) -> Vec<u64> {
    let mut phi: Vec<u64> = (0..=limit as u64).collect();
    for i in 2..=limit {
        if phi[i] == i as u64 {
            // i is prime — update all multiples
            let mut j = i;
            while j <= limit {
                phi[j] -= phi[j] / i as u64;
                j += i;
            }
        }
    }
    phi
}

/// Property: sum of φ(d) over all divisors d of n equals n.
fn sum_divisor_totients(n: u64) -> u64 {
    let phi = totient_sieve(n as usize);
    (1..=n).filter(|&d| n % d == 0).map(|d| phi[d as usize]).sum()
}

fn main() {
    let values = [1u64, 2, 6, 9, 10, 12, 36, 100];
    for &n in &values {
        println!("φ({n}) = {}", totient(n));
    }

    println!("\nTotient sieve [1..12]:");
    let phi = totient_sieve(12);
    for (i, &v) in phi.iter().enumerate().skip(1) {
        println!("  φ({i}) = {v}");
    }

    println!("\nProperty ∑_{{d|n}} φ(d) = n:");
    for n in [6u64, 12, 30] {
        let s = sum_divisor_totients(n);
        println!("  n={n}: sum={s}, match={}", s == n);
    }

    // φ(p) = p-1 for primes
    println!("\nPrime totients:");
    for p in [2u64, 3, 5, 7, 11, 13] {
        println!("  φ({p}) = {} (= p-1 = {})", totient(p), p - 1);
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_totient_known() {
        assert_eq!(totient(1), 1);
        assert_eq!(totient(2), 1);
        assert_eq!(totient(6), 2);   // coprime: 1, 5
        assert_eq!(totient(9), 6);   // coprime: 1,2,4,5,7,8
        assert_eq!(totient(10), 4);  // coprime: 1,3,7,9
        assert_eq!(totient(12), 4);  // coprime: 1,5,7,11
    }

    #[test]
    fn test_prime_totient() {
        for p in [2u64, 3, 5, 7, 11, 13, 97] {
            assert_eq!(totient(p), p - 1, "φ({p}) should be p-1");
        }
    }

    #[test]
    fn test_prime_power() {
        // φ(p^k) = p^k - p^(k-1) = p^(k-1) * (p-1)
        assert_eq!(totient(8), 4);   // φ(2³) = 4
        assert_eq!(totient(9), 6);   // φ(3²) = 6
        assert_eq!(totient(25), 20); // φ(5²) = 20
    }

    #[test]
    fn test_sieve_matches_direct() {
        let phi = totient_sieve(100);
        for n in 1..=100u64 {
            assert_eq!(phi[n as usize], totient(n),
                "sieve[{n}] = {} but totient({n}) = {}", phi[n as usize], totient(n));
        }
    }

    #[test]
    fn test_divisor_sum_property() {
        for n in [6u64, 12, 30, 100] {
            assert_eq!(sum_divisor_totients(n), n, "sum_divisor_totients({n}) != {n}");
        }
    }

    #[test]
    fn test_multiplicative() {
        // φ is multiplicative: φ(mn) = φ(m)φ(n) when gcd(m,n)=1
        assert_eq!(totient(3 * 5), totient(3) * totient(5));
        assert_eq!(totient(4 * 9), totient(4) * totient(9));
    }
}

(* Euler's Totient Function in OCaml *)

(* Single value: φ(n) = n × ∏(1 - 1/p) over distinct prime factors *)
let totient (n : int) : int =
  let result = ref n in
  let n' = ref n in
  let p = ref 2 in
  while !p * !p <= !n' do
    if !n' mod !p = 0 then begin
      (* p is a prime factor — multiply result by (p-1)/p *)
      while !n' mod !p = 0 do n' := !n' / !p done;
      result := !result - !result / !p
    end;
    incr p
  done;
  (* Remaining prime factor > sqrt(n) *)
  if !n' > 1 then
    result := !result - !result / !n';
  !result

(* Totient sieve: compute φ(i) for all i in [0, n] in O(n log log n) *)
let totient_sieve (n : int) : int array =
  let phi = Array.init (n + 1) (fun i -> i) in
  for i = 2 to n do
    (* phi[i] = i means i hasn't been processed as prime factor yet *)
    if phi.(i) = i then begin
      (* i is prime *)
      let j = ref i in
      while !j <= n do
        phi.(!j) <- phi.(!j) - phi.(!j) / i;
        j := !j + i
      done
    end
  done;
  phi

(* Sum of totients: ∑φ(k) for k=1..n = (n*(n+1)/2 + 1)/... — test property *)
(* Property: ∑_{d|n} φ(d) = n *)
let sum_divisor_totients (n : int) : int =
  let sieve = totient_sieve n in
  (* Divisors of n *)
  let total = ref 0 in
  for d = 1 to n do
    if n mod d = 0 then total := !total + sieve.(d)
  done;
  !total

let () =
  let values = [1; 2; 6; 9; 10; 12; 36; 100] in
  List.iter (fun n ->
    Printf.printf "φ(%d) = %d\n" n (totient n)
  ) values;

  Printf.printf "\nTotient sieve up to 12:\n";
  let phi = totient_sieve 12 in
  Array.iteri (fun i v -> if i > 0 then Printf.printf "  φ(%d) = %d\n" i v) phi;

  Printf.printf "\nProperty ∑_{d|n} φ(d) = n:\n";
  List.iter (fun n ->
    Printf.printf "  n=%d: sum = %d (should be %d)\n" n (sum_divisor_totients n) n
  ) [6; 12; 30]