A048865 a(n) is the number of primes in the reduced residue system mod n.

0, 0, 1, 1, 2, 1, 3, 3, 3, 2, 4, 3, 5, 4, 4, 5, 6, 5, 7, 6, 6, 6, 8, 7, 8, 7, 8, 7, 9, 7, 10, 10, 9, 9, 9, 9, 11, 10, 10, 10, 12, 10, 13, 12, 12, 12, 14, 13, 14, 13, 13, 13, 15, 14, 14, 14, 14, 14, 16, 14, 17, 16, 16, 17, 16, 15, 18, 17, 17, 16, 19, 18, 20, 19, 19, 19, 19, 18, 21, 20, 21

Offset: 1

Author

Labos Elemer

Keywords

• nonn

Comments

The number of primes p <= n with p coprime to n. - Enrique Pérez Herrero, Jul 23 2011

Examples

			At n=30 all but 1 element in reduced residue system of 30 are primes (see A048597) so a(30) = Phi(30) - 1 = 7.
n=100: a(100) = Pi(100) - A001221(100) = 25 - 2 = 23.
		

Links

• Reinhard Zumkeller, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A000010, A000720, A001221, A010051, A048597, A070296, A368616, A368641.

Programs

Haskell

a048865 n = sum $ map a010051 [t | t <- [1..n], gcd n t == 1]
-- Reinhard Zumkeller, Sep 16 2011

Maple

A048865 := n ->  nops(select(isprime, select(k -> igcd(n,k) = 1, [$1..n]))):
seq(A048865(n), n = 1..81); # Peter Luschny, Jul 23 2011

Mathematica

p=Prime[Range[1000]]; q=Table[PrimePi[i], {i, 1, 1000}]; t=Table[c=0; Do[If[GCD[p[[j]], i]==1, c++ ], {j, 1, q[[i-1]]}]; c, {i, 2, 950}]
Table[Count[Select[Range@ n, CoprimeQ[#, n] &], p_ /; PrimeQ@ p], {n, 81}] (* Michael De Vlieger, Apr 27 2016 *)
Table[PrimePi[n] - PrimeNu[n], {n, 50}] (* G. C. Greubel, May 16 2017 *)

PARI

A048865(n)=primepi(n)-omega(n)

Formula

a(n) = A000720(n) - A001221(n).

From Reinhard Zumkeller, Apr 05 2004: (Start)

a(n) = Sum_{p prime and p<=n} (ceiling(n/p) - floor(n/p)).

a(n) = A093614(n) - A013939(n). (End)

a(n) = A001221(A001783(n)). - Enrique Pérez Herrero, Jul 23 2011

a(n) = A368616(n) - A368641(n). - Wesley Ivan Hurt, Jan 01 2024