mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2006-02-01, 01:23   #1
Xyzzy
 
Xyzzy's Avatar
 
"Mike"
Aug 2002

22×7×281 Posts
Default 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.

Xyzzy is offline   Reply With Quote
Old 2006-02-01, 05:21   #2
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

23×5×59 Posts
Default

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
wblipp is offline   Reply With Quote
Old 2006-02-01, 07:15   #3
Orgasmic Troll
Cranksta Rap Ayatollah
 
Orgasmic Troll's Avatar
 
Jul 2003

641 Posts
Default

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.
Orgasmic Troll is offline   Reply With Quote
Old 2006-02-01, 13:54   #4
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

93816 Posts
Default

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.
wblipp is offline   Reply With Quote
Old 2006-02-01, 15:40   #5
Xyzzy
 
Xyzzy's Avatar
 
"Mike"
Aug 2002

22×7×281 Posts
Default

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
Xyzzy is offline   Reply With Quote
Old 2006-02-01, 18:35   #6
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

3×7×19×29 Posts
Default

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...)
ewmayer is offline   Reply With Quote
Old 2006-02-01, 19:02   #7
Xyzzy
 
Xyzzy's Avatar
 
"Mike"
Aug 2002

22·7·281 Posts
Default

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
Xyzzy is offline   Reply With Quote
Old 2006-02-01, 19:15   #8
Xyzzy
 
Xyzzy's Avatar
 
"Mike"
Aug 2002

22×7×281 Posts
Default

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
Xyzzy is offline   Reply With Quote
Old 2006-02-01, 19:20   #9
Xyzzy
 
Xyzzy's Avatar
 
"Mike"
Aug 2002

22·7·281 Posts
Default

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
Xyzzy is offline   Reply With Quote
Old 2006-02-02, 06:54   #10
drew
 
drew's Avatar
 
Jun 2005

2×191 Posts
Default

What's the longest sequence that appears twice?

3 times?

Drew
drew is offline   Reply With Quote
Old 2006-02-02, 15:04   #11
Numbers
 
Numbers's Avatar
 
Jun 2005
Near Beetlegeuse

22·97 Posts
Default

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 ?
Numbers is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Unique Groupings found in the first 49 mersenne numbers ONeil ONeil 27 2018-12-03 01:52
I think I found proof that no odd perfect numbers exist! Philly314 Aliquot Sequences 3 2014-11-16 14:58
Have Found Principle to generate infinitive PRIME NUMBERS Evgeny Dolgov Miscellaneous Math 38 2010-09-05 17:45
Shortest sequences hhh Aliquot Sequences 18 2009-11-02 15:49
Powers and numbers in sequence roger Puzzles 7 2006-10-27 21:54

All times are UTC. The time now is 18:04.

Thu Dec 3 18:04:36 UTC 2020 up 14:15, 1 user, load averages: 2.14, 2.17, 2.04

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.