A074818 Number of integers in {1, 2, ..., prime(n)} that are coprime to n.

2, 2, 4, 4, 9, 5, 15, 10, 16, 12, 29, 13, 38, 19, 26, 27, 56, 21, 64, 29, 42, 36, 80, 30, 78, 47, 69, 46, 106, 31, 123, 66, 84, 66, 103, 51, 153, 78, 104, 70, 175, 52, 187, 88, 106, 96, 207, 75, 195, 92, 147, 111, 237, 84, 187, 113, 170, 131, 273, 75, 279, 142, 176

Offset: 1

Author

Joseph L. Pe, Oct 04 2002

Keywords

• nonn

Comments

Compare the definition of a(n) to phi(n) = number of integers in {1, 2, ..., n} that are coprime to n.

Examples

			There are five numbers in {1, 2, ..., prime(6) = 13} that are coprime to 6, i.e. 1, 5, 7, 11, 13. Hence a(6) = 5.
		

Crossrefs

Cf. A000010, A000040, A004648, A008683.

Cf. A129139, A074919, A074882, A074933, A074934, A057828.

Programs

Maple

with(numtheory): seq(add(mobius(d)*floor(ithprime(n)/d), d in divisors(n)), n=1..100) ; # Ridouane Oudra, Jun 04 2025

Mathematica

h[n_] := Module[{l}, l = {}; For[i = 1, i <= Prime[n], i++, If[GCD[i, n] == 1, l = Append[l, i]]]; l]; Table[Length[h[i]], {i, 1, 100}]

PARI

a(n) = sum(k=1, prime(n), gcd(k, n)==1); \\ Michel Marcus, Jun 04 2025

PARI

a(n) = my(p = prime(n)); eulerphi(n) * (p \ n) + sum(i = (p \ n)*n + 1, p, gcd(i, n) == 1); \\ David A. Corneth, Jun 04 2025

Formula

a(n) = Sum_{d|n} mu(d)*floor(prime(n)/d). - Ridouane Oudra, Jun 04 2025