OFFSET
0,11
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.
LINKS
Hieronymus Fischer, Table of n, a(n) for n = 0..10000
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).
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)
EXAMPLE
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).
PROG
(PARI) a(n) = 1 + sum(k=1, n, vecmin(digits(k)) == 0); \\ Michel Marcus, Mar 20 2019
CROSSREFS
KEYWORD
nonn,base
AUTHOR
Hieronymus Fischer, Feb 15 2019
STATUS
approved