A074915 -id:A074915 - cp's OEIS frontend

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

Labos Elemer

nonn

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

			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.

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.

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

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

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

a(n) = eulerphi(n) - (primepi(n) - omega(n)); \\ Indranil Ghosh, Apr 27 2017

from sympy import totient, primepi, primefactors
def a(n): return totient(n) - (primepi(n) - len(primefactors(n))) # Indranil Ghosh, Apr 27 2017

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

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

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

A072022 Smallest x such that the number of nonprimes (i.e., 1 and composites) in the reduced residue set (RSS(x)) of x equals n, or 0 if there are no such x.

Original entry on oeis.org

1, 5, 7, 15, 26, 11, 13, 38, 102, 17, 19, 25, 0, 23, 35, 144, 74, 198, 29, 31, 75, 57, 104, 94, 37, 55, 69, 41, 43, 118, 0, 47, 81, 128, 87, 134, 53, 93, 480, 146, 77, 59, 61, 117, 111, 166, 172, 67, 250, 91, 71, 73, 350, 194, 129, 202, 79, 206, 212, 83, 214, 153, 218

Offset: 1

Labos Elemer, Jun 06 2002

nonn

See A074915 for a bound on A048864(x) which allows the establishment of a search range for a(n). - Giovanni Resta, Feb 25 2020

			n = 15: RRS(15) = {1,2,4,7,8,11,13,14} of which nonprimes = cRRS(15) = {1,4,8,14}, i.e., 4 terms; 15 is the smallest such number, so a(4) = 15. a(m) = 0 for m = {13, 31, 70, 119, 189, 210, 235, 236}.

Giovanni Resta, 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.

Cf. A048864, A072023, A074915.

