A345674 Euler totient function phi(n) - number of primitive roots modulo n.

0, 0, 1, 1, 2, 1, 4, 4, 4, 2, 6, 4, 8, 4, 8, 8, 8, 4, 12, 8, 12, 6, 12, 8, 12, 8, 12, 12, 16, 8, 22, 16, 20, 8, 24, 12, 24, 12, 24, 16, 24, 12, 30, 20, 24, 12, 24, 16, 30, 12, 32, 24, 28, 12, 40, 24, 36, 16, 30, 16, 44, 22, 36, 32, 48, 20, 46, 32, 44, 24

Offset: 1

Author

Robert Hutchins, Jun 22 2021

Keywords

• nonn

Crossrefs

Cf. A000010, A046144.

Programs

Maple

a:= proc(n) uses numtheory; `if`(n=1, 0, (p->
      p-add(`if`(order(i, n)=p, 1, 0), i=0..n-1))(phi(n)))
    end:
seq(a(n), n=1..70);  # Alois P. Heinz, Jun 22 2021

Mathematica

a[n_] := (e = EulerPhi[n]) - If[n == 1 || IntegerQ @ PrimitiveRoot[n], EulerPhi[e], 0]; Array[a, 100] (* Amiram Eldar, Jun 23 2021 *)

Formula

a(n) = A000010(n) - A046144(n).