## Can’t see the forest for the Threes

Posted by Karl Sharman on May 19, 2011 – 11:36 am

What percentage of all integers contains at least one instance of the digit three?

For example, 13, 31, 33 and 103 all contain the digit “three” at least once.

Bonus points for your explanation…

May 19th, 2011 at 12:41 pm

From 1-100 3 appears in 19 integers so the percentage is 19%…

From 1-1,000 3 appears in 271 integers so the percentage is 27.1%…

From 1-10,000 3 appears in 3,439 integers so the percentage is 34.39%…

From 1-100,000 3 appears in 39,512 integers so the percentage is 39.512%…

From 1-1,000,000 it is 455,608 times with a percentage of 45.5608%…

From 1-10,000,000 it is 5,100,472 times with a percentage of 51.00472%…

so there is no concrete percentage, so as infinty grows, the percentage will grow ever higher.

May 19th, 2011 at 12:42 pm

the percentage will grow ever closer to 100% but will never reach it… in the reality of true numbers

May 19th, 2011 at 1:09 pm

If we have an n digit number string and each digit (0-9) is equally likely to appear at any given position (except the lead position cannot be 0). Then the probability that the first digit is not a 3 is 8/9. The probability that none of the other n-1 digits is not a 3 is (9/10)^(n-1). So the probability that at least one digit is a 3 is 1 – (8/9)(9/10)^(n-1). So n=1 => 11.1%, n=2 => 20%, n=3 => 28%,

n=4 => 35.2%, n=5 => 41.7%, n=6 => 47.5%, n=7 => 52.8%, n=44 => 99.0%,

n=65 => 99.9%, n=87 => 99.99%, n=109 => 99.999%, n=131 => 99.9999% etc.

May 19th, 2011 at 1:20 pm

Hi randy. If it never reaches 100%, what does it reach?

May 19th, 2011 at 1:25 pm

I nearly didn’t spot the actual question – exactly 100% of all the integers contain the digit 3. Proof:

Let ε = (8/9)(9/10)(9/10)…, then multiplying both sides by (9/10) =>

(9/10)ε = (8/9)(9/10)(9/10)… = ε. So ε(1 – 9/10) = 0 => ε = 0.

Therefore the probability that an integer contains a 3 is 1-ε = 1 – 0 = 1.

Will slavy give me grief about that?

May 19th, 2011 at 4:14 pm

This seems similar to the .999~ (repeating) equals 1 argument.

The result here gets infinitely close to 100%. For all practical purposes, it equals 100%. But in this case, if you claim the answer is 100%, there is an easy disproof by counter-example (1,2,4,5, etc.)

Nice question

May 20th, 2011 at 10:29 am

for a running total …

f[n] = 9*f[n-1] + 10^(n-1), where n is the number of digits, and f[n] is the sum for all digits from 1 to n.

f[1] = 1

f[2] = 9*1 + 10 = 19

f[3] = 9*19 + 100 = 271

f[4] = 9*271 + 1000 = 3439

f[5] = 9*3439 + 10000 = 40951 (different from randy)

:

:

Not sure how to state this in a formula without recursion.

May 20th, 2011 at 11:50 am

Hi cazayoux. Just allow leading 0’s to get 1 – (9/10)^n. Multiply by 10^n to get the number of numbers containing a 3 => f[n] = 10^n – 9^n

n=1 => 1, n=2 => 19, n=3 => 271, n=4 => 3439

n=5 => 40 951, n=6 => 468 559, n=7 => 5 217 031, n=8 => 56 953 279

n=20 => 87 842 334 540 943 071 199

n=100 => 9 999 734 386 011 124 125 230 661 218 677 964 220 373 170 766 547 346 605 504 025 425 038 260 907 509 098 697 817 005 615 300 955 999

n=200 => 99 999 999 929 449 208 913 446 674 287 535 728 424 065 203 783 492 050 387 212 684 237 128 776 790 737 914 448 417 065 843 420 701 470 552 865 841 845 047 665 174 644 088 133 070 206 928 175 433 305 854 915 545 464 742 972 039 714 676 239 686 807 556 716 665 911 999

May 20th, 2011 at 12:33 pm

2Cazayoux ya man you caught me slippin…

May 20th, 2011 at 12:36 pm

and that small mess up made the rest of my calculations after that one, wrong as well.

May 20th, 2011 at 12:49 pm

Hi randy. Once you’ve debugged your code, I’d love to know if your numbers agree wth mine. I unashamedly referred to your calculations to check my results.

May 20th, 2011 at 1:05 pm

Hi SP. Thanks for not ignoring the “exactly 100%” challenge, I was hoping someone would take it up But now I’ve given myself what might be a hard time proving I’m right (which I’m confident is the case).

In the real number system, there is no such thing as an infinitesimal number, or an infinitesimal is not a number if you prefer. i.e. there is no positive number, x, such that nx < 1 for all natural numbers n. Also ∞ is not a number, yet alone the largest number. If it were, then what would ∞+1 mean?

