A306442 Greatest integer N such that the number of base-n-zero containing numbers [<= N] <= the number of base-n-zerofree numbers [<= N].

3, 27, 131, 679, 7809, 34211, 274511, 4793487, 20327615, 222222219, 5187484917, 31896823991, 298693399003, 8722140365427, 70433726283479, 600479950316063, 21047228319925113, 252325338960485915, 3284805263774079161, 68985263157894736839

Offset: 2

Author

Hieronymus Fischer, Mar 26 2019

Keywords

• nonn
• base

Comments

For numbers k > a(n) the number of base-n-zero containing numbers <= k is always greater than the number of base-n-zerofree numbers <= k. This boundary is rapidly growing as the base n rises (see formula section).

The quotient numOfZerofreeNum_n(k)/numOfZeroNum_n(k) tends to 0 for k --> infinity and each fixed base n. Formally, numOfZerofreeNum_n(k)/numOfZeroNum_n(k) = O(k^c) with a constant c := c(n) = log(n-1)/(log(n) - 1 < 0, if n > 2. For n = 2 we have numOfZerofreeNum_2(k) = floor(log_2(k+1)), numOfZeroNum_2(k) = (k + 1 - floor(log_2(k+1)), thus numOfZerofreeNum_2(k)/ numOfZeroNum_2(k) = (k + 1)^(-1) * floor(log_2(k+1)) / (1 - floor(log_2(k+1))/(k+1)) = O(log(k)/k). Example: n = 3, numOfZerofreeNum_3(k)/numOfZeroNum_3(k) = O(k^(-0.369070...)); example: n = 10, numOfZerofreeNum _10(k)/numOfZeroNum_10(k) = O(k^(-0.045757490...)).

The first term a(2) = 3 = 11_2 is the only one which is a zerofree (i.e., a zeroless) number (in base 2), all the other terms a(n) are zero containing numbers (in base n). In any case, a(n) + 1 is always a zero containing number (in base n).

All terms are odd. Proof: The definition implies numOfZeroNum_n(a(n)) = numOfZerofreeNum_n(a(n)). In general, we have numOfZeroNum_n(k) + numOfZerofreeNum_n(k) = k + 1. It follows a(n) = 2*numOfZeroNum_n(a(n)) - 1.

a(n) >= A306195(n), equality holds for n = 5, 8, 11, 14, 15, 17, 18, 21, 24, 27, 28, 30, 31, 34, 37, 40, 41, 43, 44, 47, 50, 51, 53, 54, 56, 57, 60, 63, 64, 66, 67, 69, 70, 73, 76, 77, 79, 80, 82, 83, 86, 89, 90, 92, 93, 96, 99, .... For significantly large n, equality holds true for those bases which satisfy fract((n-1/2)*log(2) + O(1/n)) < 1/2 + O(1/n). This is true for infinitely many indices n. Let e(n) be the number of bases m <= n for which a(m) = A306195(m), then lim_{n->infinity} e(n)/n > 1/2, i.e., for large n, on average, at least every second term of this sequence is also a term of A306195.

Examples

			a(2) = 3, since numOfZeroNum_2(3) [= the number of zero numbers <= 3, in base 2] is less than or equal to numOfZerofreeNum_2(3) [the number of zerofree numbers <= 3, in base 2], i.e., numOfZeroNum_2(3) = 2 <= 2 = numOfZerofreeNum_2(3), but numOfZeroNum_2(k) > numOfZerofreeNum_2(k) for k > 3. Hint: the zero numbers <= 3 in base 2 are 0 = 0_2 and 2 = 10_2, the zerofree numbers <= 3 in base 2 are 1 = 1_2 and 3 = 11_2.
a(3) = 27, since numOfZeroNum_3(27) = 14 <= 14 = numOfZerofreeNum_3(27) but numOfZeroNum_3(k) > numOfZerofreeNum_3(k) for k > 27. Hint: the zero numbers <= 27 in base 3 are 0_3, 10_3, 20_3, 100_3, 101_3, 102_3, 110_3 120_3, 200_3, 201_3, 202_3, 210_3, 220_3 and 1000_3 = 27, the zerofree numbers <= 27 in base 3 are 1_3, 2_3, 11_3, 12_3, 21_3, 22_3, 111_3, 112_3, 121_3, 122_3, 211_3, 212_3, 221_3 and 222_3 = 26.
		

Links

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

Crossrefs

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

Formula

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

a(n) = max(k | numOfZeroNum_n(k) <= numOfZerofreeNum_n(k)).

Because of d = d(n) < 1, numOfZeroNum_n(k) = k*(1 + O(k^(d-1)), numOfZerofreeNum _n(k) = O(k^d) and numOfZeroNum_n(1) = 1 = numOfZerofreeNum_n(1) this maximum always exists (for n > 2). This is also true for the case n = 2, since numOfZeroNum_2(k) = k*(1 + O(log(k)/k)) and numOfZerofreeNum_2(k) = O(log(k)).

a(n) = max(k > 1 | numOfZeroNum_n(k) = (n + 1)/2).

a(n) = max(k > 1 | numOfZerofreeNum _n(k) = (n + 1)/2).

See A324160 and A324161 for general formulas regarding numOfZeroNum_n(k) and numOfZerofreeNum_n(k).

Estimate of the n-th term (n > 2):

a(n) < (2*(n-1)/(n-2))^(1/(1-d)) - 1,

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

Also, but less accurate,

a(n) < (2*(n-1)/(n-2))^((n-1/2)*log(n)), n > 2,

a(n) < n*2^(n*log(n)), n > 1.

a(n) >= A306195(n), for further lower bound estimations see A306195.

Asymptotic behavior:

a(n) = O(n*2^((n-1/2)*log(n))).

Lower and upper limits:

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

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