

A048864


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


14



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, 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, 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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,5


COMMENTS

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


LINKS

Michael De Vlieger, Table of n, a(n) for n = 1..10000
Abhijit A J, A. Satyanarayana Reddy, Number of nonprimes in the set of units modulo n, arXiv:1907.09908 [math.GM], 2019.
Abhijit A. J. and A. Satyanarayana Reddy, Number of nonprimes in the set of units modulo n, The Mathematics Student, Vol. 88, No. 12 (2019), 147152.


FORMULA

a(n) = A036997(n) + 1.  Peter Luschny, Oct 22 2010
a(n) = A000010(n)  (A000720(n)  A001221(n)).


EXAMPLE

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.
At n = 100, phi(100) = 40, phi(100)  (pi(100)  A001221(100)) = 17, thus a(100) = 17.


MAPLE

A048864 := n > nops(select(k>gcd(k, n)=1, remove(isprime, [$1..n]))); # Peter Luschny, Oct 22 2010


MATHEMATICA

Array[EulerPhi@ #  (PrimePi@ #  PrimeNu@ #) &, 82] (* Michael De Vlieger, Jul 03 2016 *)
Table[Length[Select[Range[n], GCD[n, #] == 1 && Not[PrimeQ[#]] &]], {n, 80}] (* Alonso del Arte, Oct 02 2017 *)


PROG

(PARI) a(n) = eulerphi(n)  (primepi(n)  omega(n)); \\ Indranil Ghosh, Apr 27 2017
(Python)
from sympy import totient, primepi, primefactors
def a(n): return totient(n)  (primepi(n)  len(primefactors(n))) # Indranil Ghosh, Apr 27 2017


CROSSREFS

Cf. A039776, A000010, A000720, A001221, A037228, A072022, A072023, A074915.
Sequence in context: A230070 A224762 A039776 * A003139 A349918 A244797
Adjacent sequences: A048861 A048862 A048863 * A048865 A048866 A048867


KEYWORD

nonn


AUTHOR

Labos Elemer


EXTENSIONS

Converted second formula to an equation, added commas to the example  R. J. Mathar, Oct 23 2010


STATUS

approved



