## A Lot of Nothing

Posted by Karl Sharman on August 20, 2011 – 5:52 am

How many 0’s are there in the numbers 1 to 1,000,000,000,000?

I refrain from the use of the word billion as our American cousins have difficulty in comprehending what a billion actually is (10^12, not 10^9)…. Flaming gratefully accepted at the usual address….

August 20th, 2011 at 11:36 am

100000010000

August 20th, 2011 at 3:27 pm

We can do this by breaking the problem down to how many zeros are in the 1 digit numbers, 2 digit numbers, etc.

1 digit numbers from 1-9.

This is easy it is 0.

0 total

2 digit numbers from 10-99.

Well we can only have 1 zero max. So the calculation is 1C1*9=9

1C1 for picking where the zero is (only one spot possible). And 9 for the possibilities of the other number

9*1= 9 zeros total

3 digit number from 100-999.

We can have 1 or 2 zeros

# with 1 zero is 2C1*9*9=162

2C1 for picking where the zero is (2 spots possible). And 9*9 for the possibilities of the other numbers

# with 2 zeros is 2C2*9=9

2C2 for picking where the two zeros go. And 9 for the possibilities of the other number

162*1+9*2=180 zeros total

4 digit number from 1000-9999.

We can have 1,2 or 3 zeros

# with 1 zero is 3C1*9*9*9=2187

3C1 for picking where the zero is (3 spots possible). And 9*9*9 for the possibilities of the other numbers

# with 2 zeros is 3C2*9*9=243

3C2 for picking where the two zeros go. And 9*9 for the possibilities of the other numbers

# with 3 zeros is 3C3*9=9

3C2 for picking where the two zeros go. And 9*9 for the possibilities of the other numbers

2439 total

2187*1+243*2+9*3=2700 zeros total

So for example the numbers 1 to 10000 has 0+9+180+2700+4= 2893 zeros

As one can see, a trend emerges…

So for 1 to 10^12-1 (an 11 digit number)

we have the foloowing numbers with 1 zeros:

1C1*9+2C1*9^2+3C1*9^3+……10C1*9^10

we have the foloowing numbers with 2 zeros:

2C2*9+3C2*9^2+4C2*9^3+……10C2*9^9

we have the foloowing numbers with 3 zeros:

3C3*9+4C3*9^2+5C3*9^3+……10C3*9^8

…

we have the foloowing numbers with 10 zeros:

10C10*9

So the total # of zeros is

(1*1C1+2*2C2+3*3C3+…10*10C10)*9+

(1*2C1+2*3C2+3*4C3….+9*10C9)*9^2+

(1*3C1+2*4C2+3*5C3+..8*10C8)*9^3+…….

(1*10C1)*9^10

+12 zeros for 1*10^12

That gives us:

55*9+330*9^2+990*9^3+1848*9^4+2310*9^5+1980*9^6+1155*9^7+440*9^8+99*9^9+10*9^10+12

=98,888,888,901

I’m bound to have made a mistake in the math, but I believe the method is sound (although I could be delusion on that respect too).

Anonymous Cam

August 20th, 2011 at 4:30 pm

No what would 1*10*9 be called in places that call 1*10*12 billion?

August 20th, 2011 at 4:49 pm

10^9 in the mathematical UK is one thousand million. The UK billion is a US trillion.

However, Harold Wilson’s Labour government decided that for financial purposes we’d adopt the US system.

For what it’s worth a googol 10^100 = 10000 * 10^(16*6) is ten thousand hexadecillion.

August 21st, 2011 at 3:15 am

I do agree on Cam’s combination method though no one would think of that if they had a trillion(US) or a billion(UK) xD

August 21st, 2011 at 3:52 am

I agree with Cam, up to a computational mistake. The answer is 108,888,888,901 if I am not mistaken, of course. However, I will present a slightly different solution than his, which in my opinion is less technical and gives rise to an explicit formula for the general case:

Denote by a(n) the number of zeroes, appearing between 1 and 10^n-1. The idea is to derive a recursive formula for this quantity that depends solely on previous members of the sequence, and then to solve it using standard techniques. Firstly, I claim that

a(n+1)=10*a(n)+9*(1+10+…+10^(n-1))=10*a(n)+10^n-1.

