login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A011540 Numbers that contain a digit 0. 74
0, 10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 120, 130, 140, 150, 160, 170, 180, 190, 200, 201, 202, 203, 204, 205, 206, 207, 208, 209, 210, 220, 230, 240, 250, 260, 270, 280, 290, 300, 301, 302 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

Complement of A052382.

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

A067898(a(n)) > 0. - Reinhard Zumkeller, May 04 2012; corrected by Hieronymus Fischer, Jan 13 2013

From Hieronymus Fischer, Jan 13 2013, May 28 2014; edited by M. F. Hasler: (Start)

Zerofree floor: The greatest zerofree number < a(n) is A052382(a(n) + 1 - n).

The minimal zero number (i.e., non-zerofree number, or term of this sequence) larger than a given zerofree number A052382(n) is a(A052382(n) + 1 - n).

The ratio n/(a(n) + 1) indicates the relative proportion of zero 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).

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.

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.

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.

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.

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.

The number of terms z such that 10^m <= z < 10^(m+1) is 9*(10^m - 9^m), where m >= 0.

The number of terms z <= 10^m is (8*10^m - 9*9^m + 17)/8 where m>=1 (cf. A217094).

Infinitely many terms are primes, and most primes are zero numbers. Sketch of a proof: The number of zero 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, the number of primes less than or equal to a(n) which contain a zero digit is 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.

Sequence inversion:

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:

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].

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.

(End)

For the number of k-digit numbers containing the digit '0', see A229127. - Jon E. Schoenfield, Sep 14 2013

The above "sketch of proof" that most primes are "zero numbers" is flawed. It 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. (One could imagine that numbers with a '0' digit are less likely to be prime, as is the case for numbers that end in an even digit.) - M. F. Hasler, Oct 11 2015

LINKS

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000

Index entries for 10-automatic sequences.

FORMULA

From Hieronymus Fischer, Jan 13 2013: (Start)

Inequalities:

a(n) <= 10*(n - 1), equality holds for 1 <= n <= 11.

a(n) <= 9*n, for n <> 11.

a(n) < n + 10 * n^log_10(9).

a(n) < n + 2 * n^log_10(9), for n > 6*10^8.

a(n) > n + 9^log_10(9)/8 * n^log_10(9).

a(n) < A043489(n), for n > 10.

Iterative calculation:

a(n+1) = a(n) + 1 + 9*sign(A007954(a(n)+1)).

Recursive calculation (for n > 1):

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:

Case 1: r(n) = a(b - d + (n - b) mod d), if (n - b) mod d > 10^(j-1) and n >= 19

Case 2: r(n) = (n - b) mod d, if (n - b) mod d <= 10^(j-1).

Then a(n) = (floor((n - b)/d) + 1)*10^j + r(n).

Direct calculation (for n>1):

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:

c(1) = n - (8*10^j - 9*9^j + 17)/8, then define successively for i = 1, 2, ...,

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).

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).

Asymptotic behavior:

a(n) = n + O(n^log_10(9)) = n + n^0.95424250943932....

lim a(n)/n = 1 for n -> infinity.

lim inf (a(n) - n)/n^log_10(9) = 9^log_10(9)/8 = 1.017393081085670008926619124438...

lim sup (a(n) - n)/n^log_10(9) = 9/8 = 1.125.

Sums:

Sum_{n >= 2} (-1)^n/a(n) = 0.0693489578....

Sum_{n >= 2} 1/a(n)^2 = 0.0179656962...

Sum_{n >= 2} 1/a(n) diverges, because of a(n) < 10*n.

Sum_{n >= 1} a(n)/n^2 diverges too.

Sum_{n >= 2} 1/a(n)^2 + Sum_{n >= 1} 1/A052382(n)^2 = Pi^2/6.

Generating function:

g(x) = sum_{k >= 1} g_k(x), where the terms g_k(x) obey the following recurrence relation:

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)),

where b(k) := 2 + 10^k - 9^k - (9^k-1)/8,

d(k) := 10^k - 9^k, and g_0(x) = 0.

Explicit representation of g_k(x):

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).

A summation term g_k(x) of the g.f. represents all the sequence terms >= 10^k and < 10^(k+1).

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.

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.

(End)

EXAMPLE

a(10)      = 90.

