|
| |
|
|
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.
|
|
6
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,1
|
|
|
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
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)
|
|
|
LINKS
|
|
|
|
FORMULA
|
a(n) = max{x; A048864(x)=n}; a(n)=0 if no such number exists (see A072023).
|
|
|
EXAMPLE
|
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.
|
|
|
PROG
|
(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
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
