login
Number of nonprime numbers (composites and 1) in the reduced residue system of n.
14

%I #34 Feb 25 2020 08:05:56

%S 1,1,1,1,2,1,3,1,3,2,6,1,7,2,4,3,10,1,11,2,6,4,14,1,12,5,10,5,19,1,20,

%T 6,11,7,15,3,25,8,14,6,28,2,29,8,12,10,32,3,28,7,19,11,37,4,26,10,22,

%U 14,42,2,43,14,20,15,32,5,48,15,27,8,51,6,52,17,21,17,41,6,57,12,33,20

%N Number of nonprime numbers (composites and 1) in the reduced residue system of n.

%C Differs from A039776 at n = 20, 21, ...

%H Michael De Vlieger, <a href="/A048864/b048864.txt">Table of n, a(n) for n = 1..10000</a>

%H Abhijit A J, A. Satyanarayana Reddy, <a href="https://arxiv.org/abs/1907.09908">Number of non-primes in the set of units modulo n</a>, arXiv:1907.09908 [math.GM], 2019.

%H Abhijit A. J. and A. Satyanarayana Reddy, <a href="http://www.indianmathsociety.org.in/mathstudent-part-1-2019.pdf#page=153">Number of non-primes in the set of units modulo n</a>, The Mathematics Student, Vol. 88, No. 1-2 (2019), 147-152.

%F a(n) = A036997(n) + 1. - _Peter Luschny_, Oct 22 2010

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

%e At n = 10, we see that the numbers below 10 coprime to 10 are 1, 3, 7, 9. Removing 3 and 7, which are prime, we are left with two numbers, 1 and 9. Hence a(10) = 2.

%e At n = 100, phi(100) = 40, phi(100) - (pi(100) - A001221(100)) = 17, thus a(100) = 17.

%p A048864 := n -> nops(select(k->gcd(k,n)=1,remove(isprime,[$1..n]))); # _Peter Luschny_, Oct 22 2010

%t Array[EulerPhi@ # - (PrimePi@ # - PrimeNu@ #) &, 82] (* _Michael De Vlieger_, Jul 03 2016 *)

%t Table[Length[Select[Range[n], GCD[n, #] == 1 && Not[PrimeQ[#]] &]], {n, 80}] (* _Alonso del Arte_, Oct 02 2017 *)

%o (PARI) a(n) = eulerphi(n) - (primepi(n) - omega(n)); \\ _Indranil Ghosh_, Apr 27 2017

%o (Python)

%o from sympy import totient, primepi, primefactors

%o def a(n): return totient(n) - (primepi(n) - len(primefactors(n))) # _Indranil Ghosh_, Apr 27 2017

%Y Cf. A039776, A000010, A000720, A001221, A037228, A072022, A072023, A074915.

%K nonn

%O 1,5

%A _Labos Elemer_

%E Converted second formula to an equation, added commas to the example - _R. J. Mathar_, Oct 23 2010