To show this, we can write a(n+1)=b(n+1)+a(n), where b(n+1) is the number of zeroes in the representation of all the exactly (n+1)-digit numbers and estimate the latter. it is enough to fix the leading digit to be 1 and multiply the answer by 9. In this setting we have all the zeroes from a(n) plus additional zeroes in front of the low-digit numbers. More precisely, for all the zero-digit numbers (this is only the number 0 by the way) we add one zero in front of it to make it 1-digit, for all 1-digit numbers (after the previous step those are 0,1,…,9) we add a zero in front of them to make them 2-digit, and so on until at the end we make all of them n-digit numbers. This process is described by the formula above.

Now, we want to get rid of the (10^n-1) term and obtain a pure recursive formula. This is done by a standard algorithm. Indeed, from our formula we have that

a(n+2)-10a(n+1)=10a(n+1)-100a(n)+9, i.e., a(n+2)=20a(n+1)-100a(n)+9.

Thus, a(n+3)-a(n+2)=20a(n+2)-120a(n+1)+100a(n), or

a(n+3)-21a(n+2)+120a(n+1)-100a(n)=0

Now, the characteristic equation of the last recursive formula is x^3-21x^2+120x-100=0, or (x-1)(x-10)^2=0.

Therefore, we have that a(n)=A+(B*n+C)10^n, where A, B, and C are constants. To find them, we solve a 3×3 linear system for a(0)=a(1)=0 and a(2)=9 and obtain A=1/9, B=1/10, C=-1/9. Hence,

a(n)=1/9+(n/10-1/9)10^n=n*10^(n-1)-(10^n-1)/9.

To complete the solution, it remains to compute a(12)+12 (the additional 12 zeroes in 10^12) which is the one given in the beginning of the post.

August 21st, 2011 at 6:40 am

so then

10^2 = one hundred

10^3 = one thousand

10^4 = ten thousand

10^5 = one hundred thousand

10^6 = one million

10^7 = ten million

10^8 = one hundred million

10^9 = ? (US is one billion)

10^10 = ? (ten billion)

10^11 = ? (one hundred billion)

10^12 = one billion (one trillion)

so what are the question marks in the UK?

August 21st, 2011 at 7:01 am

UK mathematicians use

10^9 = one thousand million

10^10 = ten thousand million

10^11 = one hundred thouand million

10^12 = one billion

10^18 = one trillion

i.e. Mathematical UK goes up in multiples of one million rather than the US multiples of one thousand. I assume that is still true, it definitely was before Harold Wilson made a law for economics and for that we now use the US system.

See http://en.wikipedia.org/wiki/Names_of_large_numbers for even more info.

It says that the googol is ten thousand sexdecillion (UK) and ten duotrigintillion (US)

August 21st, 2011 at 11:08 am

Thank you, Chris… I learned something new today. If only they would have taught us that back in grade school when we were learning the number system.

August 21st, 2011 at 1:37 pm

Hi Thrym, my pleasure. Being a Brit I had no choice but to be aware of both systems. I doubt that I can even pronounce “duotrigintillion” without a lot of warning.

August 21st, 2011 at 3:17 pm

Hey slavy,

Nice work. The generalized formula is very nice. I suspect it could also be derived via the principle of inclusion/exclusion.

I spotted my error:

I assumed that 10^12-1 was an 11 digit number. It is, in fact, a 12 digit number. As a 10^n-1 number is n digits.

So what I gave was the number of zeroes in 1 to 10^11-1 (98,888,888,889) plus the 12 zeroes in 10^12.

Using the proper amount of digits I get the result of 1,088,888,888,901 which agrees with yours.

Anonymous Cam

August 22nd, 2011 at 6:03 am

I’m working on a simpler solution. For this I need the sum (for i = 1 to n) of the power series Sum (i * N^i) for N > 1.

Does any math brain out there know the answer to this?

August 22nd, 2011 at 6:45 am

I thought we were talking about one thousandth of a billiard.

August 22nd, 2011 at 7:32 am

Hi Cam, I knew where your mistake was I did this (miscounting the digits of 10^n) myself a lot, so that’s why I double checked my answer before correcting yours. Sure, one can derive a(n) via counting all the digits and subtracting the number of 1s, 2s, … 9s, which is the same for all of them and is easier to compute. I believe, this is what Wiz is pursuing right now However, I had some time and decided to refresh the audience knowledge (and to check if I still remember it) on solving recursive sequences.

