

A109606


Number of numbers k with 1 < k < n which are relatively prime to n.


5



0, 0, 1, 1, 3, 1, 5, 3, 5, 3, 9, 3, 11, 5, 7, 7, 15, 5, 17, 7, 11, 9, 21, 7, 19, 11, 17, 11, 27, 7, 29, 15, 19, 15, 23, 11, 35, 17, 23, 15, 39, 11, 41, 19, 23, 21, 45, 15, 41, 19, 31, 23, 51, 17, 39, 23, 35, 27, 57, 15, 59, 29, 35, 31, 47, 19, 65, 31, 43, 23, 69, 23, 71, 35, 39, 35
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,5


COMMENTS

Number of nonprincipal Dirichlet characters mod n.  Charles R Greathouse IV, Jul 25 2013


LINKS

Vincenzo Librandi, Table of n, a(n) for n = 1..1000


FORMULA

a(n) = phi(n)  1 = A000010(n)  1.
a(n) = card({k k prime to n} setminus {k k divides n}).  Peter Luschny, Aug 05 2011
G.f.: x/(1  x) + Sum_{k >= 1} mu(k)*x^k/(1  x^k)^2.  Ilya Gutkovskiy, Mar 16 2017


EXAMPLE

a(9) = 5 because 2, 4, 5, 7, 8 are coprime to 9.
a(10) = 3 because 3, 7, 9 are coprime to 10.


MAPLE

A109606 := n > numtheory[phi](n)  1: # Peter Luschny, Aug 05 2011


MATHEMATICA

EulerPhi[Range[80]]  1 (* Alonso del Arte, Sep 16 2017 *)


PROG

(PARI) a(n)=eulerphi(n)1 \\ Charles R Greathouse IV, Jul 25 2013
(MAGMA) [EulerPhi(n)1: n in [1..80]]; // Vincenzo Librandi, Sep 16 2017


CROSSREFS

Cf. A000010.
Sequence in context: A071168 A091926 A325685 * A318727 A307806 A127418
Adjacent sequences: A109603 A109604 A109605 * A109607 A109608 A109609


KEYWORD

nonn,easy


AUTHOR

Andrew Weimholt, Jul 31 2005


EXTENSIONS

Definition modified by Reinhard Zumkeller, Mar 03 2009
Offset set to 1, in accordance to A000010, by Peter Luschny, Aug 05 2011


STATUS

approved