a(100)     = 540.

a(10^3)    = 4005.

a(10^4)    = 30501.

a(10^5)    = 253503.

a(10^6)    = 2165031.

a(10^7)    = 20163807

a(10^8)    = 182915091.

a(10^9)    = 1688534028.

a(10^10)   = 15749319096.

a(10^20)   = 114131439770460123393.

a(10^50)   = 10057979971082351274741...89870962249 = 1.0057979971082...*10^50

a(10^100)  = 10000298815737485...786424499 = 1.0000298815737...*10^100.

a(10^1000) = 1...(45 zeros)...196635515818798306...4244999 (1001 digits), using recursive calculation. - Hieronymus Fischer, Jan 13 2013

MATHEMATICA

Select[Range[0, 299], DigitCount[#, 10, 0] > 0 &] (* Alonso del Arte, Mar 10 2011 *)

Select[Range[0, 299], Times@@IntegerDigits[#] == 0 &] (* Alonso del Arte, Aug 29 2014 *)

PROG

(Haskell)

a011540 n = a011540_list !! (n-1)

a011540_list = filter ((== 0) . a168046) [0..]

-- Reinhard Zumkeller, Apr 07 2011

(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

(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)) \\ M. F. Hasler, Oct 11 2015

(Smalltalk)

A011540

"Calculates the n-th number with zero digits recursively - not optimized"

| n j m b d p r |

n := self.

n < 2 ifTrue: [^r := 0].

m := (n integerFloorLog: 10) + 1.

j := (n + 1 - ((10 raisedToInteger: m) - (((9 raisedToInteger: (m + 1)) - 17) // 8))) sign + 1 // 2 + m - 1.

d := (10 raisedToInteger: j) - (9 raisedToInteger: j).

b := ((10 raisedToInteger: j) - (((9 raisedToInteger: (j + 1)) - 17) // 8)).

(((n - b) \\ d > (10 raisedToInteger: (j - 1))) and: [n >= 19])

ifTrue:

[p := (((n - b) \\ d + b - d) A011540)].

(n - b) \\ d > (10 raisedToInteger: (j - 1))

ifFalse: [p := (n - b) \\ d].

r := (((n - b) // d + 1) * (10 raisedToInteger: j)) + p.

^r "Hieronymus Fischer, Jan 13 2013"

"------------------"

(Smalltalk)

A011540_inverse

"Version 1: Answers the index n such that A011540(n) = m, where m is the receiver.

Usage: m A011540_inverse

Answer: n"

| m p q s r d |

m := self.

m < 10 ifTrue: [^1].

p := q := 1.

[p < m] whileTrue:

[d := m // p \\ 10.

d = 0 ifTrue: [q := p].

p := 10 * p].

r := m \\ q.

s := r + 2.

p := 10.

q := 1.

m := m - r - 1.

[p < m] whileTrue:

[s := m // p * q + s.

p := 10 * p.

q := 9 * q].

^s

"by Hieronymus Fischer, May 28 2014"

"------------------"

(Smalltalk)

A011540_inverse

"Version 2: Answers the index n such that A011540(n) = m, where m is the receiver.

Uses A052382_inverse from A052382.

Usage: m A011540_inverse

Answer: n"

| m p q d |

m := self.

m < 10 ifTrue: [^1].

p := q := 1.

[p < m] whileTrue:

[d := m // p \\ 10.

d = 0 ifTrue: [q := p].

p := 10 * p].

^m + 1 - (m - 1 - (m \\ q)) A052382_inverse

"by Hieronymus Fischer, May 28 2014"

(MAGMA) [0] cat [ n: n in [0..350] | 0 in Intseq(n) ]; // Vincenzo Librandi, Oct 12 2015

CROSSREFS

A192825 is a subsequence.

Cf. A007954, A043489, A052382, A055641, A168046, A217094, A217096, A229127.

Sequence in context: A156819 A139079 A209932 * A098394 A057169 A201014

Adjacent sequences:  A011537 A011538 A011539 * A011541 A011542 A011543

KEYWORD

nonn,base,easy,look

AUTHOR

N. J. A. Sloane

EXTENSIONS

Edited by M. F. Hasler, Oct 11 2015

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 21 18:09 EST 2019. Contains 319350 sequences. (Running on oeis4.)