@Wiz – the formula for your sum is (n*N^(n+2)-(n+1)*N^(n+1)+N)/(N-1)^2. To derive it, you just need to differentiate both sides of the equality sum(for i=0 to n) N^i=(N^(n+1)-1)/(N-1).

August 22nd, 2011 at 10:25 am

Hi Wiz, also see http://www.wolframalpha.com/input/?i=Sum%5Bi+N%5Ei%2C+%7Bi%2C+1%2C+n%7D%5D&cdf=1

(Sorry, the link was faulty – now fixed).

August 22nd, 2011 at 8:53 pm

My approach is to note that in the range 000,000,000,000 to 999,999,999,999 there are equal numbers of the digits 0 to 9. So there are 12 x 10^11 zeros in this range, the same as the number of zeros from 000,000,000,001 to 10^12. However, many of these are leading zeros.

So, the problem comes down to working out the number of leading zeros in this range and subtracting from 12 x 10^11.

From 1 to 9 there are 9 x 11 leading zeros.

From 10 to 99 there are 90 x 10 leading zeros

…

From 10,000,000,000 to 99,999,999,999 there are 90,000,000,000 leading zeros.

These can, of course, be added up manually. However it is much more elegant (as they say) to derive a genaral formula for the number of zeros from 1 to 10^n for any n.

So, the number of leading zeros can be extrapolated from the above results as:

Sum[9(n-i)*10^(i-1)] for i = 1 to n-1. For our 12-digit problem this comes to Sum[9(12-i)*10^(i-1)

= 108*Sum[10^(i-1)] – 9*Sum[i*10^(i-1)]

The first part comes to 12*(10^11-1) and the second part, thanks to Slavy’s assistance in post 14 above, comes to (11*10^11 – 12*10^10 + 1) / 9.

So, there’s my answer: 12*10^11 – 12*(10^11-1) + (98*10^10 + 1) / 9

= 108,888,888,901 which agrees with what Slavy got in post 6.

The general formula for the number of zeros up to 10^n for any positive integer n is:

[(9n-10)*10^(n-1) + 1] / 9 + n

This looks a bit different to Slavy’s general formula, but maybe it’s the same and I just don’t see it.

August 31st, 2011 at 5:02 am

you’re stupid even our poorest people have somewhat of an education. to say that most could not grasp the concept of a billion is pretty lame. now im not saying there are no poorly educated people in america. but alot of that immagrates from other countries where they have no formal education system. but anyway anonymouscam broke it down perfectly. no hard feelings!

August 31st, 2011 at 5:28 am

Duh american made. You haven’t understood what Karl said, or that the remark was intended to be humourous. His point was that the British and American billion are not the same and that quite likely, the vast majority of Americans aren’t aware of that. Being British, he quite rightly considers that the British billion is the one true billion.

The French invented both systems. The British adopted the older long scale system (invented in the 1400s) some 20 years before the Americans adopted the newer short scale system (invented in the 1600s).

I’d take further issue, I don’t think that anyone really directly intuitively comprehends what any large number is. And for large we could be talking > 5.

Imagine a sheet of paper with a lot of dots on it. If there were more than 5 or so, you’d probably have to count them one by one to determine how many there actually were. But with less than 6, you’d probably just “know” how many there were.

By the time you get to a million, nobody could truly say that the have any clue about what that really means. If I showed you a sheet of paper with ten thousand dots on it, and asked you how many there were, I wouldn’t be surprised if you gave a number as low as five hundred or as large as ten million.

August 31st, 2011 at 2:34 pm

american point made.

Chris – if you have seen the film Rain Man, you may realize that you are wrong – most people can tell how many dots there are, or recite the numbers in a phone book. They are special people – american’ts.

Or have I mis-interpreted the film? Was it just one guy with this talent? Not the whole of Americky? Don’t tell me that Hollywood lied to me….;-)

I’m retired now…. an american shot me once – what more can they do to me? I’m also drunk, and coming home from a leaving party. And I’m too young to retire! Too drunk to work right now too…. I shouldn’t be typing this, I should be opening more wine…

September 5th, 2011 at 4:36 am

Our numbering system is based on digits 0-9. I the question did not ask how many times a 0 was used, it asked how were there. There is only one 0 used. You are making this to complicated.