|
%I #139 Sep 08 2022 08:44:37
%S 0,10,20,30,40,50,60,70,80,90,100,101,102,103,104,105,106,107,108,109,
%T 110,120,130,140,150,160,170,180,190,200,201,202,203,204,205,206,207,
%U 208,209,210,220,230,240,250,260,270,280,290,300,301,302
%N Numbers that contain a digit 0.
%C Complement of A052382.
%C A168046(a(n)) = 0; A054054(a(n)) = 0; A055640(a(n)) = 0 for n = 1 and A055640(a(n)) > 0 for n > 1; A055641(a(n)) > 0; subsequence of A188643. - _Reinhard Zumkeller_, Apr 25 2012, Apr 07 2011; corrected by _Hieronymus Fischer_, Jan 13 2013
%C A067898(a(n)) > 0. - _Reinhard Zumkeller_, May 04 2012; corrected by _Hieronymus Fischer_, Jan 13 2013
%C From _Hieronymus Fischer_, Jan 13 2013, May 28 2014; edited by _M. F. Hasler_; edited by _Hieronymus Fischer_, Dec 27 2018: (Start)
%C Zerofree floor: The greatest zerofree number < a(n) is A052382(a(n) + 1 - n).
%C The greatest zero-containing number (i.e., non-zerofree number, or term of this sequence) less than a given zerofree number A052382(n) is a(A052382(n) + 1 - n).
%C The ratio n/(a(n) + 1) indicates the relative proportion of zero-containing numbers less than or equal to a(n) compared to all numbers less than or equal to a(n). Since Lim_{n -> infinity} a(n)/n = 1, this can be expressed as "Almost all numbers contain a 0" (in a slightly informal manner).
%C As an example, for n = 10^100, n/(a(n) + 1) = 0.9999701184..., i.e., 99.997...% of all numbers between 0 and 10^100 contain a zero digit. Only the tiny proportion of 0.0000298816... (less than 0.003%) contain no zero digit. This is in contrast to the behavior for small indices, where the relative portion of numbers that contain no zero digit is significant: for n = 10^3 and even n = 10^7, the proportion of numbers less than or equal to n that contain no zero digit exceeds 81% and 53%, respectively.
%C Inversion: Given a number z that contains a zero digit, the index n for which a(n) = z is n = (z+1)*probability that a randomly chosen number k from the range 0..z contains a zero digit.
%C Example 1: z = 10; the probability that a randomly chosen number less than or equal to 10 contains no zero digit is 9/11. The probability that it contains a zero digit is p = 2/11. Thus, n = (z+1)*p = 2 and a(2) = 10.
%C Example 2: z = 10^6; the probability that a randomly chosen number with m > 1 digits contains no zero digit is (9/10)^(m-1). For m = 1 the probability is 9/10. The probability that a randomly chosen number with 1..m digits contains no zero digit is q = (9/10)*10/(10^m+1) + Sum_{i = 2..m} (9/10)^(i-1)*(10^i - 10^(i-1))/(10^m+1) = (72 + 81*(9^(m-1) - 1)/(8*(10^m+1)). Hence, the probability that the chosen number with 1..m digits contains a zero digit is p = 1 - q = (8*10^m - 9*9^m + 17)/(8*(10^m + 1)). Thus, p = 402131/1000001 (for z = 10^6) and so n = (z+1)*p = 402131, which implies a(402131) = 10^6.
%C The number of terms z such that k*10^m <= z < (k+1)*10^m is 10^m - 9^m, where 1 <= k < 10 and m >= 0.
%C The number of terms z such that 10^m <= z < 10^(m+1) is 9*(10^m - 9^m), where m >= 0.
%C The number of terms z <= 10^m is (8*10^m - 9*9^m + 17)/8 where m>=1 (cf. A217094).
%C Infinitely many terms are primes, and most primes are zero-containing numbers. Sketch of a proof: The number of zero-containing numbers less than or equal to a(n) is n. Hence there are a(n) + 1 - n zerofree numbers less than or equal to a(n). From the asymptotic behavior of a(n) (see formula section) it follows a(n) + 1 - n < (5/4)*n^log_10(9) for sufficiently large n. By the prime number theorem we have for each fixed d > 0 the relation pi(n) [number of primes less than or equal to n] > (1 - d/4)*(n/log(n)) for sufficiently large n. Thus, for the number of primes less than or equal to a(n) which contain a zero digit [hereafter denoted as P_0(a(n))] we have P_0(a(n)) > pi(a(n)) - (a(n) + 1 - n) > (1 - d/4)*a(n)/log(a(n)) - (5/4)*n^log_10(9) > (1-d/4)*n/log(n) - (5/4)*n^log_10(9) = (1-d/4)*n/log(n) * (1 - (5/4)*(1/(1-d/4))*(1/n) * n^(log_10(9))*log(n)) > (1-d/2)*n/log(n) for sufficiently large n. Because of a(n) = n + o(n) this also implies P_0(a(n)) > (1 - d)*a(n)/log(a(n)) for sufficiently large n. Thus, the proportion of primes less than or equal to a(n) which contain a zero digit compared to the total number of primes less than or equal to a(n) is arbitrarily near to 1 for sufficiently large n.
%C Sequence inversion:
%C Given a term m > 0, the index n such that a(n) = m can be calculated with the following procedure: Define k := floor(log_10(m)) and i := digit position of the leftmost '0' in m counted from the right (starting with 0), then:
%C A011540_inverse(m) = 2 + m mod 10^i + Sum_{j = 1..k} floor((m - 1 - m mod 10^i)/10^j)*9^(j-1) [see PROG section for an implementation in Smalltalk].
%C Example: m = 905, k = 2, i = 1, A011540_inverse(905) = 2 + 905 mod 10 + floor((905 - 1 - 905 mod 10)/10)*1 + floor((905 - 1 - 905 mod 10)/100)*9 = 2 + 5 + floor(899/10)*1 + floor(899/100)*9 = 2 + 5 + 89*1 + 8*9 = 168.
%C (End)
%C For the number of k-digit numbers containing the digit '0', see A229127. - _Jon E. Schoenfield_, Sep 14 2013
%C The above "sketch of proof" only compares the relative densities, and since the density of this sequence is 1, the result is "obvious". But the nontrivial part is that there is no correlation between the absence of a digit '0' and primality of the number (cf. A038618). Indeed, consider the set S defined to be the set of primes with all digits '0' replaced by the smallest possible nonzero digit while avoiding duplicates. Having exactly the same density as the set of primes, the argument of the proof applies in the same way and leads to the same conclusion for the number of zero-containing terms; however, there is none in the set S. - _M. F. Hasler_, Oct 11 2015, example added Feb 11 2019
%H Reinhard Zumkeller, <a href="/A011540/b011540.txt">Table of n, a(n) for n = 1..10000</a>
%H <a href="/index/Ar#10-automatic">Index entries for 10-automatic sequences</a>.
%F From _Hieronymus Fischer_, Jan 13 2013: (Start)
%F Inequalities:
%F a(n) <= 10*(n - 1), equality holds for 1 <= n <= 11.
%F a(n) <= 9*n, for n <> 11.
%F a(n) < n + 10 * n^log_10(9).
%F a(n) < n + 2 * n^log_10(9), for n > 6*10^8.
%F a(n) > n + 9^log_10(9)/8 * n^log_10(9).
%F a(n) < A043489(n), for n > 10.
%F Iterative calculation:
%F a(n+1) = a(n) + 1 + 9*sign(A007954(a(n)+1)).
%F Recursive calculation (for n > 1):
%F Set m := floor(log_10(n)) + 1), j := floor(sign(n+1 - (8*10^m - 9*9^m + 17)/8) + 1)/2) + m - 1, d := 10^j - 9^j, b := (8*10^j - 9*9^j + 17)/8, and determine r(n) as follows:
%F Case 1: r(n) = a(b - d + (n - b) mod d), if (n - b) mod d > 10^(j-1) and n >= 19
%F Case 2: r(n) = (n - b) mod d, if (n - b) mod d <= 10^(j-1).
%F Then a(n) = (floor((n - b)/d) + 1)*10^j + r(n).
%F Direct calculation (for n>1):
%F Set m := floor(log_10(n)) + 1), j := floor((sign(n+1 - (8*10^m - 9*9^m + 17)/8) + 1)/2) + m - 1, and determine k and c(i) as follows:
%F c(1) = n - (8*10^j - 9*9^j + 17)/8, then define successively for i = 1, 2, ...,
%F c(i+1) = (c(i) mod (10^(j-i+1) - 9^(j-i+1))) - 10^(j-i) while this value is > 0, and set k := i for the last such index for which c(i) > 0 (in any case k is k<=j).
%F Then a(n) = c(k) mod (10^(j-k+1) - 9^(j-k+1)) + sum_{i=1..k}(floor(c(i)/(10^(j-i+1) - 9^(j-i+1))) + 1)*10^(j-i+1).
%F Asymptotic behavior:
%F a(n) = n + O(n^log_10(9)) = n*(1+ O(1/n^0.04575749056...)).
%F lim a(n)/n = 1 for n -> infinity.
%F lim inf (a(n) - n)/n^log_10(9) = 9^log_10(9)/8 = 1.017393081085670008926619124438...
%F lim sup (a(n) - n)/n^log_10(9) = 9/8 = 1.125.
%F Sums:
%F Sum_{n >= 2} (-1)^n/a(n) = 0.0693489578....
%F Sum_{n >= 2} 1/a(n)^2 = 0.0179656962...
%F Sum_{n >= 2} 1/a(n) diverges, because of a(n) < 10*n.
%F Sum_{n >= 1} a(n)/n^2 diverges too.
%F Sum_{n >= 2} 1/a(n)^2 + Sum_{n >= 1} 1/A052382(n)^2 = Pi^2/6.
%F Generating function:
%F g(x) = Sum_{k >= 1} g_k(x), where the terms g_k(x) obey the following recurrence relation:
%F g_k(x) = 10^k*x^b(k) * (1 - 10x^(9d(k)) + 9x^(10d(k)))/((1-x^d(k))(1-x)) + (x*x^b(k) * (1 - 10^(k-1)*x^(10^(k-1)-1) + (10^(k-1)-1)*x^10^(k-1))/((1-x)^2) + g_(k-1)(x)*x^d(k)) * (1-x^(9d(k)))/(1-x^d(k)),
%F where b(k) := 2 + 10^k - 9^k - (9^k-1)/8,
%F d(k) := 10^k - 9^k, and g_0(x) = 0.
%F Explicit representation of g_k(x):
%F g_k(x) = (10^k*x^b(k)*(1 - 10x^(9d(k)) + 9x^(10d(k)))/(1-x^d(k)) + sum_{j=1..k-1} ((10^j*x^b(j) * (1 - 10x^(9d(j)) + 9x^(10d(j)))/(1-x^d(j)) + x^(b(j)-10^j+1) * (1 - 10^j*x^(10^j-1) + (10^j-1)*x^10^j)/(1-x)) * Product_{i=j+1..k} x^d(i)*(1-x^(9d(i)))/(1-x^d(i)))/(1-x).
%F A summation term g_k(x) of the g.f. represents all the sequence terms >= 10^k and < 10^(k+1).
%F Example 1: g_1(x) = 10*x^2*(1 - 10x^9 + 9x^10)/(1-x)^2 represents the g.f. fragment 10x^2 + 20x^3 + ... + 90x^10 and so generates the terms a(2)=10 ... a(10)=90.
%F Example 2: g_2(x) = 10^2*x^11*(1 - 10x^(9*19) + 9x^(10*19))/((1-x)(1-x^19)) + 10*x^21 * (1 - 10x^9 + 9x^10)/((1-x)^2) * (1-x^(9*19))/(1-x^19)) + x^11*x * (1 - 10x^9 + 9x^10)/((1-x)^2) * (1-x^(9*19))/(1-x^19) represents the g.f. fragment 100x^11 + 101x^12 + ... + 109x^20 + 110x^21 + 120x^22 + ... + 190x^29 + 200x^30 + 201x^31 + ... + 210x^40 + ... + 990x^181 and so generates the terms a(11) = 100 ... a(181) = 990.
%F (End)
%F From _Hieronymus Fischer_, Feb 12 2019: (Start)
%F The number C(n) of zero-containing numbers <= n (counting function) is given by C(n) = A011540_inverse(n), if n is a zero-containing number, and C(n) = A011540_inverse(A052382(a(n) + 1 - n)), if n is a zerofree number.
%F Upper bound:
%F C(n) <= n+1-((9*n+1)^d-1)/8.
%F Lower bound:
%F C(n) > n+1-((10*n+1)^d-1)/8
%F where d = log_10(9) = 0.95424250943932...
%F (see A324160).
%F (End)
%e a(10) = 90.
%e a(100) = 540.
%e a(10^3) = 4005.
%e a(10^4) = 30501.
%e a(10^5) = 253503.
%e a(10^6) = 2165031.
%e a(10^7) = 20163807
%e a(10^8) = 182915091.
%e a(10^9) = 1688534028.
%e a(10^10) = 15749319096.
%e a(10^20) = 114131439770460123393.
%e a(10^50) = 10057979971082351274741...89870962249 = 1.0057979971082...*10^50
%e a(10^100) = 10000298815737485...786424499 = 1.0000298815737...*10^100.
%e a(10^1000) = 1...(45 zeros)...196635515818798306...4244999 (1001 digits), using recursive calculation. - _Hieronymus Fischer_, Jan 13 2013
%t Select[Range[0, 299], DigitCount[#, 10, 0] > 0 &] (* _Alonso del Arte_, Mar 10 2011 *)
%t Select[Range[0, 299], Times@@IntegerDigits[#] == 0 &] (* _Alonso del Arte_, Aug 29 2014 *)
%o (Haskell)
%o a011540 n = a011540_list !! (n-1)
%o a011540_list = filter ((== 0) . a168046) [0..]
%o -- _Reinhard Zumkeller_, Apr 07 2011
%o (PARI) is(n)=!n||!vecmin(digits(n)) \\ _M. F. Hasler_, Feb 28 2018, replacing an earlier version from _Charles R Greathouse IV_, Aug 09 2011
%o (PARI) A011540(n)=my(m=log(n+.5)\log(10)+1, f(m)=n-10^m+(9*9^m-17)/8, j=(sign(f(m)+1)+1)\2+m-1, c=[f(j)], k=1); while(c[k]>0,c=concat(c,c[k] % (10^(j-k+1) - 9^(j-k+1)) - 10^(j-k));k++); k>1&&k--||n>1||return(0); c[k]%(10^(j-k+1) - 9^(j-k+1)) + sum(i=1,k, (c[i]\(10^(j-i+1) - 9^(j-i+1)) + 1)*10^(j-i+1)) \\ Uses the "Direct calculation" formula given by H. Fischer. - _M. F. Hasler_, Oct 11 2015
%o (Smalltalk)
%o A011540
%o "Calculates the n-th number with zero digits recursively - not optimized"
%o | n j m b d p r |
%o n := self.
%o n < 2 ifTrue: [^r := 0].
%o m := (n integerFloorLog: 10) + 1.
%o j := (n + 1 - ((10 raisedToInteger: m) - (((9 raisedToInteger: (m + 1)) - 17) // 8))) sign + 1 // 2 + m - 1.
%o d := (10 raisedToInteger: j) - (9 raisedToInteger: j).
%o b := ((10 raisedToInteger: j) - (((9 raisedToInteger: (j + 1)) - 17) // 8)).
%o (((n - b) \\ d > (10 raisedToInteger: (j - 1))) and: [n >= 19])
%o ifTrue:
%o [p := (((n - b) \\ d + b - d) A011540)].
%o (n - b) \\ d > (10 raisedToInteger: (j - 1))
%o ifFalse: [p := (n - b) \\ d].
%o r := (((n - b) // d + 1) * (10 raisedToInteger: j)) + p.
%o ^r "_Hieronymus Fischer_, Jan 13 2013"
%o (Smalltalk)
%o A011540_inverse
%o "Version 1: Answers the index n such that A011540(n) = m, where m is the receiver.
%o Usage: m A011540_inverse
%o Answer: n"
%o | m p q s r d |
%o m := self.
%o m < 10 ifTrue: [^1].
%o p := q := 1.
%o [p < m] whileTrue:
%o [d := m // p \\ 10.
%o d = 0 ifTrue: [q := p].
%o p := 10 * p].
%o r := m \\ q.
%o s := r + 2.
%o p := 10.
%o q := 1.
%o m := m - r - 1.
%o [p < m] whileTrue:
%o [s := m // p * q + s.
%o p := 10 * p.
%o q := 9 * q].
%o ^s
%o "_Hieronymus Fischer_, May 28 2014"
%o (Smalltalk)
%o A011540_inverse
%o "Version 2: Answers the index n such that A011540(n) = m, where m is the receiver.
%o Uses A052382_inverse from A052382.
%o Usage: m A011540_inverse
%o Answer: n"
%o | m p q d |
%o m := self.
%o m < 10 ifTrue: [^1].
%o p := q := 1.
%o [p < m] whileTrue:
%o [d := m // p \\ 10.
%o d = 0 ifTrue: [q := p].
%o p := 10 * p].
%o ^m + 1 - (m - 1 - (m \\ q)) A052382_inverse
%o "_Hieronymus Fischer_, May 28 2014"
%o (Magma) [0] cat [ n: n in [0..350] | 0 in Intseq(n) ]; // _Vincenzo Librandi_, Oct 12 2015
%o (Python)
%o A011540_list = [n for n in range(10**3) if '0' in str(n)] # _Chai Wah Wu_, Mar 26 2021
%Y A192825 is a subsequence.
%Y Cf. A007954, A043489, A052382, A055641, A168046, A217094, A217096, A229127.
%K nonn,base,easy,look
%O 1,2
%A _N. J. A. Sloane_
%E Edited by _M. F. Hasler_, Oct 11 2015
| 