Re: Mersenne: Size of largest prime factor
On 24 Jan 00, at 11:48, Paul Landon wrote: > This is not new news to most people here, but I have to remind > myself, it still hasn't been proved whether there are an infinite > number of Mersenne Primes or an infinite number of Mersenne > composites. The latter conjecture looks very, very probable! Note that it would be sufficient to prove that there are an infinite number of Sophie-Germain primes, since there is a "well known" theorem which states that, if p is a Sophie-Germain prime, then 2^p-1 is divisible by 2p+1. Of course, we do have heuristics which tend to indicate that the number of Mersenne primes is infinite. If this is not so, then the number of Mersenne composites _must_ be infinite. The same heuristics (or even just application of the Prime Number Theorem) suggest that the probability that 2^p-1 is prime decreases with increasing p, which is a strong indication that there are, indeed, an infinite number of Mersenne composites. The contrary would be amusing - if there are a finite number of Mersenne composites, there must be an integer P which is the exponent of the _largest_ composite Mersenne number, i.e. 2^(P+k)-1 is prime for every positive integer k. The challenge then would not be to find all the Mersenne primes, but to determine the value of P. Regards Brian Beesley _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Size of largest prime factor
At 11:48 AM 1/24/00 +0100, Paul Landon wrote: > On the average, the largest prime factor of n is n^0.6065, > >But for Mersennes this might not be the case. >For the size of exponents that we deal with Mersennes are less >composite than a random set of ones & zeroes. That's right, but the original question just said a large random number. ++ | Jud McCranie | || | 137*2^197783+1 is prime! (59,541 digits, 11/11/99)| | 137*2^224879+1 is prime! (67,687 digits, 1/00)| ++ _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Size of largest prime factor
Hiya Henrik, I did mean for 2^p-1; p prime. That's why I work in Computing not the discipline of Maths :-) I am certain that the graph in Knuth sect 4.5.4 (which by luck I had only read for the first time last night) is definately not applicable to Mersenne numbers (with prime exponent). I am certain that there is a minimum size for any divisor of a Mersenne (conversely there is a maximum order of 2 mod f for a candidate factor f) such that there is therefore a maximum size for the largest factor. This makes the cumulative frequency graph hit 1.0 before 100%! (I had best be precise so that one day I grow up to be a good Mathematician, - ignoring the factorisation 1 & itself). Can we do some statistics on the (complete) factorisations we already have? I am also sure that in many other ways Mersennes do not behave like random numbers as discussed in sect 4.5.4. I think I am correct in what I meant to say, that it hasn't been proved that there are an infinite number of Mersenne Primes or an infinite number of Mersenne's with prime exponent that are composite or both with a limiting ratio. Thanks Henrik for encouraging me to be precise in the presense of real Mathematicians. Cheers, Paul Landon Henrik Olsen wrote: > On Mon, 24 Jan 2000, Paul Landon wrote: > > Subject: Re: Mersenne: Size of largest prime factor > >[snip] > > This is not new news to most people here, but I have to remind > > myself, it still hasn't been proved whether there are an infinite > > number of Mersenne Primes or an infinite number of Mersenne > > composites. > Erhm? > 2^n-1 where n is composite is in itself composite, so showing that there > are infinitely many Mersenne composites is easy. :) _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Size of largest prime factor
On Mon, 24 Jan 2000, Paul Landon wrote: > Subject: Re: Mersenne: Size of largest prime factor > > > Pierre Abbat wrote: > > >If I pick a huge number n at random, how much smaller than n, on average, > > is > > >its largest prime factor? > > > Jud McCranie wrote:- > > > On the average, the largest prime factor of n is n^0.6065, and the second > > largest is n^0.2117. Reference: Knuth, the Art of Computer Programming, > > vol 2, section 4.5.4. > > > But for Mersennes this might not be the case. > For the size of exponents that we deal with Mersennes are less > composite than a random set of ones & zeroes. > There are many reasons for this, if 2^p-1 has any factors they > must be bigger than p. They must be +-1 mod 8 etc. > Looking at the string of ones it certainly has regularity. Indeed > there is a measure for it, the order of 2 mod 2^p-1 which is very > low, =p; and any factors have this order as well. This is not > average. > This is not new news to most people here, but I have to remind > myself, it still hasn't been proved whether there are an infinite > number of Mersenne Primes or an infinite number of Mersenne > composites. Erhm? 2^n-1 where n is composite is in itself composite, so showing that there are infinitely many Mersenne composites is easy. :) > > Cheers, > Paul Landon -- Henrik Olsen, Dawn Solutions I/S URL=http://www.iaeste.dk/~henrik/ `Can you count, Banjo?' He looked smug. `Yes, miss. On m'fingers, miss.' `So you can count up to ...?' Susan prompted. `Thirteen, miss,' said Banjo proudly. Terry Pratchett, Hogfather _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Size of largest prime factor
> Pierre Abbat wrote: > >If I pick a huge number n at random, how much smaller than n, on average, > is > >its largest prime factor? > Jud McCranie wrote:- > On the average, the largest prime factor of n is n^0.6065, and the second > largest is n^0.2117. Reference: Knuth, the Art of Computer Programming, > vol 2, section 4.5.4. > But for Mersennes this might not be the case. For the size of exponents that we deal with Mersennes are less composite than a random set of ones & zeroes. There are many reasons for this, if 2^p-1 has any factors they must be bigger than p. They must be +-1 mod 8 etc. Looking at the string of ones it certainly has regularity. Indeed there is a measure for it, the order of 2 mod 2^p-1 which is very low, =p; and any factors have this order as well. This is not average. This is not new news to most people here, but I have to remind myself, it still hasn't been proved whether there are an infinite number of Mersenne Primes or an infinite number of Mersenne composites. Cheers, Paul Landon _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
RE: Mersenne: Size of largest prime factor
At 04:51 PM 1/23/00 -0600, Kyle Evans wrote: >But (assuming n is composite) no prime factor of n can be greater than >n^0.5. So how can n^0.6065 be the average? I'm not assuming that n is composite. Some of them are prime, and in that case the largest prime number is the number itself, and that brings up the average. ++ | Jud McCranie | || | 137*2^197783+1 is prime! (59,541 digits, 11/11/99)| | 137*2^224879+1 is prime! (67,687 digits, 1/00)| ++ _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Size of largest prime factor
> But (assuming n is composite) no prime factor of n can be greater than > n^0.5. So how can n^0.6065 be the average? > > (I hope I'm not showing my idiocy here! :) No, that's not correct. If n is composite, then it *must have* a prime factor 7, but 31>14.73. -Lucas Wiman _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
RE: Mersenne: Size of largest prime factor
Never mind. My idiocy is admitted. :) It's the LOWEST prime factor that can't exceed n^0.5. Sorry for the trouble. Kyle E. -Original Message- From: Kyle Evans [mailto:[EMAIL PROTECTED]] Sent: Sunday, January 23, 2000 4:51 PM To: Jud McCranie; Pierre Abbat Cc: [EMAIL PROTECTED] Subject: RE: Mersenne: Size of largest prime factor But (assuming n is composite) no prime factor of n can be greater than n^0.5. So how can n^0.6065 be the average? (I hope I'm not showing my idiocy here! :) Kyle Evans (newbie on this list) -Original Message- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED]]On Behalf Of Jud McCranie Sent: Sunday, January 23, 2000 4:00 PM To: Pierre Abbat Cc: [EMAIL PROTECTED] Subject: Re: Mersenne: Size of largest prime factor At 03:48 PM 1/23/00 -0500, Pierre Abbat wrote: >If I pick a huge number n at random, how much smaller than n, on average, is >its largest prime factor? On the average, the largest prime factor of n is n^0.6065, and the second largest is n^0.2117. Reference: Knuth, the Art of Computer Programming, vol 2, section 4.5.4. ++ | Jud McCranie | || | 137*2^197783+1 is prime! (59,541 digits, 11/11/99)| | 137*2^224879+1 is prime! (67,687 digits, 1/00)| ++ _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
RE: Mersenne: Size of largest prime factor
But (assuming n is composite) no prime factor of n can be greater than n^0.5. So how can n^0.6065 be the average? (I hope I'm not showing my idiocy here! :) Kyle Evans (newbie on this list) -Original Message- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED]]On Behalf Of Jud McCranie Sent: Sunday, January 23, 2000 4:00 PM To: Pierre Abbat Cc: [EMAIL PROTECTED] Subject: Re: Mersenne: Size of largest prime factor At 03:48 PM 1/23/00 -0500, Pierre Abbat wrote: >If I pick a huge number n at random, how much smaller than n, on average, is >its largest prime factor? On the average, the largest prime factor of n is n^0.6065, and the second largest is n^0.2117. Reference: Knuth, the Art of Computer Programming, vol 2, section 4.5.4. ++ | Jud McCranie | || | 137*2^197783+1 is prime! (59,541 digits, 11/11/99)| | 137*2^224879+1 is prime! (67,687 digits, 1/00)| ++ _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Size of largest prime factor
At 03:48 PM 1/23/00 -0500, Pierre Abbat wrote: >If I pick a huge number n at random, how much smaller than n, on average, is >its largest prime factor? On the average, the largest prime factor of n is n^0.6065, and the second largest is n^0.2117. Reference: Knuth, the Art of Computer Programming, vol 2, section 4.5.4. ++ | Jud McCranie | || | 137*2^197783+1 is prime! (59,541 digits, 11/11/99)| | 137*2^224879+1 is prime! (67,687 digits, 1/00)| ++ _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: Size of largest prime factor
If I pick a huge number n at random, how much smaller than n, on average, is its largest prime factor? phma _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
