cp's OEIS Frontend

A011540 Numbers that contain a digit 0.

%I A011540 #143 Apr 17 2025 01:55:16
%S A011540 0,10,20,30,40,50,60,70,80,90,100,101,102,103,104,105,106,107,108,109,
%T A011540 110,120,130,140,150,160,170,180,190,200,201,202,203,204,205,206,207,
%U A011540 208,209,210,220,230,240,250,260,270,280,290,300,301,302
%N A011540 Numbers that contain a digit 0.
%C A011540 Complement of A052382.
%C A011540 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 A011540 A067898(a(n)) > 0. - _Reinhard Zumkeller_, May 04 2012; corrected by _Hieronymus Fischer_, Jan 13 2013
%C A011540 From _Hieronymus Fischer_, Jan 13 2013, May 28 2014; edited by _M. F. Hasler_; edited by _Hieronymus Fischer_, Dec 27 2018: (Start)
%C A011540 Zerofree floor: The greatest zerofree number < a(n) is A052382(a(n) + 1 - n).
%C A011540 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 A011540 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 A011540 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 A011540 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 A011540 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 A011540 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 A011540 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 A011540 The number of terms z such that 10^m <= z < 10^(m+1) is 9*(10^m - 9^m), where m >= 0.
%C A011540 The number of terms z <= 10^m is (8*10^m - 9*9^m + 17)/8 where m>=1 (cf. A217094).
%C A011540 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 A011540 Sequence inversion:
%C A011540 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 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 A011540 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 A011540 (End)
%C A011540 For the number of k-digit numbers containing the digit '0', see A229127. - _Jon E. Schoenfield_, Sep 14 2013
%C A011540 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 A011540 Reinhard Zumkeller, <a href="/A011540/b011540.txt">Table of n, a(n) for n = 1..10000</a>
%H A011540 <a href="/index/Ar#10-automatic">Index entries for 10-automatic sequences</a>.
%F A011540 From _Hieronymus Fischer_, Jan 13 2013: (Start)
%F A011540 Inequalities:
%F A011540 a(n) <= 10*(n - 1), equality holds for 1 <= n <= 11.
%F A011540 a(n) <= 9*n, for n <> 11.
%F A011540 a(n) < n + 10 * n^log_10(9).
%F A011540 a(n) < n + 2 * n^log_10(9), for n > 6*10^8.
%F A011540 a(n) > n + 9^log_10(9)/8 * n^log_10(9).
%F A011540 a(n) < A043489(n), for n > 10.
%F A011540 Iterative calculation:
%F A011540 a(n+1) = a(n) + 1 + 9*sign(A007954(a(n)+1)).
%F A011540 Recursive calculation (for n > 1):
%F A011540 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 A011540 Case 1: r(n) = a(b - d + (n - b) mod d), if (n - b) mod d > 10^(j-1) and n >= 19
%F A011540 Case 2: r(n) = (n - b) mod d, if (n - b) mod d <= 10^(j-1).
%F A011540 Then a(n) = (floor((n - b)/d) + 1)*10^j + r(n).
%F A011540 Direct calculation (for n>1):
%F A011540 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 A011540 c(1) = n - (8*10^j - 9*9^j + 17)/8, then define successively for i = 1, 2, ...,
%F A011540 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 A011540 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 A011540 Asymptotic behavior:
%F A011540 a(n) = n + O(n^log_10(9)) = n*(1+ O(1/n^0.04575749056...)).
%F A011540 lim a(n)/n = 1 for n -> infinity.
%F A011540 lim inf (a(n) - n)/n^log_10(9) = 9^log_10(9)/8 = 1.017393081085670008926619124438...
%F A011540 lim sup (a(n) - n)/n^log_10(9) = 9/8 = 1.125.
%F A011540 Sums:
%F A011540 Sum_{n >= 2} (-1)^n/a(n) = 0.0693489578....
%F A011540 Sum_{n >= 2} 1/a(n)^2 = 0.0179656962...
%F A011540 Sum_{n >= 2} 1/a(n) diverges, because of a(n) < 10*n.
%F A011540 Sum_{n >= 1} a(n)/n^2 diverges too.
%F A011540 Sum_{n >= 2} 1/a(n)^2 + Sum_{n >= 1} 1/A052382(n)^2 = Pi^2/6.
%F A011540 Generating function:
%F A011540 g(x) = Sum_{k >= 1} g_k(x), where the terms g_k(x) obey the following recurrence relation:
%F A011540 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 A011540 where b(k) := 2 + 10^k - 9^k - (9^k-1)/8,
%F A011540 d(k) := 10^k - 9^k, and g_0(x) = 0.
%F A011540 Explicit representation of g_k(x):
%F A011540 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 A011540 A summation term g_k(x) of the g.f. represents all the sequence terms >= 10^k and < 10^(k+1).
%F A011540 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 A011540 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 A011540 (End)
%F A011540 From _Hieronymus Fischer_, Feb 12 2019: (Start)
%F A011540 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 A011540 Upper bound:
%F A011540   C(n) <= n+1-((9*n+1)^d-1)/8.
%F A011540 Lower bound:
%F A011540   C(n) > n+1-((10*n+1)^d-1)/8
%F A011540 where d = log_10(9) = 0.95424250943932...
%F A011540 (see A324160).
%F A011540 (End)
%e A011540 a(10)      = 90.
%e A011540 a(100)     = 540.
%e A011540 a(10^3)    = 4005.
%e A011540 a(10^4)    = 30501.
%e A011540 a(10^5)    = 253503.
%e A011540 a(10^6)    = 2165031.
%e A011540 a(10^7)    = 20163807
%e A011540 a(10^8)    = 182915091.
%e A011540 a(10^9)    = 1688534028.
%e A011540 a(10^10)   = 15749319096.
%e A011540 a(10^20)   = 114131439770460123393.
%e A011540 a(10^50)   = 10057979971082351274741...89870962249 = 1.0057979971082...*10^50
%e A011540 a(10^100)  = 10000298815737485...786424499 = 1.0000298815737...*10^100.
%e A011540 a(10^1000) = 1...(45 zeros)...196635515818798306...4244999 (1001 digits), using recursive calculation. - _Hieronymus Fischer_, Jan 13 2013
%t A011540 Select[Range[0, 299], DigitCount[#, 10, 0] > 0 &] (* _Alonso del Arte_, Mar 10 2011 *)
%t A011540 Select[Range[0, 299], Times@@IntegerDigits[#] == 0 &] (* _Alonso del Arte_, Aug 29 2014 *)
%o A011540 (Haskell)
%o A011540 a011540 n = a011540_list !! (n-1)
%o A011540 a011540_list = filter ((== 0) . a168046) [0..]
%o A011540 -- _Reinhard Zumkeller_, Apr 07 2011
%o A011540 (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 A011540 (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 A011540 (Smalltalk)
%o A011540 A011540
%o A011540 "Calculates the n-th number with zero digits recursively - not optimized"
%o A011540 | n j m b d p r |
%o A011540 n := self.
%o A011540 n < 2 ifTrue: [^r := 0].
%o A011540 m := (n integerFloorLog: 10) + 1.
%o A011540 j := (n + 1 - ((10 raisedToInteger: m) - (((9 raisedToInteger: (m + 1)) - 17) // 8))) sign + 1 // 2 + m - 1.
%o A011540 d := (10 raisedToInteger: j) - (9 raisedToInteger: j).
%o A011540 b := ((10 raisedToInteger: j) - (((9 raisedToInteger: (j + 1)) - 17) // 8)).
%o A011540 (((n - b) \\ d > (10 raisedToInteger: (j - 1))) and: [n >= 19])
%o A011540 ifTrue:
%o A011540 [p := (((n - b) \\ d + b - d) A011540)].
%o A011540 (n - b) \\ d > (10 raisedToInteger: (j - 1))
%o A011540 ifFalse: [p := (n - b) \\ d].
%o A011540 r := (((n - b) // d + 1) * (10 raisedToInteger: j)) + p.
%o A011540 ^r "_Hieronymus Fischer_, Jan 13 2013"
%o A011540 (Smalltalk)
%o A011540 A011540_inverse
%o A011540 "Version 1: Answers the index n such that A011540(n) = m, where m is the receiver.
%o A011540 Usage: m A011540_inverse
%o A011540 Answer: n"
%o A011540 | m p q s r d |
%o A011540 m := self.
%o A011540 m < 10 ifTrue: [^1].
%o A011540 p := q := 1.
%o A011540 [p < m] whileTrue:
%o A011540 [d := m // p \\ 10.
%o A011540 d = 0 ifTrue: [q := p].
%o A011540 p := 10 * p].
%o A011540 r := m \\ q.
%o A011540 s := r + 2.
%o A011540 p := 10.
%o A011540 q := 1.
%o A011540 m := m - r - 1.
%o A011540 [p < m] whileTrue:
%o A011540 [s := m // p * q + s.
%o A011540 p := 10 * p.
%o A011540 q := 9 * q].
%o A011540 ^s
%o A011540 "_Hieronymus Fischer_, May 28 2014"
%o A011540 (Smalltalk)
%o A011540 A011540_inverse
%o A011540 "Version 2: Answers the index n such that A011540(n) = m, where m is the receiver.
%o A011540 Uses A052382_inverse from A052382.
%o A011540 Usage: m A011540_inverse
%o A011540 Answer: n"
%o A011540 | m p q d |
%o A011540 m := self.
%o A011540 m < 10 ifTrue: [^1].
%o A011540 p := q := 1.
%o A011540 [p < m] whileTrue:
%o A011540 [d := m // p \\ 10.
%o A011540 d = 0 ifTrue: [q := p].
%o A011540 p := 10 * p].
%o A011540 ^m + 1 - (m - 1 - (m \\ q)) A052382_inverse
%o A011540 "_Hieronymus Fischer_, May 28 2014"
%o A011540 (Magma) [0] cat [ n: n in [0..350] | 0 in Intseq(n) ]; // _Vincenzo Librandi_, Oct 12 2015
%o A011540 (Python)
%o A011540 A011540_list = [n for n in range(10**3) if '0' in str(n)] # _Chai Wah Wu_, Mar 26 2021
%Y A011540 A192825 is a subsequence.
%Y A011540 Cf. A007954, A043489, A052382, A055641, A168046, A217094, A217096, A229127.
%K A011540 nonn,base,easy,look
%O A011540 1,2
%A A011540 _N. J. A. Sloane_
%E A011540 Edited by _M. F. Hasler_, Oct 11 2015