A306521 Least integer N > 2 such that the number of primes (<=N) <= the number of base-n-zero containing numbers (<=N).

3, 3, 4, 28, 42, 104, 136, 329, 510, 856, 1449, 2212, 2782, 3434, 4188, 5042, 6001, 7082, 8276, 9604, 11062, 12666, 14405, 31651, 35694, 40061, 66427, 73966, 108764, 149756, 197516, 288280, 354924, 515538, 701002, 963687, 1318399, 1840377

Offset: 2

Author

Hieronymus Fischer, Mar 29 2019

Keywords

• nonn
• base

Comments

a(n) <= A306526(n), equality holds for n = 2, 14, 15, 16, 17, 18, 19, 20, 40, 41, 42, 44, 45, 46, 47, 48, 49, 50, 51, 52 (but a(n) < A306526(n) for all other indices n up to 82). For sufficiently large n, equality holds true for those bases n which satisfy 1/2 <= fract(sqrt(n/log(n)) + O(sqrt(log(n)/n))) < 3/4. This is true for infinitely many further indices, at least for all bases n = ceiling(x), where x is a solution of x/log(x) = k-th triangular number + 1/4, k > 1. For k = 2..10 the corresponding bases are n = 19, 48, 92, 152, 230, 326, 440, 574, 727. Let e(n) be the number of bases m <= n for which a(m) = A306526(m), then lim_{n->infinity} e(n)/n >= 1/4. Conjecture: lim_{n->infinity} e(n)/n = 1/4.

Examples

			a(2) = 3, since pi(3) = 2 <= 2 = numOfZeroNum_2(3), where numOfZeroNum_2(m) is the number of base-2-zero containing numbers <= m and pi(m) = number of primes <= m. The first base-2-zero containing numbers are 0 = 0_2, 2 = 10_2, 4 = 100_2, ... (Hint: numbers <= 2 are out of scope for self-evident reasons).
a(3) = 3, since pi(3) = 2 <= 2 = numOfZeroNum_3(3), where numOfZeroNum_3(m) is the number of base-3-zero containing numbers <= m and pi(m) = number of primes <= m. The first base-3-zero containing numbers are 0 = 0_2, 3 = 10_3, 6 = 20_3, 9 = 100_3, 10 = 101_3, 11 = 102_3, 12 = 120_3, ...
a(4) = 4, since pi(3) = 2 > 1 = numOfZeroNum_4(3), pi(4) = 2 <= 2 = numOfZeroNum_4(4), where numOfZeroNum_4(m) is the number of base-4-zero containing numbers <= m and pi(m) = number of primes <= m. The first base-4-zero containing numbers are 0 = 0_2, 4 = 10_4, 8 = 20_4, ...
		

Links

• Hieronymus Fischer, Table of n, a(n) for n = 2..100

Crossrefs

Cf. A011540, A052382, A306195, A306442, A306526, A324154, A324155, A324160, A324161.

Programs

PARI

cz(m,n) = vecmin(digits(m, n))==0;
a(n) = {my(m=2, nbz=1+sum(k=1, 2, cz(k,n)), pmp=primepi(2)); for (m=3, oo, if (isprime(m), pmp++); if (cz(m,n), nbz++); if (pmp <= nbz, return (m)););} \\ Michel Marcus, Jun 10 2019

Formula

With numOfZeroNum_n(k) [= the number of base-n-zero containing numbers <= k] and pi(k) [= the number of primes <= k] and d := log(n-1)/log(n):

a(n) = min(k > 2 | pi(k) <= numOfZeroNum_n(k)). Because of d = d(n) < 1, numOfZeroNum_n(k) = k*(1 + O(k^(d-1)), pi(k) = k/log(k)*(1+o(1)), and pi(3) = 2 >= 2 = numOfZeroNum_n(3), this minimum always exists (for n > 2). The case n = 2 is obvious. See A324160 regarding general formulas for numOfZeroNum_n(k).

Estimate of the n-th term:

a(n) > e*(1 + c1/c2*(1 + sqrt(1 + c2*c3/c1^2)))^(1/(1-d)), for n > 6,

where d := log(n-1)/log(n),

c0 := e^(1-d),

c1 := (n-1)^d/(n-2) - 1/e^(sqrt(n*log(n))) - d*c0,

c2 := (n-1)^d/(n-2) - 1/e^(sqrt(n*log(n))) + (1 - 1/sqrt(n*log(n)))*c0,

c3 := 2*(1-d)*c0.

Also, but less accurate, for n > 6,

a(n) > e*(1 + 1/(sqrt(n*log(n)) - 2))^(1/(1-d)).

a(n) > e*(1 + 1/(sqrt(n*log(n)) - 2))^((n-1/2)*log(n)).

a(n) <= A306526(n), see A306526 for further upper bound estimations.

Asymptotic behavior:

a(n) = O(sqrt(n)*e^sqrt(n*log(n))).

lim sup a(n)/e^(sqrt(n*log(n))+(log(n)+1)/2) = 1, for n --> infinity.

lim inf a(n)/e^(sqrt(n*log(n))+1/2) = 1, for n --> infinity.