|
| |
|
|
A324161
|
|
Number of zerofree nonnegative integers <= n.
|
|
12
|
|
|
|
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 81, 82, 83
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,3
|
|
|
COMMENTS
|
This sequence represents the counting function of A052382 (for indices > 0). The offset is set to zero for compatibility with A324160.
For indices 1 < n < 10761677 we have a(n) > A324160(n), for all indices n > 20327615 we have a(n) < A324160(n), i.e., the number of zerofree numbers <= N is smaller than the number of zero containing numbers <= N for sufficiently large N.
There are exactly 20 indices for which a(n) = A324160(n).
The greatest number n = n_max such that a(n) >= pi(n) [the number of primes <= n] is in the range 1.0075615552421*10^45 < n_max < 1.0075622026833*10^45 (see A324155). Thus, for all indices n > n_max, we have a(n) < pi(n). For n = n_max the number of primes is pi(n) = 9818959014098676479127822164411318257546629.
The least number n = n_min such that a(n) <= pi(n) [the number of primes <= n] is in the range 1.0953002073198*10^44 < n_min < 1.0953009588121*10^44 (see A324154). Thus, for all indices n < n_min, we have a(n) > pi(n). For n = n_min the number of primes is pi(n) = 1090995446010964053236424684934590917505180.
|
|
|
LINKS
|
|
|
|
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) = n - 1 - Sum_{j=1..m} floor((b(n,k+1)-1)/10^j)*9^(j-1), if k = 0 (valid for n > 9),
a(n) = b(n,k) - 1 - Sum_{j=1..m} floor((b(n,k)-1)/10^j)*9^(j-1), if k > 0 (valid for n > 0),
a(n) = b(n,k) - 1 + 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).
A052382(a(n)) = n, iff n is a zerofree number.
a(10*n + k) >= 9*a(n) + k, k=0..9, equality holds, if n is a zerofree number (i.e., contains no '0'-digit).
a(10*A052382(n) + k) = 9*n + k, k=0..9, n > 0.
Values for special indices:
a(k*(10^n - 1)/9 - j) = k*(9^n - 1)/8 - j, n > 0, k = 1, 2, ... 9, j = 0, 1, 2, ... k.
a(k*10^n - j) = k*9^n + (9^n - 1)/8 - j, n >= 0, k = 1, 2, ... 10, j = 1, 2, ... 10.
a(k*10^n + j) = k*9^n + (9^n - 1)/8 - 1, n > 0, k = 1, 2, ... 10, j = 0, 1, 2, ... (10^(n+1)-1)/9 - 10^n - 1.
With: d := log_10(9) = 0.95424250943932...
Upper bound:
a(n) <= (9*(n+1)^d - 1)/8 - 1,
equality holds for n = 10^k - 1, k >= 0.
Lower bound:
a(n) >= ((9*n + 10)^d - 1)/8 - 1,
equality holds for n = (10^k - 1)/9 - 1, k > 0.
Asymptotic behavior:
a(n) <= (9/8)*n^d*(1 + O(1/n)) - 9/8.
a(n) >= (9^d/8)*n^d*(1 + O(1/n)) - 9/8.
a(n) = O(n^d) = O(n^0.954242509...).
Lower and upper limits:
lim inf a(n)/n^d = 9^d/8 = 1.0173931195971..., for n -> infinity.
lim sup a(n)/n^d = 9/8, for n -> infinity.
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) = n - 1 - 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) = b(n,k) - 1 - Sum_{j=1..m} floor((b(n,k)-1)/b^j)*(b-1)^(j-1), if k > 0, valid for n > 0;
a(n) = b(n,k) - 1 + 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) = floor(log_2(n + 1)).
With d := d(b) := log(b - 1)/log(b).
Upper bound (b = 10 for this sequence):
a(n) <= ((b - 1)*(n + 1)^d - 1)/(b - 2) - 1,
equality holds for n = b^k - 1, k >= 0.
Lower bound (b = 10 for this sequence):
a(n) >= (((b - 1)*n + b)^d - 1)/(b - 2) - 1,
equality holds for n = (b^k - 1)/(b - 1) - 1, k > 0.
Asymptotic behavior (b = 10 for this sequence):
a(n) = O(n^d(b)), for b > 2,
a(n) = O(log(n)), for b = 2.
Lower and upper limits:
lim inf a(n)/n^d = (b - 1)^d/(b - 2), for n -> infinity, for b > 2.
lim sup a(n)/n^d = (b - 1)/(b - 2), for n -> infinity, for b > 2.
In case of b = 2:
lim a(n)/log(n) = 1/log(2), for n -> infinity.
(End)
|
|
|
EXAMPLE
|
a(10) = 9, since there are 9 numbers <= 10 which contain no '0'-digit (1, 2, 3, 4, 5, 6, 7, 8 and 9).
a(100) = 90.
a(10^3) = 819.
a(10^4) = 7380.
a(10^5) = 66429.
a(10^6) = 597870.
a(10^7) = 5380839
a(10^8) = 48427560.
a(10^9) = 435848049.
a(10^10) = 3922632450.
a(10^20) = 13677373641439044900.
a(10^50) = 579799710823512747416018770986323931789870962250 = 5.79799...*10^47.
a(10^100) = 2.9881573748536...68682786424500*10^95.
a(10^1000) = 1.96635515818798306...435874245000*10^954.
|
|
|
MAPLE
|
option remember;
if n = 0 then
0;
else
convert(convert(n, base, 10), set) ;
if 0 in % then
procname(n-1) ;
else
1+procname(n-1) ;
end if;
end if;
|
|
|
PROG
|
(PARI) a(n) = sum(k=1, n, vecmin(digits(k)) != 0); \\ Michel Marcus, Mar 20 2019
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,base
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
