Mersenne Digest Wednesday, July 14 1999 Volume 01 : Number 597 ---------------------------------------------------------------------- Date: Mon, 12 Jul 1999 01:00:37 -0500 From: Ken Kriesel <[EMAIL PROTECTED]> Subject: Mersenne: re: Mersenne prime exponent binary representations and 1's frequency (incl M38) I said: >The incidence of 1's in the second place from the right (excluding >p=2) is 16/(16+21)=43.2%; This indicates the degree to which Mp for p=1 mod 4 is more probably prime than is p=3 mod 4. Of Mp for p=3 and up, p mod 4 # % 1 21 56.8 3 16 43.2 >the incidence in the remaining interior bits is 172/358=48.0% This last line was wrong. For p=3, the second bit from the right is what I've been calling an exterior bit (most significant or least significant). So the one bit for p=3 should not be subtracted from either the one bit's count or the total bit positions counts for interior bits. So the correct incidence in remaining interior bits is 173/359~=48.2%. Credit for spotting this error goes to, who else, but George Woltman! George asks, what about the bit second from the left? In total, 26 0 bits vs only 12 1 bits. (0 26 of 38 times or ~68.4%; 26/12=2.16666...) Excluding p=2 and p= 3, to look only at interior bits, 25 0 bits vs only 11 1 bits; 0 25 of 36 times, ~69.4%; 25/11=2.2727...) Now why would that be, that a 0 bit is more than twice as likely as a 1 bit? (Note that Mp#38, M6972593, has the less likely 1 bit in the second most significant position; searching biased for these probabilities would have delayed finding it. But the 4 previous Mersenne primes all had a 0 bit in that position.) Ken ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ Date: Mon, 12 Jul 1999 08:57:34 +0200 (MET DST) From: [EMAIL PROTECTED] Subject: Re: Mersenne: re: Mersenne prime exponent binary representations and 1's frequency (incl M38) Ken Kriesel <[EMAIL PROTECTED]> writes: > George asks, what about the bit second from the left? > In total, 26 0 bits vs only 12 1 bits. (0 26 of 38 times or ~68.4%; > 26/12=2.16666...) > Excluding p=2 and p= 3, to look only at interior bits, 25 0 bits vs > only 11 1 bits; 0 25 of 36 times, ~69.4%; 25/11=2.2727...) > Now why would that be, that a 0 bit is more than twice as likely as a 1 bit? > (Note that Mp#38, M6972593, has the less likely 1 bit in the second most > significant position; searching biased for these probabilities would have > delayed finding it. But the 4 previous Mersenne primes all had a 0 bit > in that position.) The law of leading digits predicts that, for decimal numbers, log10(2) ~= 30.1% will have leading digit 1. More precisely, the fractional parts of the base-10 logarithms are assumed to be uniformly distributed. This distribution is invariant under many transformations, such as converting a physical constant from miles/hour to meters/second. For binary numbers, this predicts the leading bit is 1 with probability log2(2) = 1, a not surprising result. The two leading bits are 10 with probability log2(3) - log2(2) = ln(3/2)/ln(2) ~= 58.5%. This prediction is smaller than the observed 68.4%, but above 50%. Peter Montgomery ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ Date: Mon, 12 Jul 1999 09:21:40 -0400 From: Jeff Woods <[EMAIL PROTECTED]> Subject: Re: Mersenne: re: Mersenne prime exponent binary representations and 1's frequency (incl M38) At 08:57 AM 7/12/99 +0200, you wrote: > The law of leading digits predicts that, for decimal numbers, >log10(2) ~= 30.1% will have leading digit 1. Uh, won't they *ALL* have a leading digit of one? Anything with a leading digit of ZERO can be totally discounted.... ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ Date: Mon, 12 Jul 1999 09:24:56 -0400 From: Jud McCranie <[EMAIL PROTECTED]> Subject: Re: Mersenne: re: Mersenne prime exponent binary representations and 1's frequency (incl M38) At 08:57 AM 7/12/99 +0200, [EMAIL PROTECTED] wrote: > The law of leading digits predicts that, for decimal numbers, >log10(2) ~= 30.1% will have leading digit 1. It depends on what set of numbers you are considering. +----------------------------------------------+ | Jud "program first and think later" McCranie | +----------------------------------------------+ ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ Date: Mon, 12 Jul 1999 11:55:59 -0400 (EDT) From: Chip Lynch <[EMAIL PROTECTED]> Subject: Re: Mersenne: re: Mersenne prime exponent binary representations and 1's frequency (incl M38) I'm not sure what the law of leading digits is, but I read this as talking only about base 10 numbers... so the leading digit 1 is compared to leading digit 2, 3, 4, ..., 9. Right? So for numbers 2^n (in Base 10), [or is it 2^p?] there are a lot more leading ones than one would "expect" naievely (you would expect 1/9 to start with "1", I imagine). Why this is, I have no idea... can someone explain? - ---Chip > > The law of leading digits predicts that, for decimal numbers, > >log10(2) ~= 30.1% will have leading digit 1. > > Uh, won't they *ALL* have a leading digit of one? Anything with a leading > digit of ZERO can be totally discounted.... > > > ________________________________________________________________ > Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm > \\ ^ // (o o) ---oOO--(_)--OOo------------------------------------ | Chip Lynch | Computer Guru | | [EMAIL PROTECTED] | | | (703) 465-4176 (w) | (202) 362-7978 (h) | ---------------------------------------------------- ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ Date: Mon, 12 Jul 1999 12:17:58 -0400 From: Jeff Woods <[EMAIL PROTECTED]> Subject: Mersenne: Coverage for GIMPS -- in error http://www.cnn.com/TECH/computing/9907/12/5progs.idg/ They don't mention the new find, and totally munged the quoting of past finds. They do link to the site. Can someone LART the folks at IDG and CNN? ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ Date: Mon, 12 Jul 1999 13:25:12 -0400 From: Jud McCranie <[EMAIL PROTECTED]> Subject: Re: Mersenne: re: Mersenne prime exponent binary representations and 1's frequency (incl M38) At 11:55 AM 7/12/99 -0400, Chip Lynch wrote: >I'm not sure what the law of leading digits is, but I read this as talking >only about base 10 numbers... so the leading digit 1 is compared to >leading digit 2, 3, 4, ..., 9. Right? So for numbers 2^n (in Base 10), >[or is it 2^p?] there are a lot more leading ones than one would "expect" >naievely (you would expect 1/9 to start with "1", I imagine). > >Why this is, I have no idea... can someone explain? It is also known as Benford's law and the First Digit law. You can read about it at Eric's Treasure Trove of Math (seems to be down right now or I'd give the URL). It would take me a few paragraphs to explain, but I'll do it if you can't find it elsewhere. +----------------------------------------------+ | Jud "program first and think later" McCranie | +----------------------------------------------+ ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ Date: Mon, 12 Jul 1999 16:33:59 -0400 From: "Geoffrey Faivre-Malloy" <[EMAIL PROTECTED]> Subject: RE: Mersenne: re: Mersenne prime exponent binary representations and 1's frequency (incl M38) Here's a link... http://www.newscientist.com/ns/19990710/thepowerof.html > -----Original Message----- > From: [EMAIL PROTECTED] > [mailto:[EMAIL PROTECTED]]On Behalf Of Jud > McCranie > Sent: Monday, July 12, 1999 1:25 PM > To: Chip Lynch > Cc: [EMAIL PROTECTED] > Subject: Re: Mersenne: re: Mersenne prime exponent binary > representations and 1's frequency (incl M38) > > > At 11:55 AM 7/12/99 -0400, Chip Lynch wrote: > >I'm not sure what the law of leading digits is, but I read this > as talking > >only about base 10 numbers... so the leading digit 1 is compared to > >leading digit 2, 3, 4, ..., 9. Right? So for numbers 2^n (in Base 10), > >[or is it 2^p?] there are a lot more leading ones than one would > "expect" > >naievely (you would expect 1/9 to start with "1", I imagine). > > > >Why this is, I have no idea... can someone explain? > > > It is also known as Benford's law and the First Digit law. You can read > about it at Eric's Treasure Trove of Math (seems to be down right now or > I'd give the URL). It would take me a few paragraphs to explain, but I'll > do it if you can't find it elsewhere. > > +----------------------------------------------+ > | Jud "program first and think later" McCranie | > +----------------------------------------------+ > > > ________________________________________________________________ > Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ Date: Mon, 12 Jul 1999 20:47:30 +0000 (GMT) From: Henrik Olsen <[EMAIL PROTECTED]> Subject: Re: Mersenne: re: Mersenne prime exponent binary representations and 1's frequency (incl M38) On Mon, 12 Jul 1999, Jud McCranie wrote: > > At 11:55 AM 7/12/99 -0400, Chip Lynch wrote: > >I'm not sure what the law of leading digits is, but I read this as talking > >only about base 10 numbers... so the leading digit 1 is compared to > >leading digit 2, 3, 4, ..., 9. Right? So for numbers 2^n (in Base 10), > >[or is it 2^p?] there are a lot more leading ones than one would "expect" > >naievely (you would expect 1/9 to start with "1", I imagine). > > > >Why this is, I have no idea... can someone explain? > > > It is also known as Benford's law and the First Digit law. You can read > about it at Eric's Treasure Trove of Math (seems to be down right now or > I'd give the URL). It would take me a few paragraphs to explain, but I'll > do it if you can't find it elsewhere. http://www.treasure-troves.com/ - -- Henrik Olsen, Dawn Solutions I/S URL=http://www.iaeste.dk/~henrik/ Animal behaviour is best described by the four F's Feed, Fight, Flee and Reproduce ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ Date: Mon, 12 Jul 1999 14:15:43 -0700 From: Luke Welsh <[EMAIL PROTECTED]> Subject: Re: Mersenne: re: Mersenne prime exponent binary representations and 1's frequency (incl M38) At 11:55 AM 7/12/99 -0400, Chip Lynch wrote: >I'm not sure what the law of leading digits is[......] See "Benford's Law" http://sciencenews.org/sn_arc98/6_27_98/mathland.htm http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fibonacci/fibmaths.html#msds http://www.treasure-troves.com/math/BenfordsLaw.html http://www.seanet.com/~ksbrown/kmath302.htm http://www.256.com/~gray/info/benfords.html http://web.cari.net/~ddbass/news0002.htm http://www.askdrmath.com/problems/edwards8.6.98.html De wet van Benford (has a photo of Benford) http://htsa.ie.hva.nl/~pylgroms/or1/lesstof/verdelin/logaritm.htm (So, 'wet' is Dutch for 'law'? What is Dutch for 'wet' ?) Peter, thank you for introducing a lot of us to Benford and his law. - --Luke ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ Date: Mon, 12 Jul 1999 17:45:05 -0400 (EDT) From: Lucas Wiman <[EMAIL PROTECTED]> Subject: Re: Mersenne: re: Mersenne prime exponent binary > I'm not sure what the law of leading digits is, but I read this as talking > only about base 10 numbers... so the leading digit 1 is compared to > leading digit 2, 3, 4, ..., 9. Right? So for numbers 2^n (in Base 10), > [or is it 2^p?] there are a lot more leading ones than one would "expect" > naievely (you would expect 1/9 to start with "1", I imagine). As Jud said, this is called Benford's law. It was originally discoved in the late 1800's by "Some Guy," who was never noticed. It was then rediscovered by Benford in the 1930's. I think that he worked for AT&T. Both guys discovered this law by looking at wear-and-tear on Logarithm books. This law states that for a given base a, and a given leading digit b (0<b<a-1), the probability that the leading digit is b is log_a(1+1/b). What Peter was doing when he was talking about the second digit was (aparently) converting it to base 4, and working witht the usual Benfords law. >> The law of leading digits predicts that, for decimal numbers, >>log10(2) ~= 30.1% will have leading digit 1. >Uh, won't they *ALL* have a leading digit of one? Anything with a leading >digit of ZERO can be totally discounted.... Read the rest of his email, and you will be enlightened... >> The law of leading digits predicts that, for decimal numbers, >>log10(2) ~= 30.1% will have leading digit 1. >It depends on what set of numbers you are considering. That's the point of Benford's law, it is supposed to be relatively independent of the set of numbers. Note that in the set of mersenne prime exponents (so far), the leading digit 1 (in decimal), turns up 10 times as opposed to the 4.2 times expected by equal leading digit distribution... - -Lucas Wiman P.S. I seem to recall this being mentioned (benford's law), shortly after I joine the list. May have to go into the FAQ. ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ Date: Mon, 12 Jul 1999 18:51:31 -0400 From: Jud McCranie <[EMAIL PROTECTED]> Subject: Re: Mersenne: re: Mersenne prime exponent binary At 05:45 PM 7/12/99 -0400, Lucas Wiman wrote: > >As Jud said, this is called Benford's law. It was originally discoved in >the late 1800's by "Some Guy," who was never noticed. Astronomer Simon Newcom(e). +----------------------------------------------+ | Jud "program first and think later" McCranie | +----------------------------------------------+ ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ Date: Tue, 13 Jul 1999 01:05:24 +0200 From: "Otto Bruggeman" <[EMAIL PROTECTED]> Subject: Mersenne: OT: Dutch lesson == nederlandse les > (So, 'wet' is Dutch for 'law'? What is Dutch for 'wet' ?) Yep, law(english) = wet(dutch) and nat (dutch) = wet (english). More dutch lessons anyone ???? Just reply privately ([EMAIL PROTECTED]) Otto. ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ Date: Mon, 12 Jul 1999 20:39:50 -0400 (EDT) From: "Vincent J. Mooney Jr." <[EMAIL PROTECTED]> Subject: Re: Mersenne: re: Mersenne prime exponent binary representations and 1's frequency (incl M38) For DECIMAL NUMBERS (base 10) not BINARY numbers (base 2) At 09:21 AM 7/12/99 -0400, you wrote: >At 08:57 AM 7/12/99 +0200, you wrote: > >> The law of leading digits predicts that, for decimal numbers, >>log10(2) ~= 30.1% will have leading digit 1. > >Uh, won't they *ALL* have a leading digit of one? Anything with a leading >digit of ZERO can be totally discounted.... > > >________________________________________________________________ >Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm > ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ Date: Tue, 13 Jul 1999 00:38:38 -0400 (EDT) From: Lucas Wiman <[EMAIL PROTECTED]> Subject: Mersenne: Benford's law (was exp. representations) >So for numbers 2^n (in Base 10), [or is it 2^p?] there are a lot more leading >ones than one would "expect" naievely (you would expect 1/9 to start with >"1", I imagine). Yes. Though they were talking about the exponents... Here are the percentages for the first 3000 powers of 2. The first collumn is the percentage, the second is the difference from the predicted Benford percentage. Weird, I would have thought that it wouldn't affect powers of two... .30110036678892964321 .00007037112494844799 .17639213071023674558 .00030087165455550349 .12470823607869289763 -.00023050052960705550 .09703234411470490163 .00012233110664848727 .07935978659553184394 .00017854054790701622 .06702234078026008669 .00007555114964688849 .05768589529843281093 -.00030605167925394399 .05168389463154384794 .00053137218416255899 .04534844948316105368 -.00040904107751407172 - -Lucas Wiman ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ Date: Tue, 13 Jul 1999 02:13:02 -0400 (EDT) From: Lucas Wiman <[EMAIL PROTECTED]> Subject: Mersenne: Additions to the FAQ all, I added a question about Benford's law to the FAQ, and did some re-ordering. Check it out at http://www.tasam.com/~lrwiman/FAQ-mers Everyone please read the relavent sections in the FAQ before asking a "basic" question. Thankyou, Lucas Wiman ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ Date: Tue, 13 Jul 1999 09:02:14 +0100 From: "Brian J. Beesley" <[EMAIL PROTECTED]> Subject: Re: Mersenne: re: Mersenne prime exponent binary On 12 Jul 99, at 17:45, Lucas Wiman wrote: > That's the point of Benford's law, it is supposed to be relatively independent > of the set of numbers. ... within reason ? If I take the (decimal) powers of 0.999 and get bored after 100 trials, I find they _all_ start with a 9 ;-) > Note that in the set of mersenne prime exponents (so far), the leading > digit 1 (in decimal), turns up 10 times as opposed to the 4.2 times > expected by equal leading digit distribution... Actually we should expect an excess of smaller leading digits over that predicted by "Benford's Law" in this case. A smaller exponent is more likely to be prime than a larger exponent, and a smaller prime exponent is more likely to give rise a Mersenne prime than a larger prime exponent. "Benford's Law" would follow if _every_ exponent (prime or composite) was equally likely to give rise to a Mersenne prime. [Different message, same author] > Yes. Though they were talking about the exponents... > Weird, I would have thought that it wouldn't affect powers of > two... Why not? Looks like a perfect model to me! Regards Brian Beesley ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ Date: Tue, 13 Jul 1999 08:51:58 +0000 (GMT) From: Henrik Olsen <[EMAIL PROTECTED]> Subject: Re: Mersenne: Benford's law (was exp. representations) On Tue, 13 Jul 1999, Lucas Wiman wrote: > >So for numbers 2^n (in Base 10), [or is it 2^p?] there are a lot more leading > >ones than one would "expect" naievely (you would expect 1/9 to start with > >"1", I imagine). > Yes. Though they were talking about the exponents... > Here are the percentages for the first 3000 powers of 2. The first collumn > is the percentage, the second is the difference from the predicted Benford > percentage. Weird, I would have thought that it wouldn't affect powers of > two... > .30110036678892964321 .00007037112494844799 > .17639213071023674558 .00030087165455550349 > .12470823607869289763 -.00023050052960705550 > .09703234411470490163 .00012233110664848727 > .07935978659553184394 .00017854054790701622 > .06702234078026008669 .00007555114964688849 > .05768589529843281093 -.00030605167925394399 > .05168389463154384794 .00053137218416255899 > .04534844948316105368 -.00040904107751407172 Benfords Law is a direct consequence of the fact that most sets of numbers obtained by actual measurements are either resulting from exponentially distributed data (eg. river lengths), or come from uniformly distributed numbers, gathered from multiple ranges of exponentially distributed length (eg. house numbers). Since powers of numbers are just about the cleanest exponentially distributed set of numbers you can get, it shouldn't really come as a surprise that they fix the law:) - -- Henrik Olsen, Dawn Solutions I/S URL=http://www.iaeste.dk/~henrik/ Leonardo DiCaprio: Your social class is stuffy. Let's dance with the ship's rats and have fun. Kate Winslet: You have captured my heart. Let's run around the ship and giggle. (The ship SINKS.) Leonardo DiCaprio: Never let go. Kate Winslet: I promise. (lets go) Titanic, the Movie-A-Minute version ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ Date: Tue, 13 Jul 1999 14:20:18 +0200 From: Johan Winge <[EMAIL PROTECTED]> Subject: Re: Mersenne: Mersenne prime exponent binary representations and 1's frequency (incl M38) [Oh, this is my first post to this list. Hope you'll see it correctly.] At 18:42 1999-07-11 -0500, Ken Kriesel wrote: >The latest mersenne exponent is added below. > >position p in p # of bit p in hex p mod 4 >in list base 10 in base 2 1's places > 5 13 1101 3 4 D 3 Uhm, isn't 13 mod 4 = 1? >total 263 471 # 1's=21 > # 3's=16 ...but that only betters the statistics to 59.5% 1's vs. 40.5% 3's. Interesting. (It's a pity we don't have a larger basis[?] though...) Just to make sure this irregularity isn't the case for all primes, I checked all primes above 2 and less than 10000000 for mod 4 and, not surprisingly, they are almost evenly distributed, (332180 1's and 332398 3's.) Sorry if this has been discussed before, or if it is common knowledge, or whatever. Regards, Johan Winge ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ Date: Tue, 13 Jul 1999 08:35:40 -0400 From: Jud McCranie <[EMAIL PROTECTED]> Subject: Re: Mersenne: Benford's law (was exp. representations) At 12:38 AM 7/13/99 -0400, Lucas Wiman wrote: >Here are the percentages for the first 3000 powers of 2. The first collumn >is the percentage, the second is the difference from the predicted Benford >percentage. Weird, I would have thought that it wouldn't affect powers of >two... That's the type of thing that follows the law precisely in the long run. (the repeated multiplications). A way to look at this is to think of a slide rule (if you remember them). Anything that has a uniform distribution on the slide rule follows Benford's law. The distance from 1.0 to 2.0 on the slide rule is 0.301... of the length of the scale, etc. A repeated multiplication by a number other than 0 or 1 gives a uniform distribution along the scale of the slide rule. +----------------------------------------------+ | Jud "program first and think later" McCranie | +----------------------------------------------+ ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ Date: Tue, 13 Jul 1999 09:05:22 -0400 (EDT) From: Chip Lynch <[EMAIL PROTECTED]> Subject: Re: Mersenne: re: Mersenne prime exponent binary > > Note that in the set of mersenne prime exponents (so far), the leading > > digit 1 (in decimal), turns up 10 times as opposed to the 4.2 times > > expected by equal leading digit distribution... > > Actually we should expect an excess of smaller leading digits over > that predicted by "Benford's Law" in this case. A smaller exponent is > more likely to be prime than a larger exponent, and a smaller prime > exponent is more likely to give rise a Mersenne prime than a larger > prime exponent. "Benford's Law" would follow if _every_ exponent > (prime or composite) was equally likely to give rise to a Mersenne > prime. But that's part of the interesting thing... the size of the exponent is only vaguely associated with the LEADING digit. I disagree that we'd expect smaller leading digits, at least noticeably many, since it's the order of magnitude, not just the leading digit that makes the nth mersenne prime larger or smaller. I mean M20 is some 50 digits longer than M19... at this distance, I don't see how the leading digit is affected by the larger likelyhood that smaller exponents would make more likely primes. But I'm probably wrong. This is what makes this a really interesting fact, tho, I guess. > > Yes. Though they were talking about the exponents... > > Weird, I would have thought that it wouldn't affect powers of > > two... > > Why not? Looks like a perfect model to me! In some vague attempt to not take the Benford issue off topic, it's interesting that numbers 2^n (for all Natural numbers n) follows the pattern VERY closely, but it's also interesting (perhaps moreso), that 2^p follows the pattern, as do (apparently) the Mersenne primes themselves, as do (from quick examination) the exponents for the mersenne primes. Thanks for adding this to the FAQ, btw. - ---Chip \\ ^ // (o o) ---oOO--(_)--OOo------------------------------------ | Chip Lynch | Computer Guru | | [EMAIL PROTECTED] | | | (703) 465-4176 (w) | (202) 362-7978 (h) | ---------------------------------------------------- ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ Date: Tue, 13 Jul 1999 13:53:51 -0400 From: Jud McCranie <[EMAIL PROTECTED]> Subject: Re: Mersenne: re: Mersenne prime exponent binary At 09:05 AM 7/13/99 -0400, Chip Lynch wrote: >In some vague attempt to not take the Benford issue off topic, it's >interesting that numbers 2^n (for all Natural numbers n) follows the >pattern VERY closely, In the limit as n -> infinity, 2^n must follow the law exactly. Almost by definition. +----------------------------------------------+ | Jud "program first and think later" McCranie | +----------------------------------------------+ ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ Date: Tue, 13 Jul 1999 11:06:49 -0700 (PDT) From: Kris Garrett <[EMAIL PROTECTED]> Subject: Mersenne: Hyperbola I've noticed that with any odd number you can make the formula x^2 - y^2 = n where n = the odd number and x - y and x + y are factors of n. I was just wondering if one could use the graph of a hyperbola to see only the possible integer values of x and y. _________________________________________________________ Do You Yahoo!? Get your free @yahoo.com address at http://mail.yahoo.com ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ Date: Tue, 13 Jul 1999 21:39:13 +0200 From: "Henk Stokhorst." <[EMAIL PROTECTED]> Subject: Mersenne: new milestone L.S. we reached a new small milestone. The server is now handing out 10.000.000+ exponents. I just received my first one today for factoring. YotN, Henk Stokhorst. (I got 10.003.999) ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ Date: Tue, 13 Jul 1999 13:41:08 -0700 From: Todd Sauke <[EMAIL PROTECTED]> Subject: Re: Mersenne: re: Mersenne prime exponent binary Brian Beesley wrote: >Actually we should expect an excess of smaller leading digits over >that predicted by "Benford's Law" in this case. A smaller exponent is >more likely to be prime than a larger exponent, and a smaller prime >exponent is more likely to give rise a Mersenne prime than a larger >prime exponent. "Benford's Law" would follow if _every_ exponent >(prime or composite) was equally likely to give rise to a Mersenne >prime. > This is not true. Actually, it is the fact that smaller primes are more likely to give Mersennes that theoretically should result in a "Benford's Law" type behavior of the second leading bit. It is in some sense an "accident" that Mersenne exponents SHOULD follow Benford's Law (at least the second bit generalization of it), and an irony that, due to small number statistics, they actually DON'T! (68% zeroes instead of predicted 58% or whatever) Benford's Law comes about because of power law scaling of some numbers. Many of the referenced web links emphasized that Benford's law is NOT for "regular" numbers, but ONLY for numbers expressing amounts in some (human selected) units, and that it is some property of "power law scaling" and/or "logarithmic invariance" of arbitrary choice of units to express AMOUNTS (NOT numbers) of things that result in Benford's law. As has been dealt with in many many recent posts regarding the density of Mersenne exponents, there is an expected (and observed) uniform density of Mersennes in LOG space, ie. equal numbers of Mersennes per factor of two in candidate space of about 1.5 or 1.48 or whatever. It is this logarithmic scaling or invariance that theoretically SHOULD result in Benford Law type behavior. It is ONLY this decreasing likelihood of primes to generate Mersennes that should cause Benford law behavior, not a reason for deviation from it. In fact, if the likelihood of numbers generating Mersennes followed some other law, say decreasing faster than logarithmically, then Benford's law might not apply, or only approximately. This thread has been very interesting in it's own right mathematically, but it's only "accidental" in some sense that Mersenne exponents should follow the law, and as I said before, ironic that it doesn't! The fact that we KNOW (or believe) the logarithmic scaling of Mersennes allows us to bypass all of the heuristic arguments about logarithmic scaling of human selected units for expressing quantities, and to directly DERIVE the law for Mersennes, as opposed to heuristically generating it for the other cases. Todd Sauke ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ Date: Tue, 13 Jul 1999 22:50:20 GMT From: [EMAIL PROTECTED] (Steven Whitaker) Subject: Re: Mersenne: Benford's law (was exp. representations) Maybe it's my imagination, but it seems to me that the factors of the prime exponent Mersenne numbers start with a 1 more often than a 2 or 3 etc. Are they obeying Benford's law too? For instance, for the 10 primes from 5003 to 5081, there are 20 known factors. 10 of them start with a 1. Thanks Steve - -- Steve Whitaker ([EMAIL PROTECTED]) Egham, Surrey, UK "Start the day with a smile and get it over with" - WC Fields ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ Date: Tue, 13 Jul 1999 20:34:52 -0400 From: Chris Nash <[EMAIL PROTECTED]> Subject: Re: Mersenne: Benford's law (was exp. representations) Steven Whitaker wrote: > Maybe it's my imagination, but it seems to me that the factors of the > prime exponent Mersenne numbers start with a 1 more often than a 2 or > 3 etc. Are they obeying Benford's law too? > For instance, for the 10 primes from 5003 to 5081, there are 20 known > factors. 10 of them start with a 1. Something similar. The Benford's law distribution works because we 'expect' natural, boundless, data to have the decimal part of the logarithm "fairly uniformly" distributed, and a quick look at a slide rule (younger readers, ask your Dad!) has 30.103% of its length with initial digit 1. By Merten's theorem, the probability *any* large number N has no factor smaller than X is C/log X, C is exp(-gamma) if I remember rightly. (strictly, X has to be much bigger than 1, and much smaller than sqrt(N) for this to make any sense). By that sort of estimate, suppose N has a factor F between 10^k and 10^(k+1). Then the probability that F begins with a 1 is something like [1/k-1/(k+0.30103)]/[1/k-1/(k+1)] which tends to log10(2) as k tends to infinity - so the distribution does approach Benford's law. In fact, if you plot the distribution above, it's more generous to 1's for smaller factors. It seems a skewed distribution, but remember it's based on our insistence of observing the world base 10, and believing that 2-1 is "just as important" as (M38)-(M38-1). The same observation is repeatable in any base - of course, at the most ridiculous, ALL factors begin with a 1 when written in base 2. Chris Nash Lexington KY UNITED STATES ================================================= Still a co-discoverer of the largest known *non*-Mersenne prime ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ Date: Wed, 14 Jul 1999 01:26:58 -0700 From: Paul Leyland <[EMAIL PROTECTED]> Subject: RE: Mersenne: Hyperbola > From: Kris Garrett [mailto:[EMAIL PROTECTED]] > I've noticed that with any odd number you can make the formula x^2 - > y^2 = n where n = the odd number and x - y and x + y are > factors of n. > I was just wondering if one could use the graph of a hyperbola to see > only the possible integer values of x and y. In effect, you've just described the basis behind many factoring algorithms. Fermat observed that if one could represent an integer as the difference of two squares, its factorization would be at hand; he then gave an efficient (for the 17th Century!) algorithm for finding the squares. More recently, algorithms such Continued Fraction, Quadratic Sieve and Number Field Sieve have all used Fermat's idea in the form x^2-y^2 = kN (k a small integer) or, equivalently, x^2 == y^2 (mod N) to factor N. The algorithms differ in how they construct the x and y and are *much* more efficient than Fermat's algorithm, but the underlying idea is the same. Paul ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ End of Mersenne Digest V1 #597 ******************************
