A109606 Number of numbers k with 1 < k < n which are relatively prime to n.
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
Offset: 1
Examples
a(9) = 5 because 2, 4, 5, 7, 8 are coprime to 9. a(10) = 3 because 3, 7, 9 are coprime to 10.
Links
- Vincenzo Librandi, Table of n, a(n) for n = 1..1000
- N. J. A. Sloane, Families of Essentially Identical Sequences, Mar 24 2021 (Includes this sequence)
Crossrefs
Cf. A000010.
Programs
-
Magma
[EulerPhi(n)-1: n in [1..80]]; // Vincenzo Librandi, Sep 16 2017
-
Maple
A109606 := n -> numtheory[phi](n) - 1: # Peter Luschny, Aug 05 2011
-
Mathematica
EulerPhi[Range[80]] - 1 (* Alonso del Arte, Sep 16 2017 *)
-
PARI
a(n)=eulerphi(n)-1 \\ Charles R Greathouse IV, Jul 25 2013
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
Extensions
Definition modified by Reinhard Zumkeller, Mar 03 2009
Offset set to 1, in accordance to A000010, by Peter Luschny, Aug 05 2011
Comments