Shortest sequence of numbers not found in M43

[Xyzzy]

We wrote a simple little program to search the decimal expansion of M43 and find the shortest sequence of digits that doesn't appear. The shortest appears to be "120423". Our questions are:

For a number that is 9,152,052 digits long we really expected at least all 6 digit numbers to be found. Is there any way of saying we'd expect a certain length of digits to appear, compared to maybe a random number of equal length? What relationship does the decimal expansion have to randomness in general? Say, up until December, if you gave someone the decimal expansion, would it have appeared to be a random stream of digits? Is there anything interesting about analyzing the distribution of digits in M43?

Apologies in advance for errors in terminology, etc.

[wblipp]

We have 9,152,047 6 digit sequences.

If we fix our target sequence and pick a random starting point, we expect to match once in a million, and miss with probability 0.999999.

The probability a fixed target sequence will miss every time is

(0.999999)^9152047 = 0.000106

There are one million possible target sequences, each of which misses with probability 0.000106, so the expected number of missing sequences is

10^6 * 0.000106 = 106.

So it isn't surprising that some sequences are missing - we should expect about 100 of them to be missing.

If your definition of shortest means that every sequence beginning with "0" is found, that is surprising. I would expect about 10 of the 100 missing sequences to begin with a 0.

William

[Orgasmic Troll]

Originally Posted by wblipp

We have 9,152,047 6 digit sequences.

If we fix our target sequence and pick a random starting point, we expect to match once in a million, and miss with probability 0.999999.

The probability a fixed target sequence will miss every time is

(0.999999)^9152047 = 0.000106

There are one million possible target sequences, each of which misses with probability 0.000106, so the expected number of missing sequences is

10^6 * 0.000106 = 106.

So it isn't surprising that some sequences are missing - we should expect about 100 of them to be missing.

If your definition of shortest means that every sequence beginning with "0" is found, that is surprising. I would expect about 10 of the 100 missing sequences to begin with a 0.

William

Aren't you making the assumption that the probability a fixed target sequence misses for all sequences is independent of the probability that another fixed target sequence misses for all sequences?

I don't think they're independent.

[wblipp]

Originally Posted by TravisT

Aren't you making the assumption that the probability a fixed target sequence misses for all sequences is independent of the probability that another fixed target sequence misses for all sequences?

Actually, no. But even if I was, the events interact so weakly that it can be safely ignored - Knowing that sequence "A" does not occur tells us almost nothing about sequence "B", and knowing the sequence "A" does occur only tells us that there are up to 11 places that sequence B cannot occur.

But Expectation is a linear operator. Suppose the joint probability of A and B occuring or not is the matrix

           NotA   Yes A
Not B      a         b
Yes B      c         d

The number times "NotA" occurs is a+c, the number of times "NotB" occurs is a+b. It's true that "a" get counted twice, but it's also true that that counts as two events.

[Xyzzy]

Originally Posted by wblipp

If your definition of shortest means that every sequence beginning with "0" is found, that is surprising. I would expect about 10 of the 100 missing sequences to begin with a 0.

We didn't test for 6 digit sequences beginning with 0. We just started from 0 and counted up. Here are all the hits below 1e6:

120423 131185 133219 162528 169112 171781 189328 202575 208588 209102 213227 214982 220868 253046 268050 287999 307795 316010 320114 332515 339446 381260 402272 414817 428888 429422 430029 430042 446894 454976 455286 482620 482932 485617 490494 506515 512136 523283 533259 536160 542009 555766 556540 566225 575486 585692 593704 598282 603914 607593 607916 610860 614841 634921 636073 638448 651783 660030 660498 667169 693473 699456 718760 720316 724821 725651 729367 734332 738205 753655 753934 757274 762406 771597 793060 800048 810588 814332 827045 830063 854597 869159 894255 904309 904615 915337 923155 933500 935084 973922 980845 988256 992864 997763

[ewmayer]

Related questions:

- How many of each decimal digit are there in M43?

- What are the lengths of the longest strings of the same decimal digit that occur? (e.g. longest string of 0s, 1s, etc)

- What is the longest string of consecutive digits modulo 10? (i.e. substring of ...0123456789012345678901234567890123456789...)

[Xyzzy]

Originally Posted by ewmayer

- How many of each decimal digit are there in M43?

0: 913468
1: 914272
2: 916362
3: 913997
4: 914191
5: 916441
6: 915744
7: 915905
8: 916856
9: 914816

[Xyzzy]

Originally Posted by ewmayer

- What are the lengths of the longest strings of the same decimal digit that occur? (e.g. longest string of 0s, 1s, etc)

0: 6
1: 9
2: 7
3: 6
4: 7
5: 7
6: 6
7: 7
8: 8
9: 7

[Xyzzy]

Originally Posted by ewmayer

- What is the longest string of consecutive digits modulo 10? (i.e. substring of ...0123456789012345678901234567890123456789...)

0: 0123456
1: 1234567
2: 2345678
3: 345678
4: 456789
5: 567890
6: 6789012
7: 789012
8: 890123
9: 9012345

[drew]

What's the longest sequence that appears twice?

3 times?

Drew

[Numbers]

Let me get this right. Wblipp (who experience tells us knows what he is talking about) says that he would expect about 100 6-digit sequences to be missing from M43.

While Xyzzy (who experience tells us does know how to programme stuff) says that he can find less than eight dozen valid 6-digit strings in the decimal expansion of M43.

Surely one of these must be way off the mark ?