cp's OEIS Frontend

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.

%I A074915 #45 Aug 14 2025 04:07:12
%S A074915 30,60,90,84,120,210,50,150,126,180,132,168,0,138,240,144,140,330,420,
%T A074915 130,300,92,390,234,294,228,360,222,160,246,0,336,276,630,510,450,378,
%U A074915 152,480,280,318,196,342,660,165,396,172,546,250,840,504,408,350,600
%N 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.
%C A074915 It is conjectured that x is always bounded.
%C A074915 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
%C A074915 From _Giovanni Resta_, Feb 25 2020: (Start)
%C A074915 The following bounds (valid for n>1) are known:
%C A074915 primepi(n) < 1.256*n/log(n),
%C A074915 omega(n) > 0,
%C A074915 phi(n) > n/(3/log(log(n)) + exp(g)*log(log(n))), where g = A001620 = 0.5770836... is the Euler-Mascheroni constant.
%C A074915 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)
%H A074915 Giovanni Resta, <a href="/A074915/b074915.txt">Table of n, a(n) for n = 1..10000</a>
%F A074915 a(n) = max{x; A048864(x)=n}; a(n)=0 if no such number exists (see A072023).
%e A074915 One nonprime (=1) is in RRS of {1,2,3,4,6,8,12,18,24,30}; min=1, max=30. See A048597.
%e A074915 Two nonprimes are in RRS of {5,10,14,20,42,60}; min=A072022(2), max = a(2) = 60 here.
%e A074915 For entries of A072023 neither min nor max is believed to exist.
%o A074915 (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
%Y A074915 Cf. A000010, A000720, A001221, A048597, A048864, A048865, A072022, A072023.
%K A074915 nonn
%O A074915 1,1
%A A074915 _Labos Elemer_, Oct 10 2002