A324160 Number of zero-containing nonnegative integers <= n.

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 11

Offset: 0

Author

Hieronymus Fischer, Feb 15 2019

Keywords

• nonn
• base

Comments

This sequence represents the counting function of A011540.

n = n_max = 701 is the greatest number such that a(n) <= pi(n) [the number of primes <= n]. Thus, for all indices n > n_max, we have a(n) > pi(n). For n = n_max the number of primes is pi(n) = 126.

n = n_min = 510 is the least number (> 2) such that a(n) >= pi(n) [the number of primes <= n]. Thus, for all indices 2 < n < n_min, we have a(n) < pi(n). For n = n_min the number of primes is pi(n) = 97.

Examples

			a(10) = 2, since there are two numbers <= 10 which contain a '0'-digit (0 and 10).
a(100) = 11.
a(10^3) = 182.
a(10^4) = 2621.
a(10^5) = 33572.
a(10^6) = 402131.
a(10^7) = 4619162
a(10^8) = 51572441.
a(10^9) = 564151952.
a(10^10) = 6077367551.
a(10^20) = 86322626358560955101.
a(10^50) = 99420200289176487252583981229013676068210129037751 = 9.9420200289176... *10^49
a(10^100) = 9.9997011842625...13575501*10^99.
a(10^1000) = 9.999999999999...564125755001*10^999
(here, the first 45 digits are 9's).
		

Links

• Hieronymus Fischer, Table of n, a(n) for n = 0..10000

Crossrefs

Cf. A011540, A052382, A324161, A217094.

Programs

PARI

a(n) = 1 + sum(k=1, n, vecmin(digits(k)) == 0); \\ Michel Marcus, Mar 20 2019

Formula

With m := floor(log_10(n)); k := Max_{j | j = 1..m and (floor(n/10^j) mod 10)*j = 0} = digit position of the leftmost '0' in n counted from the right (starting with 0), k = 0 if there is no '0' digit; b(n,k):= floor(n/10^k)*10^k:

a(n) = 2 + Sum_{j = 1..m} floor((b(n,k+1)-1)/10^j)*9^(j-1), if k = 0 (valid for n > 9),

a(n) = 2 + n mod 10^k + Sum_{j = 1..m} floor((b(n,k)-1)/10^j)*9^(j-1), if k > 0 (valid for n > 0),

a(n) = 2 + n mod 10^k - ceiling(fract(n/10))*(1-ceiling(k/(m+1))) + Sum_{j = 1..m} floor((b(n,k)-1)/10^j)*9^(j-1) (all k, valid for n > 0).

a(n) + A324161(n) = n + 1

a(A011540(n)) = n.

A011540(a(n)) <= n, for n >= 0.

A011540(a(n)) = n, iff n is a zero-containing number.

a(10*n + k) <= 9*a(n) + n - 8, k = 0..9, equality holds for k = 9, and also, if n is a zerofree number (i.e., contains no '0'-digit).

a(10*A052382(n) + k) = 10*A052382(n) + 1 - 9*n, k = 0..9.

Values for special indices:

a(k*(10^n-1)/9 - j) = k*(8*10^n - 9*9^n + 1)/72 + 1, n > 0, k = 1..9, j = 0..k.

a(k*10^n - j) = k*(10^n - 9^n) + 1 - (9^n - 1)/8, n >= 0, k = 1..10, j = 1..10.

a(10^n) = 10^n + 2 - (9^(n+1) - 1)/8, n > 0.

a(k*10^n + j) = k*(10^n - 9^n) + j + 2 - (9^n - 1)/8, n > 0, k = 1..9, 0 <= j < (10^(n+1)-1)/9 - 10^n.

With: d := log_10(9) = 0.95424250943932...

Upper bound:

a(n) <= n + 2 - ((9*n + 10)^d - 1)/8,

equality holds for n = (10^k - 1)/9 - 1, k > 0.

Lower bound:

a(n) >= n + 2 - (9*(n + 1)^d - 1)/8,

equality holds for n = 10^k - 1, k >= 0.

Asymptotic behavior:

a(n) <= n + 2 + (1/8) - (9^d/8)*n^d*(1 + O(1/n)).

a(n) >= n + 2 + (1/8) - (9/8)*n^d*(1 + O(1/n))).

a(n) = n*(1 + O(n^(d-1)) = n*(1 + O(1/n^0.045757490...)).

Lower and upper limits:

lim inf (a(n) - n)/n^d = -9/8, for n -> infinity.

lim sup (a(n) - n)/n^d = -9^d/8 = -1.0173931195971..., for n -> infinity.

From Hieronymus Fischer, Apr 04 2019: (Start)

Formulas for general bases b > 2:

With m := floor(log_b(n)); k := Max_{j | j=1..m and (floor(n/b^j) mod b)*j = 0} = digit position of the leftmost '0' in n counted from the right (starting with 0), k = 0 if there is no '0' digit; b(n,k):= floor(n/b^k)*b^k:

a(n) = 2 + Sum_{j=1..m} floor((b(n,k+1)-1)/b^j)*(b-1)^(j-1), if k = 0, valid for n > b-1;

a(n) = 2 + n mod b^k + Sum_{j=1..m} floor((b(n,k)-1)/b^j)*(b-1)^(j-1), if k > 0, valid for n > 0;

a(n) = 2 + n mod b^k - ceiling(fract(n/b))*(1-ceiling(k/(m+1))) + Sum_{j=1..m} floor((b(n,k)-1)/b^j)* (b-1)^(j-1), all k, valid for n > 0.

Formula for base b = 2: a(n) = (n + 1 - floor(log_2(n + 1))).

With d := d(b) := log(b - 1)/log(b):

Upper bound (b = 10 for this sequence):

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

equality holds for n = (b^k - 1)/(b - 1) - 1, k > 0.

Lower bound (b = 10 for this sequence):

a(n) >= n + 2 - ((b - 1)*(n + 1)^d - 1)/(b - 2),

equality holds for n = b^k - 1, k >= 0.

Asymptotic behavior (b = 10 for this sequence):

a(n) = n*(1 + O(n^(d(b)-1)), for b > 2,

a(n) = n*(1 + O(log(n)/n)), for b = 2.

Lower and upper limits:

lim inf (a(n) - n)/n^d(b) = -(b - 1)/(b - 2), for n -> infinity, for b > 2.

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

In case of b = 2:

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

(End)