login
a(n) is the smallest x > 2 to satisfy pi(x-1)/(x-1)^n < pi(x)/x^n, where pi(x) is the prime counting function (A000720).
0

%I #41 Nov 24 2019 21:46:38

%S 3,11,29,127,347,1087,3079,8419,23531,64553,175211,480881,1304519,

%T 3523901,9558533,25874767,70115473,189961193,514272463,1394193607,

%U 3779851091,10246935679,27788566133,75370121191,204475052401,554805820477,1505578023841,4086199302077

%N a(n) is the smallest x > 2 to satisfy pi(x-1)/(x-1)^n < pi(x)/x^n, where pi(x) is the prime counting function (A000720).

%C The integer 2 satisfies the inequality for all values of n (as pi(1) = 0), so it is omitted. With n=0 the sequence is clearly satisfied by all primes.

%C Conjecture: a(n) exists for all n, that is, for all n, there exists at least one integer which satisfies the inequality.

%C Occurs when examining convergence of alternating sum to infinity of (-1^x)* pi(x)/(x^n).

%C If a(n) exists it is prime. Proof: If a(n) is composite then pi(x - 1) = pi(x), so pi(x-1)/((x-1)^n) > pi(x)/(x^n), a contradiction. - _David A. Corneth_, Oct 02 2017

%C From _Chai Wah Wu_, Apr 24 2018: (Start)

%C Conjecture above is true.

%C Theorem: a(n) exists for all n and satisfies prime(floor(e^W(e^n))) < a(n) < prime(ceiling(e^W(e^(n+1)))), where W is Lambert W function.

%C Proof: for a fixed n, let x = a(n) if it exists. Since x is prime, pi(x-1) = pi(x)-1 and thus the condition is m-1/(x-1)^n < m/x^n, where m = pi(x). This simplifies to 1-1/m < (1-1/x)^n. A result of Dusart in 1999 shows that x > m(log(m log(m))-1) when m > 1. This implies that (1-1/x)^n > (1-1/(m(log(m log(m))-1)))^n >= 1-n/(m(log(m log(m))-1)) where the last inequality is due to Bernoulli's inequality.

%C Thus (1-1/x)^n > 1-1/m if log(m log(m))-1 >= n which is satisfied if m >= e^W(e^(n+1)).

%C The lower bound on a(n) follows analogously from the 1941 upper bound on x due to Rosser: x < m log(m log(m)) when m > 5.

%C (End)

%e For n=3, the first integer which satisfies pi(x-1)/((x-1)^3) < pi(x)/(x^3) is 29 = a(3).

%t For[j = 1, j < 11, j++, For[i = 2, i < 1000000 i++, If[(PrimePi[i]/(i^j)) - (PrimePi[i-1]/((i-1)^j)) > 0, Print[i] Break[]]]]

%o (PARI) a(n) = my(x=3); while(primepi(x-1)/(x-1)^n >= primepi(x)/x^n, x++); x; \\ _Michel Marcus_, Oct 02 2017

%o (PARI) upto(u)=my(t = 1, n = 1, logt = 0, logtm1, logp, logpm1, res = List()); forprime(p = 3, u, t++; logtm1 = logt; logt = log(t); logp = log(p); logpm1 = log(p - 1); if(logtm1 + n * logp < logt + n*logpm1, listput(res, p); n++)); res \\ _David A. Corneth_, Oct 02 2017

%Y Cf. A000040, A000720.

%K nonn

%O 1,1

%A _Josh Marza_, Sep 27 2017

%E a(20)-a(28) from _Chai Wah Wu_, Apr 24 2018