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

%I #45 Jan 01 2024 22:28:55

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

%T 9,9,9,11,10,10,10,12,10,13,12,12,12,14,13,14,13,13,13,15,14,14,14,14,

%U 14,16,14,17,16,16,17,16,15,18,17,17,16,19,18,20,19,19,19,19,18,21,20,21

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

%C The number of primes p <= n with p coprime to n. - _Enrique Pérez Herrero_, Jul 23 2011

%H Reinhard Zumkeller, <a href="/A048865/b048865.txt">Table of n, a(n) for n = 1..10000</a>

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

%F From _Reinhard Zumkeller_, Apr 05 2004: (Start)

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

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

%F a(n) = A001221(A001783(n)). - _Enrique Pérez Herrero_, Jul 23 2011

%F a(n) = A368616(n) - A368641(n). - _Wesley Ivan Hurt_, Jan 01 2024

%e At n=30 all but 1 element in reduced residue system of 30 are primes (see A048597) so a(30) = Phi(30) - 1 = 7.

%e n=100: a(100) = Pi(100) - A001221(100) = 25 - 2 = 23.

%p A048865 := n -> nops(select(isprime, select(k -> igcd(n,k) = 1, [$1..n]))):

%p seq(A048865(n), n = 1..81); # _Peter Luschny_, Jul 23 2011

%t 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}]

%t Table[Count[Select[Range@ n, CoprimeQ[#, n] &], p_ /; PrimeQ@ p], {n, 81}] (* _Michael De Vlieger_, Apr 27 2016 *)

%t Table[PrimePi[n] - PrimeNu[n], {n, 50}] (* _G. C. Greubel_, May 16 2017 *)

%o (PARI) A048865(n)=primepi(n)-omega(n)

%o (Haskell)

%o a048865 n = sum $ map a010051 [t | t <- [1..n], gcd n t == 1]

%o -- _Reinhard Zumkeller_, Sep 16 2011

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

%K nonn

%O 1,5

%A _Labos Elemer_