cp's OEIS Frontend

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

%I A048865 #45 Jan 01 2024 22:28:55
%S A048865 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 A048865 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 A048865 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 A048865 a(n) is the number of primes in the reduced residue system mod n.
%C A048865 The number of primes p <= n with p coprime to n. - _Enrique Pérez Herrero_, Jul 23 2011
%H A048865 Reinhard Zumkeller, <a href="/A048865/b048865.txt">Table of n, a(n) for n = 1..10000</a>
%F A048865 a(n) = A000720(n) - A001221(n).
%F A048865 From _Reinhard Zumkeller_, Apr 05 2004: (Start)
%F A048865 a(n) = Sum_{p prime and p<=n} (ceiling(n/p) - floor(n/p)).
%F A048865 a(n) = A093614(n) - A013939(n). (End)
%F A048865 a(n) = A001221(A001783(n)). - _Enrique Pérez Herrero_, Jul 23 2011
%F A048865 a(n) = A368616(n) - A368641(n). - _Wesley Ivan Hurt_, Jan 01 2024
%e A048865 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 A048865 n=100: a(100) = Pi(100) - A001221(100) = 25 - 2 = 23.
%p A048865 A048865 := n ->  nops(select(isprime, select(k -> igcd(n,k) = 1, [$1..n]))):
%p A048865 seq(A048865(n), n = 1..81); # _Peter Luschny_, Jul 23 2011
%t A048865 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 A048865 Table[Count[Select[Range@ n, CoprimeQ[#, n] &], p_ /; PrimeQ@ p], {n, 81}] (* _Michael De Vlieger_, Apr 27 2016 *)
%t A048865 Table[PrimePi[n] - PrimeNu[n], {n, 50}] (* _G. C. Greubel_, May 16 2017 *)
%o A048865 (PARI) A048865(n)=primepi(n)-omega(n)
%o A048865 (Haskell)
%o A048865 a048865 n = sum $ map a010051 [t | t <- [1..n], gcd n t == 1]
%o A048865 -- _Reinhard Zumkeller_, Sep 16 2011
%Y A048865 Cf. A000010, A000720, A001221, A010051, A048597, A070296, A368616, A368641.
%K A048865 nonn
%O A048865 1,5
%A A048865 _Labos Elemer_