mersenneforum.org Shortest sequence of numbers not found in M43
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2006-02-01, 01:23 #1 Xyzzy     Aug 2002 23·1,039 Posts Shortest sequence of numbers not found in M43 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.
 2006-02-01, 05:21 #2 wblipp     "William" May 2003 New Haven 26×37 Posts 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
2006-02-01, 07:15   #3
Orgasmic Troll
Cranksta Rap Ayatollah

Jul 2003

641 Posts

Quote:
 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.

2006-02-01, 13:54   #4
wblipp

"William"
May 2003
New Haven

236810 Posts

Quote:
 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

Code:
           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.

2006-02-01, 15:40   #5
Xyzzy

Aug 2002

23×1,039 Posts

Quote:
 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

 2006-02-01, 18:35 #6 ewmayer ∂2ω=0     Sep 2002 República de California 22×5×11×53 Posts 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...)
2006-02-01, 19:02   #7
Xyzzy

Aug 2002

23×1,039 Posts

Quote:
 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

2006-02-01, 19:15   #8
Xyzzy

Aug 2002

23·1,039 Posts

Quote:
 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

2006-02-01, 19:20   #9
Xyzzy

Aug 2002

831210 Posts

Quote:
 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

 2006-02-02, 06:54 #10 drew     Jun 2005 2·191 Posts What's the longest sequence that appears twice? 3 times? Drew
 2006-02-02, 15:04 #11 Numbers     Jun 2005 Near Beetlegeuse 22×97 Posts 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 ?

 Similar Threads Thread Thread Starter Forum Replies Last Post ONeil ONeil 27 2018-12-03 01:52 Philly314 Aliquot Sequences 3 2014-11-16 14:58 Evgeny Dolgov Miscellaneous Math 38 2010-09-05 17:45 hhh Aliquot Sequences 18 2009-11-02 15:49 roger Puzzles 7 2006-10-27 21:54

All times are UTC. The time now is 17:42.

Mon Oct 25 17:42:23 UTC 2021 up 94 days, 12:11, 0 users, load averages: 1.56, 1.64, 1.49