Euler's totient function: phi(n)

1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 4, 12, 6, 8, 8, 16, 6, 18, 8, 12, 10, 22, 8, 20, 12, 18, 12, 28, 8, 30, 16, 20, 16, 24, 12, 36, 18, 24, 16, 40, 12, 42, 20, 24, 22, 46, 16, 42, 20, 32, 24, 52, 18, 40, 24, 36, 28, 58, 16, 60, 30, 36, 32, 48, 20, 66, 32, 44, 24, 70, 24, 72, 36, 40, 36, 60, 24, 78, 32, 54, 40, 82, 24, 64, 42, 56, 40, 88, 24, 72, 44, 60, 46, 72, 32, 96, 42, 60

OFFSET

1

COMMENTS

Count of integers k in the range 1..n such that gcd(n,k) = 1.

Number of elements in a reduced residue system modulo n.

PROPERTIES

Multiplicative with a(p^k) = p^(k-1) * (p-1).

FORMULAS

a(n) = Sum_{d|n} d*μ(n/d), where μ is the Möbius function

a(n) = n * Product_{p|n} (1 - 1/p)

PROGRAMS

Perl

use ntheory qw(:all);
sub a { euler_phi(shift) }

PARI/GP

a(n) = eulerphi(n);

Sidef

func a(n) { phi(n) }

SEE ALSO

results matching ""

    No results matching ""