# P37 - Calculate Euler's totient function phi(m) (improved).

*Author: Philip Potter*

# Specification

P37 (**) Calculate Euler's totient function phi(m) (improved). See problem P34 for the definition of Euler's totient function. If the list of the prime factors of a number m is known in the form of problem P36 then the function phi(m) can be efficiently calculated as follows: Let ((p1 m1) (p2 m2) (p3 m3) ...) be the list of prime factors (and their multiplicities) of a given number m. Then phi(m) can be calculated with the following formula: phi(m) = (p1-1) * p1 ** (m1-1) * (p2-1) * p2 ** (m2-1) * (p3-1) * p3 ** (m3-1) * ...

# Example

> say "phi2(315): ", totient(315); phi2(315): 144

Source code: P37-rhebus.pl

use v6; # Straight from P36-rhebus.pl sub prime_factors_mult (Int $n) { my $residue = $n; my @values = (2,3,*+2 ... * > $n); gather for @values -> $k { my $mult=0; while $residue %% $k { $mult++; $residue div= $k; } take $k => $mult if $mult; last if $residue == 1; if $k > sqrt $residue { take $residue => 1; last; } } } # 1. One-liner version say "phi($_): ", [*] prime_factors_mult($_).map({ (.key-1) * .key ** (.value-1) }) for 1..20; say [*] prime_factors_mult(315).map: { (.key-1) * .key ** (.value-1) }; # 2. sub version # note that when prime_factors_mult returns an empty list, [*] returns the # multiplicative identity 1. This means we don't need to special-case # totient(1) like in P34-rhebus.pl sub totient (Int $n) { my @factors = prime_factors_mult($n); return [*] @factors.map: { (.key-1) * .key ** (.value-1) } } # This hangs too! \o/ # say "phi2($_): ", totient($_) for 1..20; say "phi2(315): ", totient(315);