|
%I #41 Apr 26 2019 03:05:06
%S 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,
%T 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,
%U 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
%N Number of zero-containing nonnegative integers <= n.
%C This sequence represents the counting function of A011540.
%C 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.
%C 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.
%H Hieronymus Fischer, <a href="/A324160/b324160.txt">Table of n, a(n) for n = 0..10000</a>
%F 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:
%F 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),
%F 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),
%F 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).
%F a(n) + A324161(n) = n + 1
%F a(A011540(n)) = n.
%F A011540(a(n)) <= n, for n >= 0.
%F A011540(a(n)) = n, iff n is a zero-containing number.
%F 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).
%F a(10*A052382(n) + k) = 10*A052382(n) + 1 - 9*n, k = 0..9.
%F Values for special indices:
%F 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.
%F a(k*10^n - j) = k*(10^n - 9^n) + 1 - (9^n - 1)/8, n >= 0, k = 1..10, j = 1..10.
%F a(10^n) = 10^n + 2 - (9^(n+1) - 1)/8, n > 0.
%F 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.
%F With: d := log_10(9) = 0.95424250943932...
%F Upper bound:
%F a(n) <= n + 2 - ((9*n + 10)^d - 1)/8,
%F equality holds for n = (10^k - 1)/9 - 1, k > 0.
%F Lower bound:
%F a(n) >= n + 2 - (9*(n + 1)^d - 1)/8,
%F equality holds for n = 10^k - 1, k >= 0.
%F Asymptotic behavior:
%F a(n) <= n + 2 + (1/8) - (9^d/8)*n^d*(1 + O(1/n)).
%F a(n) >= n + 2 + (1/8) - (9/8)*n^d*(1 + O(1/n))).
%F a(n) = n*(1 + O(n^(d-1)) = n*(1 + O(1/n^0.045757490...)).
%F Lower and upper limits:
%F lim inf (a(n) - n)/n^d = -9/8, for n -> infinity.
%F lim sup (a(n) - n)/n^d = -9^d/8 = -1.0173931195971..., for n -> infinity.
%F From _Hieronymus Fischer_, Apr 04 2019: (Start)
%F Formulas for general bases b > 2:
%F 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:
%F 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;
%F 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;
%F 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.
%F Formula for base b = 2: a(n) = (n + 1 - floor(log_2(n + 1))).
%F With d := d(b) := log(b - 1)/log(b):
%F Upper bound (b = 10 for this sequence):
%F a(n) <= n + 2 - (((b - 1)*n + b)^d - 1)/(b - 2),
%F equality holds for n = (b^k - 1)/(b - 1) - 1, k > 0.
%F Lower bound (b = 10 for this sequence):
%F a(n) >= n + 2 - ((b - 1)*(n + 1)^d - 1)/(b - 2),
%F equality holds for n = b^k - 1, k >= 0.
%F Asymptotic behavior (b = 10 for this sequence):
%F a(n) = n*(1 + O(n^(d(b)-1)), for b > 2,
%F a(n) = n*(1 + O(log(n)/n)), for b = 2.
%F Lower and upper limits:
%F lim inf (a(n) - n)/n^d(b) = -(b - 1)/(b - 2), for n -> infinity, for b > 2.
%F lim sup (a(n) - n)/n^d(b) = -(b - 1)^d/(b - 2) for n -> infinity, for b > 2.
%F In case of b = 2:
%F lim (a(n) - n)/log(n) = -1/log(2), for n -> infinity.
%F (End)
%e a(10) = 2, since there are two numbers <= 10 which contain a '0'-digit (0 and 10).
%e a(100) = 11.
%e a(10^3) = 182.
%e a(10^4) = 2621.
%e a(10^5) = 33572.
%e a(10^6) = 402131.
%e a(10^7) = 4619162
%e a(10^8) = 51572441.
%e a(10^9) = 564151952.
%e a(10^10) = 6077367551.
%e a(10^20) = 86322626358560955101.
%e a(10^50) = 99420200289176487252583981229013676068210129037751 = 9.9420200289176... *10^49
%e a(10^100) = 9.9997011842625...13575501*10^99.
%e a(10^1000) = 9.999999999999...564125755001*10^999
%e (here, the first 45 digits are 9's).
%o (PARI) a(n) = 1 + sum(k=1, n, vecmin(digits(k)) == 0); \\ _Michel Marcus_, Mar 20 2019
%Y Cf. A011540, A052382, A324161, A217094.
%K nonn,base
%O 0,11
%A _Hieronymus Fischer_, Feb 15 2019
|
