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.

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

Author

Labos Elemer, Jun 06 2002

Keywords

• nonn

Comments

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

Examples

			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}.
		

Links

• 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.

Crossrefs

Cf. A048864, A072023, A074915.

Programs

Mathematica

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

PARI

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

Formula

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