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

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

Offset: 1

Author

Labos Elemer

Keywords

• nonn

Comments

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

Examples

			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.
		

Links

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

Crossrefs

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

Programs

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

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

Formula

a(n) = A036997(n) + 1. - Peter Luschny, Oct 22 2010

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

Extensions

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