In your counter-example [I take it that] you removed all the numbers that contained a 3, so you removed exactly 100% of the integers from the set.

For old times sake, let x = 0.999999....., then 10x = 9.99999... = 9 + x. Therefore 9x = 9 and x = 1. That was not sleight of hand. If you were to say that x = 1 - ε, I'd say that ε = 0 and is not an infinitesimal. If ε was a number, then I'd say, ε/2 is a better fit. But then so is ε/4 etc. We don't take the limit ε → 0 (with ε > 0) we actually let ε = 0.

I’m pretty sure that the number system that allows infinitesimals and infinities is called the hyperreal number system. I believe that you can define hyper-infinitesimals as well.

Although I’ve been aware of this for well over a year, it still causes me pain. But I’ve got to defer to the “Archimedean Property” of integers and reals, and the concept of the “Dedekind cut” for the rationals and reals.

May 21st, 2011 at 4:21 pm

My guess will be infinite

May 22nd, 2011 at 12:59 am

10%

May 22nd, 2011 at 4:06 am

i dont know

May 22nd, 2011 at 4:08 am

it will come to 1000%

May 22nd, 2011 at 7:53 am

100% of all integers contain at least one three.

What?!? How can this be? The solution is so surprising, it is difficult, if not impossible to believe that 100% of integers contain the digit three at least once. The simple fact that the number 8, for example, has exactly zero threes in it seems to dispute this.

Consider this: what percentage of the first ten numbers contains at least one three? That’s easy- ten percent; three and only three. What percentage of the first one hundred number contains at least one three? A slightly inflated nineteen percent. What percentage of the thousand numbers contains at least one three? Twenty-seven point one (27.1) percent.

The percentage of numbers with threes in them rises can be expressed as 1 – (.9)^n, where n is the number of digits. It reaches 99% at about the point where n has 42 digits.

The ratio of “threed” to “three-less” numbers at infinity would be 1 – (.9)^(Infinity), or 1.

It is interesting to note that there are also an infinite number of integers which do not contain the digit three. The simple progression “1, 11, 111, … ” illustrates this fact. This means that there are an infinite number of integers with 3 in, as well as an infinite number of integers without 3 in. So, that would be slightly more numbers than ∞….?

This seeming paradox illustrates one of the many “problems” associated with trying to apply concepts (like percentages) used for regular sets on the infinite.

This puzzle, to the best of my knowledge, was originally posed by Clifford Pickover, the author and mathematician.

May 22nd, 2011 at 8:53 am

Just to make it worse, according to Cantor’s notion of infinities, 1,11,111,… is the same sized infinity as 1,2,3,…. The size of the set of integers is the smallest infinity there is and it’s the same size as the set of the rational numbers.

Just for a giggle, there are as many points in a finite line as in an infinite line and a finite and infinite square (and a cube I guess).

May 25th, 2011 at 4:57 pm

is it possible to have a percentage of infinity????

if so whats half

June 24th, 2011 at 1:36 am

Wouldn’t it have to stop at like 99.9 recurring, as it can never get to 100%

June 24th, 2011 at 3:45 am

Hi Frostee. 99.999 recurring = 100 exactly.

July 6th, 2011 at 1:11 pm

Most of the responses claiming 100% are really answering the question “What is the probability that an infinitely large integer has the digit 3?” But that’s not the question. It’s not enough to show that there are an infinite number of integers that include the digit 3, since there are also an infinite number of integers that don’t include the digit 3. The question is, is there a meaningful way to compute the ratio of these two? I believe the answer is no, but I’d be interested in hearing otherwise.

July 6th, 2011 at 1:28 pm

Hi Matthew. I was going to say that “none of the responses indicate your proposed misinterpretation of the question”, but I’ve changed my mind about that, as I believe that the two views are equivalent, even though they seem to be different.

See post 3. It starts with a finite set of numbers, examines the fracion of the numbers that contain a 3, and then takes the limit.

The fraction that don’t contain a 3 is 0, even though an infinite number of numbers don’t contain a 3.

I’m guessing that “measure theory” http://en.wikipedia.org/wiki/Measure_(mathematics) is needed to make it make sense.

July 7th, 2011 at 4:27 pm

Chris,

In post 3 (and 5) you’re taking the limit of an n-digit integer, not the limit of n integers. There’s no doubt about that – an infitely long random integer has a 1.0 probability of having a 3. That says nothing, however, about the percentage, or ratio, of integers with 3.

Let’s say A is the set of “integers with a 3″ and B is the set of “integers without a 3″. Both A and B are countably infinite. I’ve not yet seen a convincing proof that the ratio of A/(A+B) is 1.0. Post 3 doesn’t do that.

In fact, I think we can construct a one-to-one mapping of A with a subset of B, like this:

3 — 1

13 — 11

23 — 111

30 — 1111

31 — 11111

etc.

Which would seem to imply that A, B, and this particular subset of B are all “the same size” as infinities go, and that their ratios are undefined. Just like, I think, the ratio of “even integers” to “odd integers” is undefined.

But what do I know???

Cheers.