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

%I #31 Sep 08 2022 08:45:19

%S 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,

%T 7,29,15,19,15,23,11,35,17,23,15,39,11,41,19,23,21,45,15,41,19,31,23,

%U 51,17,39,23,35,27,57,15,59,29,35,31,47,19,65,31,43,23,69,23,71,35,39,35

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

%C Number of nonprincipal Dirichlet characters mod n. - _Charles R Greathouse IV_, Jul 25 2013

%H Vincenzo Librandi, <a href="/A109606/b109606.txt">Table of n, a(n) for n = 1..1000</a>

%H N. J. A. Sloane, <a href="/A115004/a115004.txt">Families of Essentially Identical Sequences</a>, Mar 24 2021 (Includes this sequence)

%F a(n) = phi(n) - 1 = A000010(n) - 1.

%F a(n) = card({k| k prime to n} setminus {k| k divides n}). - _Peter Luschny_, Aug 05 2011

%F G.f.: -x/(1 - x) + Sum_{k >= 1} mu(k)*x^k/(1 - x^k)^2. - _Ilya Gutkovskiy_, Mar 16 2017

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

%e a(10) = 3 because 3, 7, 9 are coprime to 10.

%p A109606 := n -> numtheory[phi](n) - 1: # _Peter Luschny_, Aug 05 2011

%t EulerPhi[Range[80]] - 1 (* _Alonso del Arte_, Sep 16 2017 *)

%o (PARI) a(n)=eulerphi(n)-1 \\ _Charles R Greathouse IV_, Jul 25 2013

%o (Magma) [EulerPhi(n)-1: n in [1..80]]; // _Vincenzo Librandi_, Sep 16 2017

%Y Cf. A000010.

%K nonn,easy

%O 1,5

%A _Andrew Weimholt_, Jul 31 2005

%E Definition modified by _Reinhard Zumkeller_, Mar 03 2009

%E Offset set to 1, in accordance to A000010, by _Peter Luschny_, Aug 05 2011