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

30, 60, 90, 84, 120, 210, 50, 150, 126, 180, 132, 168, 0, 138, 240, 144, 140, 330, 420, 130, 300, 92, 390, 234, 294, 228, 360, 222, 160, 246, 0, 336, 276, 630, 510, 450, 378, 152, 480, 280, 318, 196, 342, 660, 165, 396, 172, 546, 250, 840, 504, 408, 350, 600

Offset: 1

Author

Labos Elemer, Oct 10 2002

Keywords

• nonn

Comments

It is conjectured that x is always bounded.

If p and q are primes < sqrt(x) that do not divide x, then p*q is in RRS(x). Thus the number of composites in RRS(x) is at least (pi(sqrt(x)) - log_2(x))^2/2. If x is too large, this must be greater than n. Thus suppose N is large enough that pi(sqrt(N)) > 2*sqrt(2*n) and for all x >= N, pi(sqrt(x)) > 2*log_2(x). Then a(n) <= N. It appears that the condition pi(sqrt(x)) > 2*log_2(x) is true for all x >= 103^2. - Robert Israel, Aug 26 2018, corrected Feb 24 2020

From Giovanni Resta, Feb 25 2020: (Start)

The following bounds (valid for n>1) are known:

primepi(n) < 1.256*n/log(n),

omega(n) > 0,

phi(n) > n/(3/log(log(n)) + exp(g)*log(log(n))), where g = A001620 = 0.5770836... is the Euler-Mascheroni constant.

Combining these bounds we obtain a lower bound for A048864(k) = phi(k) - primepi(k) + omega(k), which allows the establishment of a finite search range when solving A048864(x) = n. (End)

Examples

			One nonprime (=1) is in RRS of {1,2,3,4,6,8,12,18,24,30}; min=1, max=30. See A048597.
Two nonprimes are in RRS of {5,10,14,20,42,60}; min=A072022(2), max = a(2) = 60 here.
For entries of A072023 neither min nor max is believed to exist.
		

Links

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

Crossrefs

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

Programs

PARI

lista(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, vecmax(w)));} \\ Michel Marcus, Feb 23 2020

Formula

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