Mersenne Digest Thursday, June 24 1999 Volume 01 : Number 587 ---------------------------------------------------------------------- Date: Tue, 22 Jun 1999 20:30:09 EDT From: [EMAIL PROTECTED] Subject: Mersenne: Testing for factors <<Now we can filter out multiples of small primes>> I'm assuming that we don't need to divide by factors divisible by 3 or 5, etc, because a Mersenne number cannot be divisible by 3 or 5 because they don't have the structure 2kp+1 themselves? (Excluding the REALLY low Mersenne numbers). Ideally, we'd like to only test factors that are prime themselves.... Am I right? S.T.L. ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ Date: Tue, 22 Jun 1999 21:15:43 -0400 (EDT) From: "Vincent J. Mooney Jr." <[EMAIL PROTECTED]> Subject: Re: Mersenne: Testing for factors Yes, S.T.L: is right, and I believe that more can be done. No two Mersenne primes can have the same prime divisor, as I recall. So by listing the composite Mersenne primes (i.e., p is prime but 2^p -1 is not prime), we can get a list of primes that no longer need to be tried as divisors of 2^p - 1. So sure, use the +/-1 mod 8 rules, eliminating a series of trial divisors, and pare the list even more by comparing to known divisors of Mersenne primes. These prime divisors would presumably be in a database. As the work of factoring progresses, one can see that factoring is more and more important. If my hypothesis that "No two Mersenne primes can have the same prime divisor" is incorrect, I appologize in advance. At 08:30 PM 6/22/99 EDT, you wrote: ><<Now we can filter out multiples of small primes>> >I'm assuming that we don't need to divide by factors divisible by 3 or 5, >etc, because a Mersenne number cannot be divisible by 3 or 5 because they >don't have the structure 2kp+1 themselves? (Excluding the REALLY low Mersenne >numbers). Ideally, we'd like to only test factors that are prime >themselves.... Am I right? >S.T.L. >________________________________________________________________ >Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm > ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ Date: Tue, 22 Jun 1999 21:51:57 -0400 (EDT) From: lrwiman <[EMAIL PROTECTED]> Subject: re: Mersenne: Testing for factors ><<Now we can filter out multiples of small primes>> >I'm assuming that we don't need to divide by factors divisible by 3 or 5, >etc, because a Mersenne number cannot be divisible by 3 or 5 because they >don't have the structure 2kp+1 themselves? (Excluding the REALLY low Mersenne >numbers). Ideally, we'd like to only test factors that are prime >themselves.... Am I right? If I understand you, then you are asking if we ever need to test mersenne numbers for divisibility by 3 or 5. These factors are never considered because they are not of the form 2*k*p+1, so on that regard you are correct. However, he is talking about testing potential factors *of mersenne numbers* for divisibility by such small primes. If you reread Brian's seive code you will see that here is what he is doing: he creates an array of 3*5*7*11*13*17=255255 elements. Then he eliminates every 3rd, 5th, 7th, 11th, 13th, and 17th element. Therefore, he can any number mod 255255 whose remainder wasn't eliminated in the seiving is not divisible by 3, 5, 7, 11, 13, or 17. We can also use the value p mod 255255 to allow us to find the value (2*k*p+1) mod 255255 (since a*b mod c is equal to (a mod c)*(b mod c) mod c). So, we can precompute multiples of p mod 255255, and add them based on the sieve table. - -Lucas Wiman ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ Date: Tue, 22 Jun 1999 22:15:26 -0400 (EDT) From: lrwiman <[EMAIL PROTECTED]> Subject: Re: Mersenne: Testing for factors >No two Mersenne primes can have the same prime divisor, as I recall. So by >listing the composite Mersenne primes (i.e., p is prime but 2^p -1 is not >prime), we can get a list of primes that no longer need to be tried as >divisors of 2^p - 1. So sure, use the +/-1 mod 8 rules, eliminating a >series of trial divisors, and pare the list even more by comparing to known >divisors of Mersenne primes. I don't think this would be very effective for the simple reason that it would take longer to read from disk than it would to just check the factor. >These prime divisors would presumably be in a database. It is possible to do this using methods like Chris Nash's PriMers method. In this, you calculate all the prime numbers ==+/-1 mod 8 up to a certain point. Then you can factor that prime-1, and test the mersenne exponents that are factors. - -Lucas Wiman ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ Date: Wed, 23 Jun 1999 06:17:45 +0100 From: "Brian J. Beesley" <[EMAIL PROTECTED]> Subject: Re: Mersenne: Testing for factors On 22 Jun 99, at 20:30, [EMAIL PROTECTED] wrote: > <<Now we can filter out multiples of small primes>> > I'm assuming that we don't need to divide by factors divisible by 3 or 5, > etc, because a Mersenne number cannot be divisible by 3 or 5 because they > don't have the structure 2kp+1 themselves? (Excluding the REALLY low Mersenne > numbers). Actually you've missed the obvious point. The smallest factor of _any_ number is prime. So we've no need to test any candidate factors which are "obviously" composite (i.e. we can see easily that they're divisible by any small prime). And, if p is prime, we know (mathematically) that the smallest possible factor of 2^p-1 is 2p+1. So 2^p-1 cannot be divisible by _any_ prime < 2p. > Ideally, we'd like to only test factors that are prime > themselves.... Am I right? Yes. But you have to balance out the effort involved in finding out whether the candidate factor is probably prime against the effort involved in doing a trial division. I can do a trial division of 2^p-1 by f for any p < 2^32, f < 2^63 in 10 microseconds or less on a PII-350. Checking whether f is _really_ prime is going to take a lot longer than that, unless you have a 2^63 bit lookup table lying about somewhere in RAM ;-) e.g. consider a Fermat test to base 2 (which is a long way from proving primality, though it's a good first guess). We need to compute 2^((2kp+1)-1) (mod 2kp+1). But, to check divisibility of 2^p-1 by 2kp+1, we only need to compute 2^p (mod 2kp+1), which is obviously less effort! Regards Brian Beesley ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ Date: Wed, 23 Jun 1999 06:17:45 +0100 From: "Brian J. Beesley" <[EMAIL PROTECTED]> Subject: Re: Mersenne: Once again factoring On 22 Jun 99, at 17:38, Gary Diehl wrote: > > 1. Why only put the first six prime numbers in the sieve table? (Don't > you want to eliminate other prime numbers too, or am I missing a bigger > issue here?) For a 1-pass sieve table, the table size is the product of the numbers you're sieving out. 3 * 5 * 7 * 11 * 13 * 17 = 255255, which seems a reasonable table size, whereas 19 times that size is getting a bit large, and 19 * 23 times that size is too damn big to fit in memory on (most) current PC systems. Each extra prime sieved for eliminates 1/pth of the remaining candidate factors. So, as p gets bigger, the "gain" gets progressively smaller, whilst the "pain" involved increases. Eventually you arrive at a balance. Whilst keeping memory requirements reasonable, we could build a second stage sieve to eliminate the primes 19, 23, 29 & 31 in a second table of size 392863. Doing this would eliminate about 15% of the candidates remaining from the first pass, whereas the first pass eliminates about 64%. Apart from the memory cost, we'd also need to keep track of 2kp+1 (mod 392863) as well as of 2kp+1 (mod 255255). If this takes more than 1/6th of the time to do the trial division, it's not worth it. (Actually it almost certainly _is_ worth it - though a third stage would be of dubious value. I was trying to illustrate the sieving procedure without complicating things too much.) > > 2. Why use a table at all? Is it faster than doing a calculation to > determine if [f % 255255] != 0 ? (I know sometimes tables can speed > things up, but does it really help with so few numbers involved in the > table?) > I know the factors I'm looking at are of the form 2kp+1. So, if I have a candidate factor f and I know x = f (mod 255255), I can generate the next index into the table by adding 2p (mod 255255) to x and taking the modulus again. Note that 2p (mod 255255) is fixed so I only need to calculate this once. And, because x < 255255 and 2p (mod 255255) < 255255, x + 2p (mod 255255) < 2 * 255255, so all I need to do to reduce to mod 255255 again is to subtract 255255 if the result is >= 255255. This is a lot quicker than doing the modulus operation again (which has an implied division - and don't forget that f is usually bigger than the word size, so you're straight into multi- precision arithmetic - whereas the index manipulation fits easily into a 32 bit word). Once you have the index, the table lookup is essentially instantaneous. On a Pentium, recalculating the index & looking up the table takes of the order of 20 clocks (allowing for a cache miss on the table read), irrespective of the size of f, whereas just dividing f by 255255 to get the remainder costs 39 clocks, even if f/255255 < 2^32. > I guess i'm still kinda clueless as to why LL factoring is done this > way. > As usual, there's more than one way to skin the cat. The method I've outlined seems to be reasonably quick. If you can find a faster way, tell us about it! Regards Brian Beesley ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ Date: Wed, 23 Jun 1999 01:23:27 -0400 From: Chris Nash <[EMAIL PROTECTED]> Subject: Re: Mersenne: Testing for factors > >No two Mersenne (numbers) can have the same prime divisor, as I recall. Yes, every odd prime *belongs* to a given Mersenne exponent x, (the exponent of 2 mod p). Then p divides 2^n-1 if and only if x divides n. x certainly divides p-1, but x may not necessarily be a prime. > >prime), we can get a list of primes that no longer need to be tried as > >divisors of 2^p - 1. So sure, use the +/-1 mod 8 rules, eliminating a > >series of trial divisors, and pare the list even more by comparing to known > >divisors of Mersenne primes. > I don't think this would be very effective for the simple reason that it would > take longer to read from disk than it would to just check the factor. Almost definitely. If we have a candidate prime divisor, X=2kp+1, we'd have to look for all the entries for the divisors of 2k in a database, while the value of 2^p-1 mod X can be calculated in about two dozen squarings and shifts (mod X). > It is possible to do this using methods like Chris Nash's PriMers method. > In this, you calculate all the prime numbers ==+/-1 mod 8 up to a certain > point. Then you can factor that prime-1, and test the mersenne exponents that > are factors. That's the theory. Given a prime p, find x above. The algorithm is not too difficult get an admissible prime (+-1 mod 8) begin with x=p-1 for every prime factor q of x, test 2^(x/q) mod p. If it's one, then replace x by x/q and repeat. If none of these are 1, then x is the exponent to which p belongs. x however is very rarely much smaller than p-1 - I'll leave a full analysis to others, but typically you'll see (p-1), (p-1)/2, maybe a few others, but rarely much smaller. (To be (p-1)/d, 2 would have to be a d'th root of unity, and the probability of that is "about" 1/d). For even a 32-bit prime, the probability it belongs to an exponent in the current search range (2^23) is very small indeed (1000 to 1?), not to mention of course that the exponent it belongs to will probably be composite. While testing is quite quick, expect to scan many thousands of primes before you get an 'interesting' factor this way (even more with larger factors). In theory it's quicker than testing the same prime a handful of times for many different exponents, but in practice it generates many results for composite exponents, or huge exponents, which we may not necessarily be interested in - at least, not for a long time. I have a very silly result somewhere that M(some 62-bit exponent) is composite with a known factor - the Mersenne number itself would have 10^18 digits... Chris Nash ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ Date: Wed, 23 Jun 1999 01:42:08 PDT From: Alan Simpson <[EMAIL PROTECTED]> Subject: Mersenne: this 3/2 conjecture and a result of Wagstaff hi everyone, there have been several messages lately about this conjecture that the n-th Mersenne prime is "around" (3/2)^{n}. However, no one seems to have mentioned Wagstaff's paper in Math. Comp. (1982 or 1983). He shows two things in this paper. (1)he shows that an earlier conjecture of Gilles (??) (something like the n-th Mersenne prime is "around" 2^{n} -- I can't remember what his base in this exponential expression was) runs contrary to known results concerning the distribution of primes. (2)he also gives a heuristic argument that the n-th Mersenne prime is "around" e^{gamma*n), where gamma is Euler's constant= 0.57721... I realise that some of you have tried to find a "best-fit" value for this base and that so far it appears near 3/2. But do people have any mathematical arguments (a la heuristic of Wagstaff) for supporting this 3/2 value? And a pile of other related questions that I can't articulate this early in the morning. Alan Simpson _______________________________________________________________ Get Free Email and Do More On The Web. Visit http://www.msn.com ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ Date: Wed, 23 Jun 1999 02:08:12 PDT From: Alan Simpson <[EMAIL PROTECTED]> Subject: Mersenne: re: the 3/2 conjecture and a paper of Wagstaff hi, I'm sure that you all have calculators (hell, you all have some serious PC's!), but e^{gamma} is approximately 1.781. Maybe that was unnecessary, Alan Simpson _______________________________________________________________ Get Free Email and Do More On The Web. Visit http://www.msn.com ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ Date: Wed, 23 Jun 1999 12:34:56 -0700 From: Lang Pal <[EMAIL PROTECTED]> Subject: Re: Mersenne: Mersenne 3/2 conjecture I agree - if and only if - one throws in a pi or an e - without any mathematical reason. I draw your kind attention to the quotation in my letter regarding the Hardy-Ramanujan-Rademacher formula. Besides I mention, the recommended modification is a better approximation as 3/2 and almost just the same as the Jud Mc Cranie's other number. Regards Paul La'ng Budapest, Hungary Aaron Blosser wrote: > > Well, we're dealing with experimental data, and both look about > > equally good. On balance I prefer the argument with pi in it. Pi > > deserves a place in most fundamental laws... > > > > (Much waving of arms ... obviously a beautiful solution isn't always > > right) > > Besides, any equation just looks much cooler if you throw in a pi or an e or > something. Just the word "transcendental" makes an equation seem > otherworldly! :-) > > ________________________________________________________________ > Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ Date: Wed, 23 Jun 1999 14:11:20 -0700 From: Lang Pal <[EMAIL PROTECTED]> Subject: Re: Mersenne: this 3/2 conjecture and a result of Wagstaff Alan Simpson wrote: > hi everyone, > > there have been several messages lately about this conjecture that the n-th > Mersenne prime is "around" (3/2)^{n}. > > > (1) > However, no one seems to have mentioned Wagstaff's paper in Math. Comp. > (1982 or 1983). > ... > (2) > . But do people have any > mathematical arguments (a la heuristic of Wagstaff) for supporting this 3/2 > value? And a pile of other related questions that I can't articulate this > early in the morning. > > Alan Simpson > > > Ad 1) Really, I did not read Wagstaff's paper. I shall try to retrieve. > Ad 2) Denoting by > S(n) =the sum of divisors of the natural number "n", > P(n)= the partition function of the natural number "n" > and E(n) = the Euler-coefficients of the famous Euler formula > > it is known that n > ------ > S(n)= \ E(i)*P(n-i) > / > ------ > i=1 > (the so-called Cauchy multiplication) > So the S(n) function , - and therefore the Mersenne problem, too - is somehow > in relation with the partition function. The quoted > Hardy-Ramanujan-Rademacher formula contains the "PI*SQRT(2)/3" > expression. > I know, other factors should be found, and I hope, someone would. Regards Paul La'ng Budapest, Hungary > > _______________________________________________________________ > Get Free Email and Do More On The Web. Visit http://www.msn.com > ________________________________________________________________ > Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ Date: Wed, 23 Jun 1999 10:54:19 -0400 From: Jud McCranie <[EMAIL PROTECTED]> Subject: Re: Mersenne: this 3/2 conjecture and a result of Wagstaff At 01:42 AM 6/23/99 -0700, Alan Simpson wrote: > >there have been several messages lately about this conjecture that the n-th >Mersenne prime is "around" (3/2)^{n}. > >However, no one seems to have mentioned Wagstaff's paper in Math. Comp. >(1982 or 1983). > >He shows two things in this paper. > >(1)he shows that an earlier conjecture of Gilles (??) (something like the >n-th Mersenne prime is "around" 2^{n} -- I can't remember what his base in >this exponential expression was) runs contrary to known results concerning >the distribution of primes. I was aware of Gilles conjecture about 20 or 21 years ago when I graphed them and saw that 3/2 was a much better fit, but I'm not aware of Wagstaff's paper. Anyhow, both of these are reasons for expecting an infinite number of Mersenne primes (and there may be others). >(2)he also gives a heuristic argument that the n-th Mersenne prime is >"around" e^{gamma*n), where gamma is Euler's constant= 0.57721... > >I realise that some of you have tried to find a "best-fit" value for this >base and that so far it appears near 3/2. But do people have any >mathematical arguments (a la heuristic of Wagstaff) for supporting this 3/2 >value? There's no heuristic argument that I know of for 3/2 (it just fits known data well). Wagstaff's equation is a vast overestimate for small n, but maybe better for large n, or an upper bound. +----------------------------------------------+ | Jud "program first and think later" McCranie | +----------------------------------------------+ ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ Date: Wed, 23 Jun 1999 10:23:35 -0400 From: Jud McCranie <[EMAIL PROTECTED]> Subject: Re: Mersenne: Testing for factors At 01:23 AM 6/23/99 -0400, Chris Nash wrote: >x however is very rarely much smaller than p-1 - I'll leave a full analysis >to others, but typically you'll see (p-1), (p-1)/2, maybe a few others, but >rarely much smaller. That's right. +----------------------------------------------+ | Jud "program first and think later" McCranie | +----------------------------------------------+ ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ Date: Wed, 23 Jun 1999 10:19:17 -0400 From: Jud McCranie <[EMAIL PROTECTED]> Subject: Re: Mersenne: Testing for factors At 06:17 AM 6/23/99 +0100, Brian J. Beesley wrote: > Checking whether f is _really_ prime is going to take a lot >longer than that, unless you have a 2^63 bit lookup table lying about >somewhere in RAM ;-) I've got one for up to 2^32. That really helps on some things. +----------------------------------------------+ | Jud "program first and think later" McCranie | +----------------------------------------------+ ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ Date: 23 Jun 99 09:27:15 MDT From: Paul Derbyshire <[EMAIL PROTECTED]> Subject: Re: Mersenne: Testing for factors "Vincent J. Mooney Jr." <[EMAIL PROTECTED]> wrote things like: > No two Mersenne primes can have the same prime divisor... > ...listing the composite Mersenne primes... etc. Don't let this happen to you. While some people may be able to post news at all hours of the day and night, others have Fatigue Associated Incoherent Posting Susceptibility Syndrome. FAIPSS sufferers should refrain from posting between the hours of midnight and 11 am, or there may be tragic consequences, as Vincent J. Mooney, Jr., demonstrates. :-) ____________________________________________________________________ Get free e-mail and a permanent address at http://www.netaddress.com/?N=1 ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ Date: Wed, 23 Jun 1999 12:40:28 -0500 From: "Willmore, David" <[EMAIL PROTECTED]> Subject: RE: Mersenne: Testing for factors Uhh, yeah, I've got a 2^32 one, too and I can *make* any arbitrary part of a 2^64 one fairly quickly. :) > ---------- > From: Jud McCranie[SMTP:[EMAIL PROTECTED]] > Sent: Wednesday, June 23, 1999 9:19 AM > To: Brian J. Beesley > Cc: [EMAIL PROTECTED]; [EMAIL PROTECTED] > Subject: Re: Mersenne: Testing for factors > > At 06:17 AM 6/23/99 +0100, Brian J. Beesley wrote: > > Checking whether f is _really_ prime is going to take a lot > >longer than that, unless you have a 2^63 bit lookup table lying about > >somewhere in RAM ;-) > > I've got one for up to 2^32. That really helps on some things. > > +----------------------------------------------+ > | 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: Wed, 23 Jun 1999 14:36:02 -0400 From: Jud McCranie <[EMAIL PROTECTED]> Subject: RE: Mersenne: Testing for factors At 12:40 PM 6/23/99 -0500, Willmore, David wrote: >Uhh, yeah, I've got a 2^32 one, too and I can *make* any arbitrary part of a >2^64 one fairly quickly. :) How about any arbitrary LARGE part of 2^64, stored in RAM? That would be really nice. :-) +----------------------------------------------+ | Jud "program first and think later" McCranie | +----------------------------------------------+ ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ Date: 23 Jun 99 13:14:11 MDT From: Paul Derbyshire <[EMAIL PROTECTED]> Subject: Re: Mersenne: Finite or infinite? "Steinar H. Gunderson" <[EMAIL PROTECTED]> wrote: > My other (a PII/448) is currently... 448? That looks like the kind of MHz number that results from some kind of an overclock... ____________________________________________________________________ Get free e-mail and a permanent address at http://www.netaddress.com/?N=1 ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ Date: Wed, 23 Jun 1999 19:41:21 GMT From: [EMAIL PROTECTED] (Steven Whitaker) Subject: Re: Mersenne: this 3/2 conjecture and a result of Wagstaff On Wed, 23 Jun 1999 01:42:08 PDT, you wrote: > >hi everyone, > >there have been several messages lately about this conjecture that the n-th >Mersenne prime is "around" (3/2)^{n}. > >However, no one seems to have mentioned Wagstaff's paper in Math. Comp. >(1982 or 1983). > >He shows two things in this paper. > >(1)he shows that an earlier conjecture of Gilles (??) (something like the >n-th Mersenne prime is "around" 2^{n} -- I can't remember what his base in >this exponential expression was) runs contrary to known results concerning >the distribution of primes. > >(2)he also gives a heuristic argument that the n-th Mersenne prime is >"around" e^{gamma*n), where gamma is Euler's constant= 0.57721... > >I realise that some of you have tried to find a "best-fit" value for this >base and that so far it appears near 3/2. But do people have any >mathematical arguments (a la heuristic of Wagstaff) for supporting this 3/2 >value? And a pile of other related questions that I can't articulate this >early in the morning. > >Alan Simpson > Of course, if you want a better match, you could try combining the two: the n-th Mersenne prime is "around" e^(2/3*gamma*n). That gives a base of approximately 1.469. Note - I have no mathematical arguments for this whatsoever. :-) Cheers Steve Whitaker ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ Date: Wed, 23 Jun 1999 22:32:19 +0200 From: "Lars Lindley" <[EMAIL PROTECTED]> Subject: SV: Mersenne: Finite or infinite? - ---- Original Message ----- From: Paul Derbyshire <[EMAIL PROTECTED]> > 448? That looks like the kind of MHz number that results from some kind of an > overclock... > Yep... A PII-400 run at 112 MHz bus renders a speed like that. Forgive my laziness for not looking through the 300+ messages from the last two weeks, but why are you noting that? Just curious... :) /Lars ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ Date: Wed, 23 Jun 1999 15:26:31 -0600 From: "Jason Vallery" <[EMAIL PROTECTED]> Subject: Re: SV: Mersenne: Finite or infinite? > > 448? That looks like the kind of MHz number that results from some > kind of an > > overclock... Maybe he just has a lazy PII-450.. (Im joking) ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ Date: Thu, 24 Jun 1999 00:24:33 +0200 From: "Steinar H. Gunderson" <[EMAIL PROTECTED]> Subject: Re: Mersenne: Finite or infinite? On Wed, Jun 23, 1999 at 01:14:11PM -0600, Paul Derbyshire wrote: >448? That looks like the kind of MHz number that results from some kind of an >overclock... Yes. 112 MHz bus, 4x multiplier. (Don't worry, I get the same results & temperature at 4x100MHz...) /* Steinar */ ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ Date: Wed, 23 Jun 1999 17:58:07 -0400 From: George Woltman <[EMAIL PROTECTED]> Subject: Mersenne: M#38 Hi all, Thanks to Ernst Mayer's fine program and David Willmore's generous donation of Alpha CPU time, the first verification of M#38 is complete. As expected, the new prime has been confirmed. I'll keep you posted on the schedule for publishing this exciting new find. As of now the editor of the Bulletin of the AMS has expressed some interest. Now that M#38 is verified I'll talk with him some more. Now, on to M#39.... George ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ Date: Wed, 23 Jun 1999 17:21:13 -0700 (PDT) From: poke <[EMAIL PROTECTED]> Subject: Mersenne: Side Effect Hello, This is slightly off topic so please bare with me. A side effect of having Gimps on your computer is improved security. I have mine configured to be a tray icon, which generally goes unnoticed or is ignored. If someone were to steal my laptop (assuming they didn't reformat my hard drive), eventually when they are "surfing" the net, Gimps will report results back to the Primenet server. The primenet logs should show where the perp is connecting to the net. From there, server logs at the ISP should be sufficient to start some sort of trace. - -Chuck -- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ : WWW: http://www.silverlink.net/poke : : E-Mail: [EMAIL PROTECTED] : ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ : Ask Mike! Aviation's response to Dear : : Abby. http://www.avstarair.com : ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ Date: Thu, 24 Jun 1999 01:36:54 -0400 (EDT) From: lrwiman <[EMAIL PROTECTED]> Subject: Re: Mersenne: Once again factoring > Whilst keeping memory requirements reasonable, we could build a > second stage sieve to eliminate the primes 19, 23, 29 & 31 in a > second table of size 392863. Doing this would eliminate about 15% of > the candidates remaining from the first pass, whereas the first pass > eliminates about 64%. Apart from the memory cost, we'd also need to > keep track of 2kp+1 (mod 392863) as well as of 2kp+1 (mod 255255). If > this takes more than 1/6th of the time to do the trial division, it's > not worth it. (Actually it almost certainly _is_ worth it Remember, adding more primes only seives out those with those new primes as their *lowest* divisor. Thus adding the second seive table would eliminate around 5%, not 15%. In other words, 1-(2*4*6*10*12*16*18*22*28*30)/(3*5*7*13*17*11*19*23*29*31)!=(1-\ (2*4*6*10*12*16)/(3*5*7*13*17*11))+(1-(18*22*28*30)/(19*23*29*31)) So, it would have to be faster than 1/20th of the trial division time, rather than 1/6th. - -Lucas Wiman ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ Date: Thu, 24 Jun 1999 01:45:05 PDT From: Alan Simpson <[EMAIL PROTECTED]> Subject: Re: Mersenne: this 3/2 conjecture and a result of Wagstaff hi again, >From: Jud McCranie <[EMAIL PROTECTED]> >To: Alan Simpson <[EMAIL PROTECTED]> >CC: [EMAIL PROTECTED] >Subject: Re: Mersenne: this 3/2 conjecture and a result of Wagstaff >Date: Wed, 23 Jun 1999 10:54:19 -0400 > >There's no heuristic argument that I know of for 3/2 (it just fits known >data >well). Wagstaff's equation is a vast overestimate for small n, but maybe >better for large n, or an upper bound. > If Wagstaff's heuristic is valid (and number theorists do seem to find it convincing --- take that statement with handful of caution, after all mathematics is about proofs not heuristics), then asymptotically the n-th Mersenne prime should get closer and closer to e^(gamma*n). Again, if true, this means that the 3/2 conjecture would become a progressively worse and worse approximation. As a number theorist, I would guess that the reason why e^{gamma*n) is not such a good approximation (is this really true?) for the Mersenne primes that we have seen so far is because of lower order terms. It is clearly not the case that the exponent of the n-th Mersenne prime is not (3/2)^P{n} or e^(gamma*n), but something like c^{n+o(n)), where "o(n)" is the usual "little-o of n" (lim_{n \rightarrow \infty} o(n)/n = zero (a severe abuse of notation in that limit!). Do we have enough data to make any sensible guesses about the nature of this "o(n)" term? And another question, how does this linear curve (the term in the exponential is linear in n, I mean) that people seem to want to attach to the growth of the exponent of the n-th Mersenne prime change as n grows. Could it be that if you look at the first 5 primes, and then the first 10 primes, etc., that the slopes are changing in some consistent manner? Perhaps going to some limit? I guess this last question gets back to Jud McCraine's (and others') point that it looks like (3/2)^{n}. Alan Simpson _______________________________________________________________ Get Free Email and Do More On The Web. Visit http://www.msn.com ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ Date: Thu, 24 Jun 1999 08:32:26 -0400 From: Jud McCranie <[EMAIL PROTECTED]> Subject: Re: Mersenne: this 3/2 conjecture and a result of Wagstaff At 01:45 AM 6/24/99 -0700, Alan Simpson wrote: > >It is clearly not the case that the exponent of the n-th Mersenne prime is >not (3/2)^P{n} or e^(gamma*n), but something like c^{n+o(n)), where "o(n)" >is the usual "little-o of n" (lim_{n \rightarrow \infty} o(n)/n = zero (a >severe abuse of notation in that limit!). > >Do we have enough data to make any sensible guesses about the nature of this >"o(n)" term? Not at this point. The data has always provided a very good fit to something around 1.5. Here's the data: N Best fit Correlation coefficient 2 1.50000 1.0000 3 1.58114 0.9978 4 1.53252 0.9972 5 1.58263 0.9964 6 1.55430 0.9966 7 1.49068 0.9885 8 1.47602 0.9913 9 1.49766 0.9928 10 1.50665 0.9946 11 1.49615 0.9954 12 1.47691 0.9944 13 1.51560 0.9892 14 1.52890 0.9908 15 1.54999 0.9909 16 1.56791 0.9914 17 1.56752 0.9928 18 1.56434 0.9938 19 1.55793 0.9944 20 1.54433 0.9938 21 1.54132 0.9945 22 1.53166 0.9944 23 1.51928 0.9936 24 1.51220 0.9938 25 1.50214 0.9933 26 1.48995 0.9921 27 1.48331 0.9923 28 1.48093 0.9930 29 1.47755 0.9934 30 1.47278 0.9936 31 1.46983 0.9940 32 1.47466 0.9943 33 1.47661 0.9948 34 1.47817 0.9952 35 1.47747 0.9956 36 1.47932 0.9959 37 1.47850 0.9962 > >And another question, how does this linear curve (the term in the >exponential is linear in n, I mean) that people seem to want to attach to >the growth of the exponent of the n-th Mersenne prime change as n grows. > >Could it be that if you look at the first 5 primes, and then the first 10 >primes, etc., that the slopes are changing in some consistent manner? See the above. For the known data, Wagstaff's estimate, exp(gamma*n), grows progressively worse. (The ratio should be -> 1.) Is there another constant in the estimate I've omitted? Of course, as the candidate exponents thin out, it may become accurate. N Actual Est Ratio 1 2 2 0.89 2 3 3 1.06 3 5 6 1.13 4 7 10 1.44 5 13 18 1.38 6 17 32 1.88 7 19 57 2.99 8 31 101 3.27 9 61 180 2.96 10 89 321 3.61 11 107 572 5.35 12 127 1019 8.02 13 521 1815 3.48 14 607 3233 5.33 15 1279 5757 4.50 16 2203 10254 4.65 17 2281 18264 8.01 18 3217 32529 10.11 19 4253 57936 13.62 20 4423 103189 23.33 21 9689 183786 18.97 22 9941 327337 32.93 23 11213 583010 51.99 24 19937 1038384 52.08 25 21701 1849437 85.22 26 23209 3293981 141.93 27 44497 5866818 131.85 28 86243 10449228 121.16 29 110503 18610831 168.42 30 132049 33147238 251.02 31 216091 59037631 273.21 32 756839 105150296 138.93 33 859433 187280292 217.91 34 1257787 333559763 265.20 35 1398269 594094094 424.88 36 2976221 1058124604 355.53 37 3021377 1884596547 623.75 +----------------------------------------------+ | Jud "program first and think later" McCranie | +----------------------------------------------+ ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ Date: Thu, 24 Jun 1999 07:33:57 PDT From: Alan Simpson <[EMAIL PROTECTED]> Subject: Re: Mersenne: this 3/2 conjecture and a result of Wagstaff hi again, seeing this makes me think that maybe I have misremembered the result in Wagstaff's paper. Can anyone actually look it up and see what he "really" says. Alan "who's perhaps not as knowledgeable on this matter as he thought" Simpson _______________________________________________________________ Get Free Email and Do More On The Web. Visit http://www.msn.com ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ Date: Thu, 24 Jun 1999 08:02:09 -0700 From: "Herr, Stephen" <[EMAIL PROTECTED]> Subject: Mersenne: Date: Thu, 24 Jun 1999 09:01:14 -0600 (Sorry, messed up a key strok and sent my last message before I was ready.) For the last day I have received : ERROR: Primenet error: 12029 Can someone help me with the meaning of this particular message. I do work behind a proxy server but have never had a problem using the http connection to primenet. ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ Date: Thu, 24 Jun 1999 08:02:38 -0700 From: "Herr, Stephen" <[EMAIL PROTECTED]> Subject: Mersenne: Date: Thu, 24 Jun 1999 08:59:17 -0600 For the last day I have received : ERROR: Primenet error: 12029 Can someone help me with the meaning of this particular message. I do work behind a proxy server but have never ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ Date: Thu, 24 Jun 1999 12:13:47 -0400 From: Jud McCranie <[EMAIL PROTECTED]> Subject: Mersenne: safe to defrag? Since Prime95 writes to the disk periodically, is it safe to do a disk defragmentation while it is running? +----------------------------------------------+ | Jud "program first and think later" McCranie | +----------------------------------------------+ ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ End of Mersenne Digest V1 #587 ******************************