f[x_] := EulerPhi[x]-PrimePi[x]+Length[FactorInteger[x]] t=Table[0, {256}]; Do[s=f[n]; If[s<257&&t[[s]]==0, t[[s]]=n], {n, 3, 1000000}]; t
(* Second program: *)
With[{s = Table[Count[Range[n - 1], k_ /; And[CoprimeQ[k, n], ! PrimeQ@ k]], {n, 10^3}]}, Function[{t, u}, Take[#, 63] &@ Join[{1}, Rest@ ReplacePart[t, Map[# -> Lookup[u, #][[1]] &, Rest@ Keys@ u]]]] @@ {ConstantArray[0, Max@ s], KeySort@ PositionIndex@ s}] (* Michael De Vlieger, Jul 30 2017 *)

f(n) = eulerphi(n) - (primepi(n) - omega(n)); \\ A048864
a(n) = {my(k=1); while (f(k) != n, k++); k;} \\ Michel Marcus, Aug 07 2019

a(n) = min{x; A048864(x)=n}; a(n)=0 if no such number exists.

A072023 Values of k such that A072022(k)=0.

Original entry on oeis.org

13, 31, 70, 119, 189, 210, 235, 236, 265, 301, 303, 317, 345, 352, 366, 448, 470, 472, 479, 498, 500, 511, 520, 546, 557, 562, 572, 578, 580, 624, 674, 682, 691, 724, 740, 747, 768, 784, 808, 815, 876, 878, 880, 948, 957, 964, 981, 990, 995, 998, 1017, 1035, 1044

Offset: 1

Labos Elemer, Jun 06 2002

nonn

See A074915 for a bound on A048864(x) which allows the establishment of a suitable search range the terms of this sequence. - Giovanni Resta, Feb 25 2020

			13 is a term because a number whose RRS includes exactly 13 nonprime numbers doesn't exist. Phi(x) - Pi(x) + omega(x) = 13 has no solution.

Giovanni Resta, Table of n, a(n) for n = 1..10000

Cf. A048864, A072022, A074915, A000010, A000720, A001221.

Mathematica
```
(* See A072022. *)
```

More terms (search up to 10^6) from Michel Marcus, Aug 08 2019

Terms a(51) and beyond from Giovanni Resta, Feb 25 2020

A076366 Number of numbers for which the count of nonprimes (i.e., 1 and composites) in their reduced residue set equals n.

Original entry on oeis.org

10, 6, 6, 4, 4, 7, 3, 4, 3, 7, 4, 4, 0, 6, 5, 1, 4, 3, 7, 4, 7, 2, 3, 3, 2, 2, 6, 5, 2, 2, 0, 6, 4, 3, 5, 4, 5, 3, 1, 3, 3, 4, 4, 6, 2, 3, 1, 6, 1, 6, 3, 6, 1, 4, 4, 4, 1, 1, 3, 6, 3, 2, 4, 4, 1, 1, 2, 4, 6, 0, 3, 4, 3, 5, 4, 1, 2, 8, 2, 5, 6, 2, 2, 5, 1, 4, 2, 4, 7, 2, 1, 2, 6, 1, 3, 5, 2, 3, 5, 3

Offset: 1

Labos Elemer, Oct 10 2002

nonn

			A048864(x) = 13: S = {},                                a(13) =  0;
A048864(x) = 16: S = {144},                             a(16) =  1;
A048864(x) = 22: S = {57,92},                           a(22) =  2;
A048864(x) = 7:  S = {13,34,50},                        a(7)  =  3;
A048864(x) = 4:  S = {15,22,54,84},                     a(4)  =  4;
A048864(x) = 15: S = {35,64,68,156,240},                a(15) =  5;
A048864(x) = 2:  S = {5,10,14,20,42,60},                a(2)  =  6;
A048864(x) = 6:  S = {11,21,32,40,72,78,210},           a(6)  =  7;
A048864(x) = 78: S = {133,177,268,440,490,552,870,990}, a(78) =  8;
A048864(x) = 1:  S = {1,2,3,4,6,8,12,18,24,30},         a(1)  = 10; See A048597.

Giovanni Resta, Table of n, a(n) for n = 1..10000

Cf. A000010, A000720, A001221, A048597, A048864, A048865, A070971, A072022, A072023, A074915.

listn(nn) = {my(v = vector(10^5, n, eulerphi(n) - (primepi(n) - omega(n)))); vector(nn, k, if (#(w=Vec(select(x->(x==k), v, 1))) == 0, 0, #w));} \\ Michel Marcus, Feb 23 2020

a(n) = Card{x; A048864(x) = n}; a(n)=0 if supposedly no such number exists (see A072023).

A332839 Irregular triangle whose n-th row lists the integers x such that the number of nonprimes (i.e., 1 and composites) in the reduced residue set (RSS(x)) of x equals n, or 0 if there are no such x.

Original entry on oeis.org

1, 2, 3, 4, 6, 8, 12, 18, 24, 30, 5, 10, 14, 20, 42, 60, 7, 9, 16, 36, 48, 90, 15, 22, 54, 84, 26, 28, 66, 120, 11, 21, 32, 40, 72, 78, 210, 13, 34, 50, 38, 44, 70, 150, 102, 114, 126, 17, 27, 46, 56, 96, 108, 180, 19, 33, 52, 132, 25, 45, 80, 168, 0, 23, 39, 58, 62, 110, 138

Offset: 1

Michel Marcus, Feb 26 2020

			Triangle begins:
1, 2, 3, 4, 6, 8, 12, 18, 24, 30;
5, 10, 14, 20, 42, 60;
7, 9, 16, 36, 48, 90;
15, 22, 54, 84;
26, 28, 66, 120;
11, 21, 32, 40, 72, 78, 210;
...

Abhijit A J, A. Satyanarayana Reddy, Number of non-primes in the set of units modulo n, arXiv:1907.09908 [math.GM], 2019. See p. 3.

Cf. A048597 (1st row), A072022 (least x), A074915 (largest x), A076366 (row lengths).

t = Select[ Table[{ EulerPhi[n] - PrimePi[n] + PrimeNu[n], n}, {n, 2000}], #[[1]] <= 100 &]; c = Complement[Range[100], First /@ t]; Last /@ (Sort@ Join[ Transpose[{c, 0 c}], t]) (* Giovanni Resta, Feb 26 2020 *)

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

Extensions

A072022 Smallest x such that the number of nonprimes (i.e., 1 and composites) in the reduced residue set (RSS(x)) of x equals n, or 0 if there are no such x.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A072023 Values of k such that A072022(k)=0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A076366 Number of numbers for which the count of nonprimes (i.e., 1 and composites) in their reduced residue set equals n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

A332839 Irregular triangle whose n-th row lists the integers x such that the number of nonprimes (i.e., 1 and composites) in the reduced residue set (RSS(x)) of x equals n, or 0 if there are no such x.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica