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,5

Comments

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

Links

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

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

Example

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.

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 *)

Prog

(PARI) A048865(n)=primepi(n)-omega(n)
(Haskell)
a048865 n = sum $ map a010051 [t | t <- [1..n], gcd n t == 1]
-- Reinhard Zumkeller, Sep 16 2011

Crossrefs

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

Sequence in context: A132382 A366627 A325495 * A058754 A279909 A125087

Adjacent sequences: A048862 A048863 A048864 * A048866 A048867 A048868

Keyword

nonn

Author

Labos Elemer

Status

approved