Re: Mersenne: Re: PNG (good!)
>> Version Visitors % >>1. MSIE 5.x1,70553.26 >>2. Netscape 4.x1,17336.63 >>3. MSIE 4.x2247.00 >>4. MSIE 5.x (AOL)541.69 >>5. Netscape 3.x120.37 >>6. MSIE 3.x100.31 >>7. Netscape 5.x80.25 >>8. MSIE 4.x (AOL)50.16 >>9. MSIE 2.x40.12 >>10. MSIE 3.x (AOL)40.12 >>11. Opera 3.x20.06 >>12. Opera 2.x10.03 >> >> Total 3,202 100.00% > >Apparently broken statistics, since at least one of the browsers I >regularly >visit with isn't represented. If you are referring to Lynx, then it may be that Lynx has deceived the webserver. If I recall correctly Lynx (at least of a few versions ago) told webservers that it was netscape to avoid the server not sending the page. Possibly, anyway... -Lucas Send your favorite photo with any online greeting! http://www.whowhere.lycos.com/redirects/americangreetings.rdct _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.exu.ilstu.edu/mersenne/faq-mers.txt
Mersenne: the Mersenne Faq has moved
The FAQ of the mersenne mailing list has moved to http://www.exu.ilstu.edu/mersenne/faq-mers (or faq-mers.txt). The old adress will continue to work until the 18th. Sorry for the trouble, Lucas P.S. Luke, could you please tell Gordini to change the line at the end of each message. Again, sorry for the trouble. _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Re: Mersenne Digest V1 #753
> > I have to agree... You can never have your case or chip -too- cold ... > I've > > seen that same article too. > > sure you can. chilling the CPU below the point of condensation will cause > corrosion. Chilling it further below freezing will turn the whole thing > into a ball of ice. Hmm. This depends what atmosphere you have it in. You could have it submerged in liquid nitrogen or helium and then condensation wouldnt be a problem. As to the running of the chip at low temps, my guess would be that at microkelvins, the transistors would stop switching. Eventually nothing could occurr at all. > The chip maker specifies a maximum AND minimum operating temperature within > which they guarantee the chips timing specs. stray too far from these > limits in either direction can/will cause problems. I think people who chill their chips in liquid nitrogen aren't worried about what the chip manufacturors said the chip can do since what their doing isn't covered by the chip manufacturor in any way (=non prescribed usage). You technically aren't supposed to overclock at all, but many people do with no problems. -Lucas Wiman _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: GIMPS in Science News
> Precisely. I hope a serious discussion, short of a "war," can be ignited, > although perhaps GIMPS is not the proper forum. George and > and the other pioneers and principals might weigh in on this. The "listening" > SETI group, not the astro-physicist community searching for Earth-like planets, > seems a bit lunatic fringe. I agree, the logistics of them sending a message to Earth and us recieving it seem, well, a bit out of this world. :) In this case they are not hurting us though. It may seem that they are, but my guess would be that the number of people that switched from GIMPS to SETI@Home is small. It's not like we would have a million people giving us their CPU power were it not for SETI. All in all, SETI is probably a benefit. Think of the number of articles about SETI@Home that also incidentally mention GIMPS (I can think of at least 2 in the last month alone...). This probably helps us recruit members. -Lucas _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Dumb Newbie Question
> On Wed, 8 Mar 2000, Brian J. Beesley wrote: > > > 0.729. However, random events like finding factors, arrival of buses, > > airplane crashes etc. always seem to arrive in bunches. I've had a > finding factors only seems to come in cluster, but the other two does > haver mechanisms that does make them actually cluster up. > > Bus arrival clustering is cause by a well known positive feedback > mechanism since any difference in the interval between busses will cause > more passenres to arrive at the stops before the late bus, making it even > later. Only way to prevent this is to include pauses in each bus's > schedule, but traffic plannners seem to be too stupid to understand this > and tries to do it with tighter schedules instead. With regards to factoring, if prime finds a factor then it can start on another one more quickly increasing the factors found per time. -Lucas Wiman > _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: pi
> > At 10:50 AM 2/9/00 -0500, Jeff Woods wrote: > > >You're bumping up against the Fundamental Theorem of Calculus here. Pi > > >DOES have a precisely defined value, but you cannot express it in decimal > > > >form. You can express it as an infinite expansion, however. Q: What does this have to do with fundamental theorem of calculus? The fundamental theorem equates anti-derivitives with area. This has more to do with the proof that there are numbers which cannot be expressed as the ratio of integers (i.e. irrational numbers) due originally to pythagroeus (SP), as well as the proof of the irrationality of pi (due to Newton, I think). The first is proved *long* before the fundamental theorem, and is in some ways more fundamental. -Lucas _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Re: P-1 factoring
> Will this P-1 factoring step take place ONLY before a LL test, or will it > also be part of the trial factoring step? > > The reason why I'm asking is because one of my machines is a dedicated 486 > to work on trial factoring only. It has 16MB RAM. The hard disk is *very* > slow, so when it thrashes, my 486 is essentially rendered useless. The P-1 step would become a fourth work assignment (to be done after a number has been trial factored, but before it has had an LL test run on it). Much like how the trial factoring and LL test are done on separate computers. -Lucas Wiman _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Re: Odds on finding a factor
> >Who needs to? I have code which tries any number up to 2^95 as a > factor of a Mersenne number with an exponent up to approx. 600 > million, using less than 1 KByte of code space and 32 bytes of data > storage. It executes in a time proportional to the logarithm of the > exponent - for an exponent around 35 million, it takes approximately > 2000 CPU clocks i.e. 4 microseconds per test on a 500 MHz CPU. This is a bit misleading, more accuratly, it runs in time proportional to lg(p)*lg^2(n), where p is the exponent, and n is the potential factor. Just call me "Mr. Pedantic". :) -Lucas Wiman _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Q:GIMPS freezes my system
> Hi there, I've experienced a problem. I'm wondering if anyone else has had > this problem: > > GIMPS freezes my system after it runs for about 24 hours or so. > > I have Windows NT 4.0 (SP5) > Dual Intel Celeron 433Mhz (BP6 motherboard) > 128MB RAM > > If I quit both GIMPS processes on my machine (and I'm running one with the > -A2 command-line option) and start them again, no problems. It's only after > both have been running for some time. But I don't want to do this because I > leave my computer for days at a time. > It sounds like you might have problems with overheating in the case which can often cause lockups, since Prime95 stresses the CPU more, it produces more heat. I would advise getting a case fan. Just my $0.00 (the GNU version) -Lucas _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Re : Odd's on finding a factor (part 2)
> Thus for the exponent 1165 bits long, if it only has 2 factors , then the first >factor must be between 2 and 3413 bits long, and the second factor must be between >3413 and 1164 bits long. Note that the bit lengths of the 2 factors added >together must equal the bit length of the Prime (or bit length of the Prime + 1) !! No, if the exponent=1165 (I think this is what you mean), the mersenne number must be this number of bits (as you know). The first factor must be less than sqrt(M_p), not M_(sqrt(p)), which is what you were doing. The first factor must therefore be less than 2^(p/2)=2^5825000>2^sqrt(1165)~=2^3413. > > You would probably get better results with Will Edgington's mersfacgmp > program, and DJGPP (a port of g++ to dos). > > I'll check it out. I'm using UBASIC because for testing factors of large Mersenne, I >don't need to actually represent the full Mersenne Prime. If you're familiar with >UBASIC try ... > > Result = MODPOW(2,MersenneExponent,TrialFactor) > > where TrialFactor is the MersenneExponent * 2 * (some k in range 1 to 2^16) + 1. > > If Result = 1 then TrialFactor divides the Mersenne Prime. As UBASIC can handle >around 2600 decimal digits, in theory (and with a lot of time), I could check all >factors up to 2600 decimal digits for any given exponent. It's a damn sight faster >than filling 16MB+ of memory with 1's and then trial dividing. Will's program does this also (see Knuth volume II (I think 4.5.3, but I'm not sure don't have my copy handy), or the mersenne FAQ at the bottom of this message). Thinking on it in a slightly more awake state, I'm not sure how much faster it would be, but try it anyway. You will need to download DJGPP (search altavista for DJGPP), set it up, compile the GMP library (ftp://metalab.unc.edu/gnu/gmp (I think), there is a dos batch file), and compile Will's program (I think it is in the links section of the mailling list FAQ). But, under windows, would George's program be the fastest (or are you using very large exponents?) Have fun, Lucas Wiman _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Re: Mersenne: Odds on finding a factor ?
> If you're factoring numbers in the 1165-1166 (bit) range, the first factor >could be anywhere in the root(1165) - root(1166) range i.e. 3413 - 3414 bits >long !! No, in the x-y bit range (remember that n bit integers are about 2^n) the first factor could be x/2 to y/2 bits long (powers of a power multiply). > I'd have thought your odds of finding a factor are a lot smaller than 12 / 64 - >probably closer to 12/3361 - and that's only if we pretend that the power series 2^n >is a linear series he he he. see http://www.utm.edu/research/primes/glossary/MertensTheorem.html > > Ala UBASIC, I estimate your real odds might be 4096 / >3298942664324070148398699377093587963271453646320083409970227900099032340084550 > [...] Abreviate! Use scientific notation... > Sorry to be the Grim Reaper, but I've spent months with UBASIC eliminating factors >in the 32,000,000 to 48,000,000 range - I'm only on about 24% eliminated using >multiples 2pk+1 where k is 1 to 2^16 - and there's no doubt that the density of >factors decreases as the multiplier increases. Finding the first few % is easy - >finding the last 1% might take forever !! Why are you only setting k==1 mod 2^16? (I'm probably missing something obvious) I think under windows that dos windows only run when they are "up". (I could be wrong, I've stopped using windows again) You would probably get better results with Will Edgington's mersfacgmp program, and DJGPP (a port of g++ to dos). -Lucas _ 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: questions
> why is f(0) in an ll test = 4 Well, it needn't be. There are a number of other possibilities, but 4 is the smallest... > also when i went to sshool (i'm 34) 7 mod 8 == 7 > i have seen 7 mod 8 == -1 > is -1 == 7 mod 8 > which is more correct They are both correct. If you have a congruence relation (mod n), then you can add n to either side (it's like adding or subtracting zero). -Lucas _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: v17 double checking
> Now that double checking has surpassed exponent 4194304, what happens to all > those machines out there running the old v17 that produced incorrect results > for LL tests above that exponent? (I don't have any, but they almost certainly > exist.) Up to this point they will have been successfully doing double checking > LL tests. Now they will be producing incorrect double checking results. > > Perhaps they should be given factoring assignments by the Primenet server? I'm guessing so... Of course they will eventually run out too, then we will either have to admit that these computers are now basically worthless to us (unless there is some way to reach them), or just try and give them some kind of error from primenet (?). Perhaps if there were some way to give an error like: Primenet error 1221: Invalid assignment "IMPORTANT: SEE http://entropia.com/important.html" -Lucas _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Meganet Corp.
> > I may have missed this, but was there any final judgment on the Meganet > >Corp. claim that they had a "deterministic and polynomial-time" prime > >test? There were some discussions on the list early this year when they > >first made their claim. But I don't recall reading about any resolution. > >Did this just fade away? Are they still holding to their claim? And if > >they are, does it stand up to examination (if they are revealing enough > >for examination)? > > These guys are snake-oil vendors. I don't know what type of prime test > they are claiming to have or not have but from my exposure to their crypto > claims I wouldn't trust anything from them without proof. I'd say this is true in this case as well. On their site they say things like: >Those results are unheard of. The 1,000 bits test on a Sparc > II workstation takes 5 Minutes and it is still only > PROBABALISTIC. The gap in time is much greater for larger > bit sizes. Eh? The probable prime test on 10^999+7 took ~20 seconds on my PII/233. That's a thousand digits, ~3000 bits. (w/primeform) >The major breakthrough is solving a 400 year old > mathematical problem how to positively identify a prime > number without spending exponential time in dividing the > number by all the primes up to its root. This problem was solved by a primality testing algorithm that is based on eliptic curves (it was not practical), but it was polynomial. >The solution > Meganet Corporation have developed is based on a newly > designed Mathematical Sequence called the T-Sequence. > Once a number is transformed to the T-Sequence, its > quadratic residue has definitive characteristics if its a prime > number that can be easily determined in polynomial time by > performing a binary decomposition. Ok, if it is a prime then a^p==a mod p, what's your point? They don't even give a correct statment for their claims, they should say if and only if... >Meganet Corporation would like to emphasize that there is a > 100% mathematical proof behind their T-Sequence, and > further, it is a complete working product tested successfully > on over 1.3 million numbers without a single mistake. Ok, so proofs are measured in percent? Also, how many numbers are both a 2-spsp, and a lucas psuedoprime ($620 prize). I'll bet that that combination has been tested for a lot more than 1.3 million numbers without failure... Besides, the name meganet is too remanisant of Homer simpson's name for his internet company (on the Simpsons) I believe he called it something like hyper-compu-global-meganet. (It was eventually bought out by bill gates for fear of competition). -Lucas _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Trial-factorers
> Well, I'm prepared to have a go. Could we tighten up the spec a bit? > > (a) There's also been some interest in something else that Prime95 > doesn't do - trial factoring 2^p+1. (Note that this form also form also has factors of the form k*p+1.) > (b) I assume we're only interested in 2kp+1 factors. This means that > we will miss any factors which are not of this form. (Applies to > Mersenne numbers with composite exponents, and all 2^p+1 numbers - > though I believe that the "missed" exponents are easy to derive > analytically.) Yes, those mersenne numbers with composite exponents have factors of the form 2^d-1 where d|p, but the remaining unfactored portion must have factors of the form k*p+1. (I believe that is Legendre's theorem) (or rather a consequence of it) > It's probably sensible to go for an application which runs in a "DOS > box" rather than a proper windowed application. This makes it a bit > easier (for me) to write & also makes deriving a linux variant almost > trivial. (Does anyone know for sure whether or not there's a DOS box > in "Millenium"? I heard a nasty rumour...) Egad! If true then it would be added to the long list of complaints I have with microsoft. > If we can agree on that, then I have a basis to begin coding. Will > certainly take a month or two to produce even a pre-pre-release as I > am very pushed for time at the moment. No need to rush, I wouldn't call the need for such a program urgent. -Lucas _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: MersenneInfo: What Happened?
> To The MBase: > > Haven't received any forwards since Friday Oct. 29th... I believe the problem lies at the source. I don't think that anybody has been sending mail to [EMAIL PROTECTED] -Lucas _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Re: Schlagobers, Louisville style
> > But while watching the movie Pi, it occurred to me that since the number > > Pi has *nothing* to do with base 10, there would be no repitition in the > > digits in any approximation of it in base 10 (or any other integer base, > > for that matter). The sequence of digits *should* be completely random, > > and it's goofy for people to try to look for patterns. I mean hey, if > > it's what you gotta do, go for it, but I think time would be better > > spent on other things. Yech! To maintain the niceties of the list, I'll just say that I'm not a fan of that movie. > I remember some notes on interesting patterns in Pi that led one to > believe that certain statistical events were NOT ocurring. For example, > in a completely random set of (base 10) digits, one would expect a string > of, say, 100 of the SAME digit to appear in the first so many digits of > the number, however this doesn't happen in Pi and, furthermore, certain > digits appear in large clusters more often than others in the list of > 'known' digits. Umm, would the probability of any specific series of n digits in a random sample occurring be 10^-n? This shouldn't yeild a series of a hundred of the same digits for some time, if the sample is random. > Does anyone have any stats on this? Personally, I imagine this is the > same sort of statistical dribble as "The Bible Code", and someone probably > got their Chi-squareds mixed up when they were doing the math, but since > I'm not strong in statistics, it would be nice to hear an 'Expert' > opinion. You mean the bible code isn't real, I'm shocked... -Lucas _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: prime 95 version 19
> p.s ...You can memorise the pi fractionals ...add infinitum...surely...since > this is a fractional series? > i.e. + fract..-fract..+ fractif you know them ok > I think cyclic numbers are more intersting...perhaps? > Any thoughts. This is a very easy thing to memorize. The alternating series of the recipricals of odd natural numbers is equal to pi/4. (that is to say 1-1/3+1/5-1/7...). Cyclic numbers are rational numbers. While easier to predict the behaviour of, they aren't (as a whole) more or less interesting or useful. Though, pi is more useful than most rational numbers (with the possible exceptions of 0,1/2,1,2). > Anybody out their write could integer stuff? Eh? What are you talking about? -Lucas _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: estimating mersenne primes
> > >I was pretty surprised that the extrapolations for M38-M42 (all that I > > >did) were *exactly* the same for both methods of extrapolations, > > > > Your two methods are equivalent. > > I know, but I thought the algorhythms for fitting linear & exponential > lines would differ enough to result in at least a small difference in > results. I believe the first thing to do in finding an exponential curve fit is to take the log of the data, then apply a linear fit. (?) That is how I would do it anyway. This would produce identical results to the accuracy of the logarithm. -Lucas _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Reciting Mersennes...
> < name in a life time, allthough it is finite in length.>> > > If I remember correctly, someone once recited millions of digits of Pi from > memory in three days. Heh. You probably don't :). I believe the world record was around 40,000 digits. I find it highly unlikely that a human brain could hold that many digits. Even assuming reciting 3 digits per second, that would take 3.85 days, no sleep. I agree with Preda that these numbers are "abstract". They are completely unimaginable in terms of size, yet completely handlable thanks to mathematics. This is probably why people find them so fascinating. -Lucas _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Re: The Mysterious Ways of Mersenne primes
> >What else is pi then > >1+1/3+1/5+1/7+1/9 and so on ... ? > > Ermmm. Isn't that value closer to 2, actually? :-) > This value diverges to +infinity. > I thought (without checking) that the value of pi was something like: > > 4/1+4/3-4/5+4/7-4/9+4/11-4/13... > > At least it involved 4 in some way, and alternate pluses and minuses. > Anybody with a little more experience, please step in and clarify :-) Ok,here it is: pi/4=1-1/3+1/5-1/7+...+(-1)^k/(2*k+1)... this is based on the expansion of arctan into an infinite series, since arctan(1)=pi/4, the rest is history... -Lucas _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: My prime is bigger than yours (Was: something else)
> The Mersenne-related point is that QC might someday make nonfactorial > primality testing (e.g. LUcas-Lehmer for Mersennes) obsolete because it > would be quicker to directly search for all factors <= sqrt(number). After a certain point, the LL test would become profitable again, if I understand correctly. That crossover point is 2^31-1 for Mersenne numbers (It would certainly be possible to prove the next mersenne prime be trial division, though the LL test would be *much* faster). Quantum computer might raise this crossover point into the billions of digits, but I believe that trial division would still be O(sqrt(n)), (with a very small constant, but it still increases with the sqrt), whereas the LL test is O(lg(n)) (it would also be sped up by quantum computing). Unless I'm missing something about quantum computing (and I probably am). (please forgive any typos, this telnet app doesn't allow backspace charactors on my shell account. Does anyone know of a good telnet app for windows?) (I would think that it wouldn't be hard to make one, but apparently it is). > of each squaring step. In practice this appears to allow a number of > given size to be modularly squared about 3-5 times faster than sans DWT. True. That would mean the mersenne exponent would have to be sqrt(3)-sqrt(5) times bigger than the proth exponent. This is one more reason why the prize money is not a great idea. It just encourages more of the same type of searches, rather than inovation in math as was intended. Anyone who would invent a method of prime production probably would have done it anyway (regardless of the EFF prize), and I think that the power of distributed computing has been demostrated. Lucas _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Bold Predictions From STL's Mysterious Ways
> STL: what was the line you fit to the log log of the known mersenne's > exponents, and what was the error (r^2) ? > > I'm assuming r^2 is like, the amount of error for a given line fitting a > set of data. > > When I fit an exponential line to the 1st 37 mersenne prime's exponents > (since I believe that 6972593 is actually the 39th, but have no proof, so > I figured I'd leave it out), the line I got was y=1.7661e^0.301x (hope I > wrote that right), and r^2=0.9925. > > I have a feeling the log log thing will actually be more useful.. easier > to predict a straight line than an exponential curve. They are actually equally easy to predict. A straight line is just a log of an exponential curve. -Lucas _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: The Mysterious Ways of S.T.L.
> According to the "Where is the next larger Mersenne prime?" page -- > http://www.utm.edu/research/primes/notes/faq/NextMersenne.html the > Wagstaff conjecture suggests a slope of 3/2, which I believe wouldn't look > so bad. No. Wagstaff's conjecture predicts a slope of around 1.47, (2^exp(-Gamma)). > I would really like to try your calculations myself, but I haven't seen my > graphing calculator for a while, I'm not sure it'd work, and I'd prefer to > use the power of my computer. Can anybody suggest any programs ? > Preferably for Linux, even though that would mean I'd have to wait to get > my Linux drive back. GNU plot (I've never had a need to use it, but I've heard good things about it). I know that it comes with Redhat and Debian. -Lucas _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Re: splitting up 10m digit primes
> > Personally, I think the big problem with regards to this is not people > > quitting so much as the possibility of major hard-drive failure etc. on the > > testers. I doubt many of them keep good backups > > NO EXCUSE! A Zip drive or a CD-R is inexpensive and effective; one > will service many networked systems, they don't all have to be > running the same OS. True, also Pkzip 2.04g (I don't know about WinZip) had the ability to span a zip archive across floppy disks. Even on a LL test of 33mil would take up under 3 floppies. (This wouldn't be reasonable for large networks, but it would be easily achievable for the home user...) -Lucas _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: The Mysterious Ways of S.T.L.
> < Lenstra, Pomerance, and Wagstaff all believe this [an early conjecture by > Gillies] and in fact suggest that ?? M(x) ~ e^gamma log x ?? where the log > is to base 2.>> > Hence, my new conjecture: > ?? M(x) ~ e^gamma log[2] (x) + C ?? > > Of course, I used 1.4615 to make my 3 conjectures to the Mersenne mailing > list. In reality, I'm guessing it might be 1.5, or even 2^(1/e^gamma)! (In > fact, I'd rather go with 2^(1/e^gamma), as Erhardt chose 1.5 for the e^gamma > in the conjecture and now several mathematicians call the Erhardt Conjecture I'm afraid that if you are correct, so is Wagstaff. The symbol "~", at least in mathematics means that if f(x)~g(x) then f(x)/g(x)=1 as x->infinity. Your conjecture seems like it would yeild a better aproximation than Wagstaff's (you could certainly argue that 2 is a special case, since it's corresponding Mersenne is the next bloody prime, and there is 1 of the 1.4615 right there). -Lucas _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: types of work to request - 10m digit prime vs. next prime
> Conjecture time: The prime number earning the $150K prize will not be a > Mersenne. This isn't so much a conjecture as a prediction (there is a difference). A conjecture is a very specialized prediction. > Why do I say that? Even with processor speeds increasing, we have a good > idea how long it'll take to find big primes by Lucas-Lehmer. Even for the > 10M-digit prime it'll be a damn long time the way we are doing it now. > Finding the monsters requires an intellectual leap by someone - possibly > in processor design, more likely in number theory. Admittedly this leap > may well be a better version of L-L in which case Mersennes will still be > the record primes for a long while to come. But my hunch is that there is > a better chance of finding some new way to either construct primes, or to > test some other special-form number, than there is of dramatically > improving on Lucas-Lehmer. Just a hunch. I might be wrong. I hope I live > long enough to see all of the EFF prizes awarded, whether to Mersennes or > not. Ok, it seems doubtful that we will ever be able to find a test more efficient than the LL test. The LL test involves p multiplications mod Mp, which is pretty impressive. However, I agree with your prediction because there are much more targeted types of numbers with similar running times (e.g. Proth numbers). As Chris Nash pointed out, a Proth test would have taken 1/4th the time of the LL test on the Mersenne found in June on a number of precisely 1,000,000 digits. You may be right about the construction of prime numbers. Also if someone were to find a faster way to multiply than an FFT convolution, that would dramatically improve primality testing. > PS - On an unrelated note --- what is the smallest natural number that is > not known whether it is prime or composite? Surely *someone* out there is > trying to work from the bottom up and factor every number. (I don't know > the answer. I am guessing the it is a smallish number of maybe 15 or > so decimal digits?) Probably the one right after the largest sieved interval. But I have to ask the question: Who cares? Unless the larger sieved limit is showcasing a new sieving algorithm, then why does it matter? To verify the primality of numbers up to a hundred digits is a simple matter. Just my $0.00 worth. (the FSF's motto) -Lucas _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: estimating primes (was: Re: Mersenne: Islands of Truth)
> Hmm... I just changed my worktodo.ini to Test=5014947,63 (where's the 63 > come from ? it was used for the last number I was assigned). > > It's saying "Error: Work-to-do file contained composite exponent: 5014947" > > I suppose that means it's already been tested & found to be non-prime ? > (composite = non-prime, right?) This is for the number of bits the Mersenne number has been trial factored to. I.E. your last number was factored to 2^63. the reason that it reported a problem was that the exponent was composite. This means that the corisponding Mersenne number is composite, thus we only check prime exponents. The number 5014947=3*7*47*5081. Thus 2^3-1, 2^7-1, 2^47-1, and 2^5081-1 all divide 2^5014947-1 (though they do not factor it completely!). -Lucas _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Islands of Truth
> > missing. #2: That the discovered M38, which all we knew about was that it was > > in the 6M range, was actually around 6.9M, which I was correct about, and #3: > > How did you make this estimate ? Fit an exponential curve to the known > primes, and extrapolate the 1st one that should have at least 1m digits ? Who knows the misterious ways of STL? > Why isn't something like this used in GIMPS to select numbers to work on ? > -- use current known primes to estimate the location of the next, start > allocating numbers to work on at that number, and keep alternating +/-1 > till it's found ? The verious conjectures all state something about the *average* distribution of Mersenne primes. They don't say anything about the local distribution. -Lucas _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: # of digits in 2^p-1
> What's the best way of finding the number of decimal digits for the number > 2^p-1 ? > Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ^^^ ^^ Q5.3. It's no good unless people read it! -Lucas _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: DOSville
> .TXT files are the one true document file. Pure ASCII bring it on!
> Mathematical notation in .TXT isn't easy, though. It's a conspiracy.
It works well enough. Most of it is pretty standard, and TeX fills in
the rest
$$\int_{0}^{1}\sqrt{1-x^2}dx={\pi \over 4}$$
Yeah!
> <>
>
> Give me a DOS-based command line (yet Win98 background-running capability)
> with a really nasty, God-awful set of fifteen switches that must be ordered
> in a precise way depending on the phase of the moon. :-P
Sorry, but M$ didn't invent multitasking, and from what I've seen
(I haven't seen NT multitask much) they have yet to implement it effectivly.
BTW, if you love command line programs with obscure switches, you could
try Linux.
> S. "Property of Billy and Andy" L.
-Lucas "I owe Linus a case of beer by now" Wiman
_
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: gzipped binary expansion of the largest prime
> Can somebody give me the last few digits of the decimal expansion of > (2^6972593)-1 so that I can verify my copy's intact ? to find the last n base-d digits of M39, find 2^(6972593) (mod 10^d) -1 The last 100 digits of it are: 854323570491331747687718276359853562553418155924593120827624505017498840034615135366526142924193791 -Lucas _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: gzipped binary expansion of the largest prime
> Is there a copy (preferably unformatted plaintext) of the decimal > expansion of the largest (2million-some digits) prime, gzipped or zipped > or something, somewhere ? Yes! Landon Curt Noll has all the Mersenne primes on his website. http://reality.sgi.com/chongo/prime/merdigit/index.html#largest (Ack! I'm slipping, I had to look it up!) Also (if you want it in poster form) look at www.perfsci.com (though last I checked it was ~$30 US). > Bummer, calc didn't compile in my shell account. > > In file included from seed.c:53: > /usr/include/sys/resource.h:25: field `ru_utime' has incomplete type > /usr/include/sys/resource.h:26: field `ru_stime' has incomplete type > seed.c: In function `pseudo_seed': > seed.c:216: field `tp' has incomplete type > seed.c:241: field `tp2' has incomplete type > *** Error code 1 > make: Fatal error: Command failed for target `seed.o' > > Oh well, hope my repaired Linux drive gets back soon Hmm, you might want to sent this to Noll. He is big on getting Calc to compile without errors on darn-near everything. Also look at Pari/GP. It has binaries for windows! (It seems faster than Calc too!) ftp://megrez.math.u-bordeaux.fr/pub/pari/windows (take off the /windows for linux/msdos/mac/etc versions). Hope this helps, Lucas _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: probability of primeness (was: Re: Mersenne: splitting up 10m digit primes)
> > I think trial factoring is done to 2^68 for an exponent around 33 million. > > Thus your chance is 2 * 68 / 3300. > > Okay, so as far as we know, each number is equally likely to be prime, and > this probability is just based on how much has already been tested ? Umm, no. The probability that a number is prime is inversly proportional to the number of digits (or more precisely, the probability that a number on the interval [1,x] is prime is asomtotically 1/ln(x)). However, the probability that a number is prime increases with the amount that has been trial factored (without finding a factor). The precise estimation is based on Mertel's theorem. > Ugh... I apparently had bad math teachers, and GIMPS is really making me > feel it. I *really* wanna play with these numbers, but I feel > intellectually cripled. You certainly seem to have done a good job! You found the two big conjectures about Mersenne distribution. That is Curt Noll's (poorly defined) island theory (your pairs observation), and your observation about it being roughly exponetial (a conjecture due to Wagstaff, and others, though Wagstaff's has hueristic evidence to back it up). > I took the numbers from > http://www.utm.edu/research/primes/mersenne.shtml#known See http://www.utm.edu/research/primes/notes/faq/NextMersenne.html, as well as http://www.tasam.com/~lrwiman/FAQ-mers, Q4.2. > Does anybody see what I'm talking about ? Is there any significance to > this ? Has somebody already written extensive papers on this ? Yes, see above. Good work! -Lucas _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: splitting up 10m digit primes
> > There is now a prize for factoring Fermat numbers too. > > Neat. Where's the info ? I think Richard Crandall is offering a prize for Fermat factors (http://www.perfsci.com). John Selfridge is also anouncing a prize for factors of various numbers which "ought to be prime". I don't think that there is a website yet. I'll repost the list if you are interested. -Lucas _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Mersenne data repository
> Anyone who has data which they wish to make publicly available may > wish to take advantage of my FTP server. > > Downloads from the server are already available by anonymous FTP > (ftp://lettuce.edsc.ulst.ac.uk/gimps), I keep copies of many Mersenne- > related programs and also George's database files. We could put this on a domain name. mersenne.net is not taken, and I'm sure we could get the registration fee. I would certainly be interested since I probably won't be using tasam.com in a couple of months, and hence I need some place to host the FAQ. -Lucas _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Mprime
> I really want to run the Linux prime search software when I'm in Red Hat 5.2 (I'm >usually in Windows 98), but the program seems to have no documentation or information >once it's running. I ran it for 4 hours once and had no idea how to close it. I had >to use "kill," the only command I could think of to close it. When I got back to >Windows, I saw that my work had not been saved. I had set the option in Windows for >disk saves every 15 minutes. Mprime and Prime95 shared the same data files, like >they are supposed to. What's going on? I'd vote for an mprime on an X-server. I >want to see SOMETHING while the thing's going. At least show me the iteration #, >iteration % of total, and seconds / iteration. (could everyone please set their mailer to wrap at <80 charactors) Try mprime -m then choose 6. Test/Continue It seems a bit odd that it didn't save work when it was killed. I thought it was supposed to. What signal did you send the process? Try CTRL+C if kill continually keeps it from saving. -Lucas _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: ECM Factoring
> When this is cleared up, it will make a good FAQ. > > Who maintains the FAQ list? Do you agree the answer here is a good FAQ? > > >I would like to look for a factor of a mersenne prime in a specific area. > >For example, for a mersenne exponent of say 40,000,000. I want to use the > >Prime95b program, (v19 I guess), to search for a factor in a specific range > >from, say, 2^40 to 2^50. I do not understand the ECM factoring instuctions > >included with Prime95. I maintain the FAQ (well, one of three anyway). There is my FAQ which deals mostly with the math involved with Mersenne numbers. There is Scott's FAQ which deals with primenet, and there is George's FAQ which deals with Prime95. I have gotten questions involving all three (and at least 2 letters which assert mine as the "best"). I like the current separation for a number of reasons: (1) It makes sense (2) I know next to nothing about Prime95, and even less about primenet (3) I don't really care enough about the other two to put forth much effort. (Note that I *do* apreciate Prime95 and primenet, I just don't care much about specific issues with them). Now the last one might sound bad, but with school, I hardly have time to add anything I care about to the FAQ (there is a section on P-1 factoring, Q3.10 BTW). Hopefully this should explain things a bit. I will (eventually, once I read more on it) add a section to the FAQ about ECM, but Prime95 specific issues I know little about, and George would be much better suited to writing about this. Sorry if my rambling makes no sense... Lucas _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: ECM Factoring
> I would like to look for a factor of a mersenne prime in a specific area. > For example, for a mersenne exponent of say 40,000,000. I want to use the > Prime95b program, (v19 I guess), to search for a factor in a specific range > from, say, 2^40 to 2^50. I do not understand the ECM factoring instuctions > included with Prime95. For this targeted a test, you might want to use trial factoring simply edit to worktodo.ini file adding the following line Factor=a,b Where a is the mersenne exponent, and 2^b is the limit trial factored to. you can override the default trial factoring depth with the line FactorOveride=n where n is the power of 2 that you want it to stop at. (I think that is how it is spelled, see undoc.txt) (a rather ironic title in my opinion) > I don't understand how to set the ECM= paramaters to accomplish my goal. > > It is my understanding that one can use ECM or 2^p-1 factoring with V19. (I think you mean P-1 factoring). Yes, but ECM wouldn't be best for such a targeted search (as I understand it). -Lucas _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Graphical visualisation of computations
> > I must admit, I dallied (albeit very briefly) with the bovine rc5 client. > > Gack! About the only manufactured challenge comes from ID software. Should read About the only more manufactured challenge comes form ID software. :) -Lucas _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Graphical visualisation of computations
> not, but, what would it show? A progress bar, maybe... anything else? There
> isn't really anything else to show. Intermediate results of the LL test
> don't themselves have a lot of meaning (even the final result, if non-zero,
> is devoid of much interpretation). There's not a lot you could plot - a
> graph of the iteration time would only serve to show when you opened
> Microsoft Word or something...
Yes, but the point is that they may be pretty. (?) This probably wouldn't
alter anyone who already is at GIMPS, but it might attract new members.
This feature (based on George's postings about his interests in the project)
would be badly maintaned, and a support headache.
> I must admit, I dallied (albeit very briefly) with the bovine rc5 client.
Gack! About the only manufactured challenge comes from ID software.
> Were it not for their peculiar statistics ('if keys were drops of water, we
> could flood the world in a week' etc) I'd have got bored of the effort a lot
> sooner than I did. The SETI client looks pretty (more of a screen burner
> than a screen saver though) but the display is at best meaningless, a waste
> of cycles at best.
Ha! SETI has gained so many cycles due to that "waste". I know at least
three people who "use SETI 'cause it looks cool", and only 1 person
(discounting y'all, and myself) who uses GIMPS. Though she let me
put it on her computer only after many assurances that it wouldn't
do anything wierd to her computer. A good reason why...
> I think we ought to count ourselves lucky that what we've got is bare-bones
> and low-impact.
Despite the extra cycles that it might get us, I couldn't agree more!
-Lucas
_
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: trial factoring using P-1's GCD
I've been wondering about this lately... If we are to begin P-1 testing on larger exponents, this implies lower trial factoring limits (though possibly only by 1 or 2 bits). Now, P-1 requires an investment of a GCD on two numbers each of similar size to Mn. So, since we are investing this much (computational) engery in a GCD, why not cram in as many factors as we can? Would it be possible to find multiply the (a^q-1) mod Mn by small (possible) factors skipped due to the lower factoring bounds faster than it would to directly check these possible factors? Gack, that was a bit unclear, say that k*n+1 divides Mn, k is non-B1-smooth. Which would take more time, checking (directly) to see if k*n+1 divides Mn, or multiplying (a^q-1) by k*n+1? (assuming k*n+1 is around 64 bits) Lucas _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Important info on M(M(p)) from Wilfrid Keller
> >Now, I think that it might be a nifty (tm) idea if GIMPS/primenet > >were to start looking for factors of double Mersenne numbers. If I > >understand correctly, much of the code is already written (changes to > >the P-1 code, and the normal factoring code), and I'm sure that such things > >could interest mathematicians more than finding the next Mersenne prime. > > The only feasible approach for M_M_61 and above is trial-division. I I was speaking about using part of the P-1 code to speed up trial factoring for the larger exponents (though, of course an FFT multiply is included in the LL code, but I don't think they are the same one (P-1 has to n*m, whereas LL has to by n*n)) > recently blew the dust off by my program MFAC and gave it a run. For > M_M_61 it processes divisors N*M_61 + 1 on an AMD/400 at about 2.2 > billion N's per hour. (6 billion/hour for M_M_31.) If people are > interested, and unless someone else can do better, after a bit of > tidying up I can make this program available. Q: Is this program in ANSI C? It would probably be a good idea to do so if not, as this would attract UNIX users... -Lucas _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Important info on M(M(p)) from Wilfrid Keller
[...] > when I found out than Curt Noll had started an attack on M(M(127)) with > superior hardware. I imagine that by now he has carried the search much > further. This is further evidence for why GIMPS is such a good idea! (as if we needed more) If Curt Noll and you have been working together, your computer time would not have been wasted, nor would (presumably) much of his. This is the beauty of distributed computing projects, but this illistrates how *key* centrilization is. Now, I think that it might be a nifty (tm) idea if GIMPS/primenet were to start looking for factors of double Mersenne numbers. If I understand correctly, much of the code is already written (changes to the P-1 code, and the normal factoring code), and I'm sure that such things could interest mathematicians more than finding the next Mersenne prime. With the (possibly buggy) announcement of prize money from J. L. Selfridge, I'm sure that interest should increase very quickly... -Lucas _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Factor of 2^(2^31-1)-1 found ($)
> >All (and especially Chris), > > > >Yesterday (and the day before), I went to the Illinois number theory > conference. > >There (2nd talk of yesterday) J. P. Selfridge announced that he would > >give away $1000 US for any factor found of a number which ought to be > >prime (he provided a list). On that list was 2^(2^31-1)-1. > > Please post the list of candidates, to the mailing list. > > > Ken F_m for m=14,20,22,24,31 M(M(p)) for p=31,61,127 M(B(p)) for p=31,61,127 F_m for m=2^k+k k>=6 B(p)=(2^p+1)/3 -Lucas _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: GIMPS client output
> Might be nice to display the percentage out to an accuracy that changes > every hundred iterations. Hmm, looks like that's an integer of the > percentage, not rounded. Guess it doesn't matter. For the one I'm > working on it looks like 3 decimal places would be needed to see a change > every 100 iterations. This is changed in V19 (currently in Beta). I believe (George correct me if I'm wrong) that you can specify it up to 6 decimal places. -Lucas _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: M(M(127)) and other M(M(p))
> Of course, the sequence that still remains unknown is > > 2 > M(2)=3 > M(3)=7 > M(7)=127 > M(127)=170141183460469231731687303715884105727 > M(170141183460469231731687303715884105727)=??? Yes, this sequence is interesting, but if someone finds a way to prove/ disprove the primality of M(M(127)), I think that would be far more significant than actually proving/disproving that specific number prime. (Assuming you don't find a factor, that is). > I checked Chris Caldwell's pages on this, and Curt Noll's trial-factored > M(M(127)) to 5.10^50, surprisingly low considering the size of M(127) > itself, I noticed many other M(M(p)) as listed in > http://www.garlic.com/~wedgingt/MMPstats.txt have only been tested to very > low limits indeed. The reason is relativly clear: the work of checking *even one* factor of M(M(p)) is greater than the work required for an LL test on that number. This is because of the need for p squarings modulo some number greater than M(p). > I wondered why there wasn't more work done on these - though I understand > it's very hard to motivate people when Guy's law of small numbers no doubt > applies, but everything M(M(61)) and above is currently unknown. It would be > nice to see a few more results there. I'm guessing that if a more optimized program were created, then perhaps there would be more interest. The Selfridge prize for these numbers could help. ...However, we have no way of knowing wether or not these numbers are prime, unless we find a factor. Interestingly enough, when we find the next Mersenne prime, searching for a factor of M(M(p)) might allow us to find an even bigger prime. If for example, 6*M(p)+1 divides M(M(p)), then it must be prime! Wait, that might just be the reason to search! Will only searched up to k=4 for M(M(6972593)), but if 2*k*M(p)+1 divides M(M(p)), then you've just beaten the world record! Non-Mersenne's might once again grace the top 10 list! -Lucas _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: Factor of M(M(31))
Ok, I should have researched a bit more. Many many people have informed me of will's site about M(M(p)) for various p's. I apreciate the link, but I have it now, I don't need any more of them. -Lucas P.S. Warut, I hope you enjoy your money! :) _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: Re: Factor of 2^(2^31-1)-1 found ($
Oopsy. That should have read J. L. Selfridge -lucas _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: Factor of 2^(2^31-1)-1 found ($)
All (and especially Chris), Yesterday (and the day before), I went to the Illinois number theory conference. There (2nd talk of yesterday) J. P. Selfridge announced that he would give away $1000 US for any factor found of a number which ought to be prime (he provided a list). On that list was 2^(2^31-1)-1. I began searching for a factor of this number in mersfacgmp at around 12:10 Central standard time. I thought that mersfacgmp was malfunctioning, because it terminated too quickly, but I was wrong, it had found a factor! 295257526626031 divides 2^(2^31-1)-1, I have confirmed it in 3 different programs. Just to make sure that I haven't gone off the deep end, could Chris Caldwell confirm that he actually offered a prize for this number, and could the rest of you confirm that it is an actual factor? Also, Chris, I lost the sheet that had everyone's email address' at the conference, could you send me J.P. Selfridge's email address? Thank you, Lucas To guard against errors in transmitions the factor is 295257526626031 _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: P-1
> But as everyone on this list knows, any factor of a Mersenne > number looks like 2*k*p+1 for N=2^p-1. Plugging this into > the above equation gives > q=2*k*p+1 > q-1=2*k*p Correct. > Doesn't this mean the lower bound on a "p-1" method search should > be greater that the Mersenne exponent (the p in 2^p-1) to have the best > chance of success? Then the "upper bound" of the "p-1" search can > be resevered for cracking a big factor in the "k" of a Mersenne factor. No. Simply multiply the exponent on the base by p. This produces the desired result, without having to go to the extra effort of extending the bound that far. I probably should add a section on P-1 to the FAQ. -Lucas _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Re: complaint
> >>One version of Linux has paid the bill and passed the test, so at least one > >>version of Linux is Unix. > > > >If you wanted to be picky, you could always say that a version of _GNU_/Linux > >has passed the test... The tests aren't for the kernel only, are they? > > But "GNU" stands for "GNU's Not Unix!", so how can it be Unix if it isn't? Wow! Could this be used for some kind of proof of the logical inconsistancy of the GNU system? What if M$ has been right all along? Scary, mind-blowing stuff. -Lucas _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Celerons vs. Pentium II/III at large FFT lengths?
> Ackk! That was rather inexact wording. Let me try again...my > Celeron 400 based systems crunch exponents in the 384K FFT range at about > the same speed as George's PII-400 machine. However, at the 448K FFT size, > George's machine appears to be 20% or more faster than my Celeron 400s. > Could the 128K L2 cache of the Celeron chips (vs. the 512K L2 cache of the > PIIs) be the culprit? I think so. Yves Gallot mentioned something similar on the Primes-L list a while ago. This brings us to an interesting point. Should the primenet server start default assigning celeron's <384K FFT mersennes, and save the larger ones for PII's/PIII's? -Lucas _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: GIMPS
> < the people who work on those ports would be interested in your input. > (ie actually tell them how you get it to segfault, maybe they can fix it :)>> > > Linux is weird. Use Win95 OSR2. :-P In fact, if you're running some weird OS > like Linux or Unix, that probably explains all your problems. Linux - an amazingly stable, powerful, robust OS, based on a year's old standard. Parts of UNIX have been refined for nearly 30 years. Windows - A 32 bit patch to a 16 bit patch to an 8 bit patch to a pirated copy of CPM. Despite the fact that it has been around for nearly 20 years, the need to be backwards compatable, combined with the genious of microbloat causes it to be notoriously unstable, buggy, and obnoxious to use! > Prime95 IS well behaved - sure seems like you running a different OS. Ok, so if the Linux version is unstable, how come the list isn't inundated with complaints about it? If the prime95 version is so infalable, why do we see any questions about it? The reason is that *certain* systems have problems (regardless of OS), it's just that yours haven't. > S. "Property of Bill Gates and Andy Grove" L. Ahh, this explains things. -Lucas _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: sci.math FAQ
> H, is it me, or is this FAQ looking somewhat out of date? I think it > might be worth contacting Alex on a more "official" basis about the > Mersenne entries, it wouldn't hurt to get a bit more GIMPS weight behind > the brief mention in the sci.math FAQ. On the other hand, it perhaps goes > to show how much attention is paid to the FAQ anyway, the data does have > a rather *aged* hint about it... much water has flowed under the bridge > since 2^2976221-1. What an odd coincidence! I just posted on sci.math yesterday complaining about this. No responses yet. Maybe if George (or me, as I might be more sympathetic, knowing what it's like to not want to update the FAQ) sent an email, then we could start to run this section of the sci.math FAQ (as long as it doesn't get too out of control). >> The largest known non-Mersenne prime... > Hmmm, I think I might be personally offended by this one! The Amdahl Six > record hasn't been there for a while... in fact, it's no longer even in the > top 20. Yes, I should say so! Perhaps Chris Caldwell could keep this part of the FAQ up to date. -Lucas _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Mailing list archive
> By the end of next week I will remove the mailing list > archive search function. The index for the archive occupies > 1/3 of my disk quota. Considering how little it has been > used, I can make better use of this disk space. I hope > someone else would be willing to rebuild the index and host > it. The mailing list messages up to Feb. 98 can be found > below (about 4.2Mb). Why not host it on xoom.com or something? They offer free unlimited space. -Lucas _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: Factors of DecMega
Scott/all, I downloaded the newest beta for Prime95V19, and set it to ask for 10,000,000 digit Mersennes. In my worktodo.ini file, I got the line: Test=33219379,32 This surprised me! I had tested this number to 2^47, and Alex Kruppa had tested it to at least 2^55 (further investigation revealed 2^60). You should update primenet's files pertaining to this off of those at http://www.informatik.tu-muenchen.de/~kruppa/M33M/index.html -Lucas Wiman _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Macintosh Speeds
> Now my question to the list is, would I be better off having these machines > participate in GIMPS via MacGIMPS on MacOS or should I run mprime on Linux? My > main concern is performance. Which performs better on the same hardware, > MacGIMPS or mprime? I would guesstimate that they all have ~32 MB of RAM, and > those that do not can get upgraded to 32 MB easily. Which route should I take? Umm, unless Mac's have changed a lot (ie become intel-based machines), you can't run Mprime under linux. Mprime is written in intel assembler! -Lucas _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: RE: Factoring more
> Numbers above are factored to > - --- > 71002^72 > 57022^71 > 44152^70 > 35102^69 > 28132^68 > 21592^67 > 17852^66 > 13382^65 > 825 2^64 Isn't this the "optimal" configuration if all computers in GIMPS were identical? There are a number of 486's that are doing only factoring, does it take these into account? Think about it, there are a number of computers which should be factoring numbers faster than LL tests can be performed. Call this "factoring profit." Wouldn't it make sense to keep factoring profit as low as possible, as this could speed up the more immediate consern of sooner-to-be-performed LL tests? As an example, I just recieved the factoring assignment of 10258511, but I should think that we wouldn't even start these tests for some time. Why not go back and factor some 8M exponents further so as to save a few current LL tests? Wouldn't this actually get us to the next prime quicker? Or do I need to get more sleep :)? -Lucas _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Simple question about P-1 factoring method
> If I understand P-1 factoring correctly, then using it to a stage one > bound of k to try to factor M(p) will find all possible factors less > than or equal to 2*k*p + 1. Yes, of the form n*p+1 (not 2*n*p+1 :). This is for the simple reason that every power of a prime <=k must divide Q (due to your definition of how Q is produced). Then by the fundemental theorem of arithmetic, (all numbers are able to be evenly divided into primes < themselves), we know that any number I've heard that P-1 is "more efficient" than trial factoring; does the > proof go along these lines? Or is it more complicated than this? It's only "sort of" more efficient than trial factoring. It will find (some) large factors more quickly than trial factoring will, but it wouldn't find the factor 2^40*p+1, which (unless p is very small) would be found very easily by trial factoring. > Of course; I realize that. I was only looking at it this odd way > because of the trial factoring gaps I need to close. Since I already > have the P-1 data, it's easy to do this. If I didn't already have the > P-1 data, it would (most likely) be faster to simply do the trial > factoring. Why would you have trial factoring with such low bounds, but P-1 with such high bounds? Just asking... -Lucas _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: P-1 second stage
>I've just finished trying to factor F24 using the P-1 method > with a bound #1 of 1,000,000. No factor was found. >Unfortunately, I do not have enough memory to run stage 2. > So, is there a volunteer that would be willing to run stage 2 on > their computer. It will take about 3 weeks. You need 256MB of memory. > The program will use 100 MB of that for the full 3 weeks. How does the stage 2 of P-1 work? Why does it require more memory? How do you know how long it will take if you don't even know what speed of computer is being used? :) The only references that I've seen to it say that it involves random walks and the birthday paradox. Can anyone point me to any online resources? (Library is closed for a week in preparations for the start of a new semester) Thank you, Lucas _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: Probabilities of P-1
A week ago, George asked about probability in P-1 factoring. I haven't seen a single response, though I would guess that he has received many private emails. Could this please be included on the list? I am interested in this, as (I'm guessing) many others are. > Extra credit: Can someone tell me the probability that P-1 factoring > will find an n-bit factor? Shouldn't the probability of it finding a n-bit factor be immaterial, as the fact that it finds a factor is all that matters. The whole n-bit concept should only matter if we speak of trial factoring. > This is but one piece of the puzzle in > determining the best trial factoring limits and P-1 bounds. To compute > this probability the k in the 2kp+1 factor must be "smooth", that is > all factors must be less than bound #1 except for one factor that > must be less than bound #2. I'm sure I have the info around here somewhere, > but everyone might be interested in the math behind deriving trial factoring > limits and P-1 bounds. The k must be smooth to B1, yes, but a more rigorous requirement is there also. What if k=2^70? Smooth to any B1, but this number would not be found by P-1 factoring. I'm guessing that numbers that are smooth with high exponents is low, so it should be about the same. Here's what I was able to come up with while doing repetitive jobs at work: A number p^x (p prime) is said to be "enough for" n if p^(x+1) does not divide n. Let f(p,a,b)="the sum from v=a to v=b of 1/p^v" (note for those of you who don't know, f(p,0,b)=(1-(1/p)^n)/(1-1/p)) The probability that p^x is not enough for n is p(p,x,n)=1-f(p,1,x)+f(p,x+1,[log_p(n)]) Thus the probability that value of Q=2^x_1*3^x_2...B1^x_(pi(B1)) will be enough for n, for all p_ihttp://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: new accounts
> The last time I did timings like this - admittedly, probably over a > year ago, but the mers package hasn't changed much since, especially > in terms of performance - this is wrong. SPARC LL testing - > especially with MacLucasUNIX - is much closer to matching Prime95 LL > testing than SPARC trial factoring - with mersfacgmp, say - is to > matching Prime95's trial factoring, by, as I recall, a factor of about > 12. Though I don't have specific timings, I imagine this would be the case. I was referring to the Mfactor program by Peter Montgomery. I have heard this performs considerably better than a GMP based program (written by Alex Kruppa) on RISC architectures. I suppose that I could/should check up on this with my SPARC-owning friend. > The UltraSPARC would probably significantly outperform a similar > megahertz PC, if we had similarly optimized code running on each. > Perhaps. Again, I have no timings for this, but I would think that if you tried MacLucasUNIX on both a SPARC, and a PC, the SPARC would be the overall winner because of the massive amount of I/O that runs on LL tests. In factoring, I would imagine that the difference would be smaller, (using the same program). -Lucas _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: new accounts
> The Intel code is very highly optimised. From the figures given on > the manual checkout page and my results to date a 270MHz UltraSPARC > runs like a 120MHz Pentium. But that's only becuase I've tweaked the > compiler options will help from people on this list. Initially it > was performing more like a 90Mhz Pentium. I had over a 1000 hours > at the lower speed before recompiling. You could do factoring, the margin between factoring on a PC and an UltraSPARC should be much slimmer than LL tests. > When I joined I didn't have any idea what the differences between a > Pentium and an UltraSPARC would be in this work. The UltraSPARC would probably significantly outperform a similar megahertz PC, if we had similarly optimized code running on each. I know my friend's SPARC (running at 233 mhz, bus 233 mhz) sure does outperform my PII (running at 233 mhz, bus 66 mhz) on most things. -Lucas _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: More basic questions
> 2. Is overclocking of my Celeron 333 a good idea? I probably can't do > it just now (EPoX P2-112A motherboard isn't made for such purposes), > but I could upgrade it in about 2-3 months' time. No. This can often lead to errors, and newer CPU's are on the edge of sanity when it comes to heat anyway. I've heard that a Celeron can burn it self out completely in a few minutes without a heat sink. > 3. How are the expected completion date and the chance that "my" > exponent is a prime computed? The chance that your number is prime is computed using a conjecture of Wagstaff which states that: * The number of Mersenne primes less than or equal to x is about (e^gamma/log 2) * log log x. (Here gamma is Euler's constant). * The expected number of Mersenne primes 2^p-1 with p between x and 2x is about e^gamma. * The probability that 2^p-1 is prime is about (e^gamma log ap )/(p log 2) where a=2 if p=3 (mod 4) and a=6 if p=1 (mod 4). gamma is Euler's constant, ~.577, it is computed as (sum from 1 to n of 1/v)-ln(n)) > 4. How come there are 8180017 iterations for M8180017? Shouldn't > there be (p - 2) iterations for Mp (since we know L(1) and don't need > to know L(p))? Or am I missing somethig? Or do I just cavil at it, > and it is useful to know which Mp am I checking for a first glance at > Prime95 output (most probably)? L(n) is defined as (2+sqrt(3))^n+(2-sqrt(3))^n. S(n)=L(2^n), hence L(1)=S(0)=4. Just because we know what L(1) is doesn't mean it should be discounted, it is still included in the count. We are trying to find if S(p-1) mod Mp=0, if S(0)=4 then there are p iterations. -Lucas _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
RE: Mersenne: Multiple residues - enhancing double-checking
> If B's checkpoint info doesn't match A's, the exponent is issued to > another system C which calculates to the first checkpoint & check in, > as before. If we now have two matching residuals, the two systems > supplying them are told to continue and the system with the "wrong" > result is told to abandon that exponent. If all three differ, issue > the exponent to system D ... The main way to speed this up is to have system C continue from the last residue that it is known that system A and B agree upon. Or, possibly even better (though more error prone) would be to have A and B recalculate from last agreed upon residue, and see if they now agree. This would waste at most 2 P90 months, without having to transfer it over the network, or have system D doing half the agreed upon work. I think it's safe to say that if system A and B can agree on the residue at that point, then it is the correct residue. > As well as minimising wasted work, this scheme results in very little > extra server traffic, since the systems all need to check in > occasionally anyway. If Prime95 is altered so that it always works on > the _smallest_ exponent it has "in hand", work should be completed > reasonably quickly and in reasonable order. (Especially bearing in > mind that this scheme completes double-checking at the same time as > first tests!) Won't this mean systems constantly getting interupted in the middle of an exponent segment? Or would the systems only continue on one segment when they finish the current one? > When a prime is found, the discovery credit (& any prize money) > should obviously be split between the two users who ran the last > iteration on the exponent in question. This makes sense, though it might not be needed. This scheme would work best on people willing to stay with GIMPS for the decade required to finish the range. Many of these people have (fast) networks with lots of computers on them. The check/double check computers might be right next to each other, owned, and run by the same person. This will not matter for some time. Does anyone have current data for % mistakes? -Lucas _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Testing times
> From this I understand that it takes around about the same number of > interations as the size of the exponent to establish primality. Correct. See the FAQ at the end of this message for more info. > I've got several UltraSPARCs I've pressed into service and currently > have 7 exponents checked out being tested with MacLucasUNIX. When I > filled out the manual checkout form I assumed, for lack of better > information, that an UltraSPARC would perform like a Pentium. This > doesn't appear to be at all close to the truth. My first assignment > was for 7902277. The account details indicated this would take 600 > hours of CPU on a 270MHz Pentium. It should perform aproximatly like a Pentium, if you check MacLucasUNIX compiled on a pentium and a sparc. However, on intel chips, we have a nice edge: George Woltman's highly optimized assembler version. I doubt any C code could even aproach it. -Lucas _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
RE: Mersenne: Multiple residues - enhancing double-checking
>> That is to say when >> one computer finishes to X%, it reports its 64-bit residue to primenet, and >> waits for the second computer working on the same LL test to do the same. >> Until the other (slower) computer reports in, the (faster) computer works on >> another exponent. >Not at all. The first-time check goes its way, but reporting >partial residues to coordinator / primenet from time to time. Later, >often when first LLTest was finished long time ago, somebody >receives: >Double-Check: >M23780981,64,863FF87,678676AA,FF637BC,[...],CRC:9923FDA. This scheme makes almost no sense for normal double checking. This is becuase it would save *no* time at all. Think about it, even if you identify that an error ocurred in the second week of a 3-month test, you still have to run it to completion, and a third test must also be run. (So 3 LL tests must still be run if an error ocurrs). >This schema makes possible simultaneous checking, > though. But the start-stop mechanism you describe has little > sense. The method that you describe would only allow simultanious checking if the computers were of equal speed, or if one kept working on the same exponent, and the other computer kept getting further behind. The scheme that I described (and Brian thought up) would allow the computers to run at the same exponent/time, while still keeping busy. Sorry about my bad english, and it's even my first language! -Lucas _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
RE: Mersenne: Multiple residues - enhancing double-checking
> This idea is rather obvious, and no, I don't remember seeing it either. This had been discussed earlier. Brian and I talked about it for a little while, he came up with the original idea. > I think the idea has definite merit. If an error does occur, it's equally > likely to happen at any step along the way, statistically. Errors are every > bit as likely to happen on the very first iteration as they are during the > 50% mark, or the 32.6% mark, or on the very last iteration. True, but if the system is malfunctioning then the errors should start early. > Especially as the exponents get larger and larger, I see a *definite* > possibility to reduce double check times by having first time LL tests > report residues at certain "percentages" along the way. Yeah. The error rate should be proportional to the runtime which is increases with the square of the exponent (ouch!). > Just for example, every 10% along the way, it'll send it's current residue > to the Primenet server. I'm guessing that you mean a certain amount of the residue. Sending in 10 2meg files for *each* exponent in the 20,000,000 range would get very unwieldy, and inconvenient for people and primenet. Of course, this would only help if we were running more one test for the same exponent at the same time (otherwise, this would just be a pointless way to do a triple check). They would either have to be coordinated (running at the same time, logistical knightmare), or (as Brian suggested) have a "pool" of exponents running on one computer. That is to say when one computer finishes to X%, it reports its 64-bit residue to primenet, and waits for the second computer working on the same LL test to do the same. Until the other (slower) computer reports in, the (faster) computer works on another exponent. This would speed up the entire project, but it would slow down the individual exponent, which would make people mad :(. > I forget the numbers being tossed around, > but you'd only save 50% of (the error rate) of the > checking time. As I pointed out above, the error rate should increase with the square of the exponent (plus change). This means that if 1% have errors at 7mil, 22% will have errors at 30mil. -Lucas Wiman _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
RE: Mersenne: massive GIMPS cabinet
>> They will have only a floppy attached, which will run once (at boot up). >Are these basically just "NC's", with a boot floppy and a network Windows 95 >location? You lousy Microsoft freaks! They will be linux boot disks that will run either Mprime v19, or Brian's factor95.c. We haven't decided whether to use Token Ring (has the advantage of being free), or ethernet (has the advantage of good development under Linux). The assignment server will probably be something very simple, maybe just using rlogin and perl. But the thing isn't built yet, so this is just a pipe dream. -Lucas _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
RE: Mersenne: massive GIMPS cabinet
> Having one power supply per computer, besides the convenience of having it > self contained, is the fact that the fan in a power supply is used not only > to cool the supply itself, but to circulate air throughout the entire case. > This is especially true for ATX spec cases and supplies, but is a general > rule of thumb for all systems. The main problem with running one supply/system is that I simply don't have that many supplies. These are mostly old ALR computers (486/66's) which I was able to save from the dumpster at the used computer store that I work at. We took the standard AT power supplies out of them, and sold them as used supplies. It certainly would not have been good for my job if I had said "Hey can I have these twenty $10 items, I thought you wouldn't mind." Images of the sarcastic comic book shop owner on the Simpsons "Please take my money *I don't want it*." Motherboard connectors are plentiful as people often bring in bad PS's, and I have been cutting off the connectors as of late. Though of course this involves bulk soldering :(, but that was the "fair amount of work" I mentioned. > You mention having central cooling for a cabinet, but I wonder if the added > power that a central cooling unit (a 120V cabinet fan?) is offsetting any > potential power savings by running less supplies total. Same problem as above, but when you add up the cost (in watts) of 20-30 12V fans, the gains become a bit more apparent (though still possibly not worth it). > Even though most power supplies come in ratings of at least 220W or so, the > average motherboard uses only a fraction. More power savings can be had by > finding less watt hungry hard drives. Laptop drives are 2.5" and generally > consume far less power than your average 3.5" drive. There are adapters > aplenty from electronics shops that let you plug your 2.5" drive into a > normal IDE cable. CD ROM drives and floppies are big power hogs too, but > they're not on all the time anyway, so that's not a problem. They will have only a floppy attached, which will run once (at boot up). > As long as you have fun, why not? :-) Of course, then if you have one > supply go out, you lose all your computers. But there's always a tradeoff > between cost and reliability. The servers I work with (even the storage > units) all have N+1 power supplies...but the cost! Whew! This shouldn't actually be a problem as the computers will only be running factoring assignments, and they should get these only a few at a time. The assignment server will be running on a UPS, and will keep track of which exponents are assigned. -Lucas _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: STOP BASHING PEOPLE WITH SLOWER MACHINES!
> The problem I have with slow computers is that I cannot afford to run > them. A 40MHz 486 uses about 20 Watts, a 400MHz AMDK6 about 40 Watts. > However if you have your own hydroelectric power supply, or if someone > else is paying the electricity bill, the situation is different. If you are running the computers *anyway* then I doubt that Prime95 adds that much to your electric bill. Also, much of the power in computers is consumed in cooling and powering them. By using 1 power supply for multiple computers, you can save a bunch of power. I am working with a friend of mine to do just this. We have 2 HP mainframe PS's (500W), an older mainframe PS (circa 1980) that I got at a yard sale (300W), and several PS's from IBM microchannel servers (~200W each). With a fair amount of work :), we hope to have a number of 486/pentiums in a cabinet with central cooling. These computers will (if we ever get the thing built) be factoring Mersenne numbers in the DecMega range. This will (of course) still draw a massive amount of power, but it has the decided advantage of all the hardware being free! This is still an impractical watt/cycle, but we're doing this for the experience (TM). BTW, does anyone know of a DOS/Linux Mersenne factorer, written in assembler that can find 64 bit factors? (Other than Brian's factor95.c, I want to know what's out there) Thank you, -Lucas _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: Re: A possible venue for a GIMPS meeting
> "Good" number theory meetings are relatively common, but this > "Millennial Conference" looks like it will be exceptional. The list of > speakers is already very impressive and they will have "broadly accessible > survey lectures" (though that couuld mean many things...) Because of that, > it may be worth folks going to the expense to come. What do you think? > Should we try to organize something? I'm definitely in favor of it! Of course that could be because the U of I is about 45 minutes away from me by car, so I'm going whether or not you all are going. -Lucas _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Pepin's Test, etc.
> If Pepin's primality test was run on F24, we could determine if F24 was > composite or prime. The chances that F24 is a psuedo-prime (a composite > pretending to be a prime) are very slim so it is worth the time to run the > test. I estimate the time required would be 6-9 months and we could do it > with existing software. Pepin's test on Fermat numbers is deterministic. There is no such thing as a Pepin psuedo-prime Fermat number. -Lucas P.S. Shouldn't this discussion be on Primes-L? _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Telling people to FAQ Off.
> Lucas Wiman made a wonderful job of the FAQ - but not *every* question > is in there... if it were, what would be the point of having a mailing > list anyway? Nor should every question be in there. I wrote the FAQ to promote *interesting* mathematical discussion, and prevent rehash of the same questions every couple of weeks. Besides, where do we draw the line? "Why can't people read back issues of Math. Comp. from 1930?" > Or is, as Paul says, the list meant to be a > forum for people to shoot down every well-meaning question just because > they're farther up the learning curve? I understand the frustration with people who ask "simplistic" questions, I mean I wrote the FAQ for goodness sake. But if a question is that annoying to you, delete the message and let others (who have more patience) field the question. Don't waste your obviously quite valuable time with such an intellectually lazy simpleton. > > *** Why? The mathematics is simple and well understood and has been known > > for centuries. Did you check the literature first, before wasting your > > time?? I find that often to understand something fully, I must derive the theorem on my own. I don't know why that is, but remember not everyone learns by reading endless books about theory. > My 8-year old is fascinated that she can multiply by 9, add the digits up, > and get back to 9 again. Perhaps I should take the above villain's advice, > tell her she is wasting her time, and ignore her completely. I think not. An excellent point! > As Lucas Wiman recently said to me (off-list, and I hope he doesn't mind me > quoting it), what if Hardy had instead said, "This Indian fellow is not > worth my time?". I don't mind a bit. > Those who recognize it, please, just smile about it. HaHaHaHaHaHa! :) -Lucas _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Cut the Crap!
> Can we cut the crap on this list? Hear, Hear! Especially the neo-poaching thread. This is simply too volatile and pointless a thread to waste our time on. Quite frankly, I'm also getting kind of annoyed with "When do you think we will see a [power of ten] digit prime?" type questions also, though some of the subtreads have been interesting. > Better yet, can we have another mailing list that is just announcements? Interesting idea, and one that makes sense for those who have less time on their hands. It seems almost like the FAQ has reduced math on the list and increased pointless "prediction" questions. Though of course I am probably just confusing correlation with causation. -Lucas _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Down With The Evil Thread
><<1) What is the approximate P-90 computing time to test for primality >for a 1, 10, 100 million (& 1 trillion!) digit Mersenne Primes?>> >Generally, a billion comes after 100 million, but I can't remember how the >British and other countries work with billions. And I don't think that many >people run P90s now for GIMPS I hope. Why not? A P90 adds 1 P90 CPU year per year (give or take). Not everyone can afford a PIII/550. >> >Moore's Law. Computers double in power approximately every 18 months. Has >worked for over a decade. Will _probably_ work for at least the next 5 years >and even up until 2020. At or around 2020, transistors hit the .01 micron >quantum limit, and "conventional" computing reaches its peak. Then, we break >out the Pentium XIV Quantum Computers, and proceed merrily on our way. :-) By that time (hopefully) the Intel architecture will be dead. I *really* hope that mass market computers in 2020 are not backwards compatable to the 8086, as that would be truly stupid (after all, my computer isn't backwards compatable to Multivac). In fact my computer would probably be much better off if it weren't backwards compatable to the 8086. Imagine how fast a version of George's program would be if everyone used ULTRASparc or MIPS or whatnot instead of the Intel... -Lucas _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Size of Mersenne Primes - 3 Questions
> OK - I'm not a math guru, and am new to the list. I can't find a > recent archive so I hope this isn't a repeated question. Perhaps > there is someone out there that could help me get some answers to the > following basic questions & ideas. Feel free to send me email > directly. Thanks! Check the FAQ, mentioned at the bottom of every message, www.tasam.com/~lrwiman/FAQ-mers > 2) What are the approximate N's that correspond to the beginnings of > these areas? See the FAQ, Q5.3. > 3) Assuming the continued (exponential?) growth of GIMPS, when will > GIMPS begin to assign work in each of these areas? I think it is parabolic. I seem to recall that someone said we should reach 20.5 million by spring 2005. I don't know when we are projected to reach the deca-mega-digit range. I think the stats are available at http://entropia.com/ips/ though I'm not sure. > I suspect that the ranges for N that GIMPS is searching are far from > the next eligible EFF prize for 10 million digit primes. I was > wondering if anyone knows what the smallest N is that gives a 10 > million digit prime might be. (I have no way to calculate it myself.) We are searching far from that range. I imagine that a number of people would begin testing in that range after V19 becomes available. -Lucas _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Evil, evil prize thread
>> >That figure seems a tad high. After double-checking, there would be a 0.01% >chance that BOTH tests had failed, which seems very high to me. Well, the likelyhood that a failure occurs may be 1%, but the likelyhood that a double check will not catch it is much lower. This is do to the fact that (barring bugs), the likelyhood that the numbers produce the same 64-bit residue is very, very low. Probably somewhere between 2^-64 and 2^-128. -Lucas _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
RE: Mersenne: Mp and E-Cash
>Unless George/Scott set some legal mumbo jumbo that ties into use of the >program/source/services, they're simply not "entitled" to any prize money. I'm forced to agree with Aaron, aparently at gunpoint :-) (and I said this a while ago, BTW). Even if they (George and Scott) did this, then there would still be MacLucasUNIX, or everything else in the mers package, as well as Ernst's program, and good ol' lucas.c. Any of these could be used. We've really got to put our feet back on the ground here. If we did put a license change on all of George's program derivitives, we would still have to get Will and Ernst to change their copyrights, and Richard Crandall. In fact, is the DWT patented? If so, Richard Crandall could claim the $100,000 for himself since I think that the programs that have a prayer of finding the Deca-mega prime would use his algorithm. If someone read on George's page "running this software means that you lose most of the prize money." They could do one of 3 things: (1) Say "Oky-doky" and download/run George's program (2) Say "Well, (sensored) you" and continue surfing (3) Say "Where can I get another program?" and find the others > I would imagine that the way they dole out the prize money is because use of > their software implies agreement with certain terms, i.e. that you agree > with the prize money disbursement outline. I didn't find anything specific, but then I didn't try and join them. I either missed it, they just "fudged" over it and hope that no one notices, or the RSA announcment covers this somehow. > And again, the first deca-mega-digit prime may not be a Mersenne > anyway...who can say? :-) Yah, it could be proth, or something. -Lucas _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: Hardware FAQs
All, On the subject of a hardware type FAQ/section in FAQ, here are the few FAQs that I could think of off the top of my head. I'm guessing others can think of more. I'm really not qualified at all to write about win95/nt/os2 questions. I've never used os2/nt, and I haven't used win95 in over 3 months. I haven't had it on one of my computers in over 6 months. I never ran any Mersenne related software on any of these platforms. Etc... Q: Does Prime95 decrease battery life on a laptop? Q: What is a Roundoff error? Is my computer broken? Q: Why does my computer start making noises when I run Mprime/prime95/NTprime? These I can answer pretty well. For other suggested questions, I should probably be able to get the answers out of the archives. -Lucas P.S. Are archives available past February 1998? _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: Links in the FAQ
I added a supplemental resources, and references section to the FAQ. Feel free to send me any links/books that you think should go in there. I'm trying to keep everything at least tangentaly related to the FAQ's on this list (and yes, the sites about general primality proving, and factoring are supposed to be there)... Thank you, -Lucas _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Worth it?
Here's something interesting, it *might* allow us to almost eliminate the x squarings in p-1 factoring. P-1 factoring is based upon Fermat's little theorem which states that with gcd(a,p)=1, p prime, a^(p-1)==1 mod p. Now, say we are factoring the number n, and p|n. We assume that (p-1)|q (hence q needs to have small factors), therefore a^q==1 mod p. Then we find (a^q-1) mod n, and then find gcd((a^q-1) mod n,n). If it is not equal to 0,1, or n then you have found a non-trivial factor (note, a result of zero would occur when (m-1)|q, and m was a base a Fermat prob. prime). (Now none of the variables in the previous paragraph carry over into the next :) What if we use 2 as a base? Well, for mersenne numbers, this might be to our advantage. Note that 2^n==1 mod Mn, hence 2^q==2^(q mod n) mod Mn. This would bring us down to (at most) log_2(n) squarings, which is insignificant. The possible problem (other than the required gcd) is this: Take 2^(a#)-1 has the factor (the product from 1 to a, p prime, of 2^p-1) Where # is the primorial function. Now, as I understand it, each prime number is "assigned" to a certain Mersenne, and this may or may not cause problems, I don't know. (Note that even after the removal of the trivial factors, there is still a very large number remaining). This would allow us to have huge, and I mean fricking huge B1 values, for no extra cost. Maybe even as high as 2^32. Using a linear approximation of my pseudo-primorial function in my previous posting, I get this number would have around 6.18*10^9 bits (627 megabytes), though it could be calculated indirectly (1.9*10^8 multiplications mod n). If this pans out, then P-1 would have decided advantages over trial factoring (past a certain point), even at lower exponent ranges. -Lucas _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Squaring algorithm...
> So the sqaure performs in O(n) time. Plus, you could already throw in the > sub 2 by starting at -1 instead of 1. And figuring out the mod is just as > easy. Yes, the runtime is proportional to some number, but that number is *not* the number of digits (as n usually means)! It is the number we are squaring! Unfortunatly, this would be quite inefficient compared even with traditional multiplying techniques. -Lucas _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Worth it?
>> If you are doing stage >> 1 only I believe that I had looked at a b1 of at least 100K which would >> translate to about 140K (I'm trusting your numbers) squarings. I think >> that that is still less than 5% of the number of squarings for a current >> LL test, and would reap factors for about 5% of the numbers so would at >> least break even. My numbers are quite suspect. I just did the primorial of _10,000_ not of 100,000 (though, the prime number theorem tells us that the primorial function should approach e^x , hence the number of bits would be linear). I also did not take into account that (for example) it is more likely that a number (p-1 in this case) will be divisible by 4, rather than 5. That is to say, instead of taking the strict primorial, I should have found the product of p^floor(log_p(B1)), p prime, from 1 to B1 (note that p^floor(log_p(B1)) is the largest power of p not greater than B1, because if it was bigger than B1, getting a bigger B1 value would make more sense). (whew!) Well, after all that, I found out that David's misinterpretation of my original estimate is very close (shows the power of S.W.A.G.) The number of bits for B1=100,000 is 144,330. (plus the bits of the exponent, obviously) (Off topic, when I computed that value in Landon's Calc program, my computer PII/233 started making a weird humming noise. The noise stopped when the calculation finished. Very strange indeed...) > There is obviously a breakeven point between trial factoring (which > will _definitely_ find any factors up to the limit specified) and P-1 > (which might not). So, are we in any sort of position to estimate > where that breakeven point might be, for exponents say around 10 > million? Yes, there is no point in finding a 32-bit factor with something that might take weeks, when it would take ~1/5,000th of a second to find it with Brian's factor95 program. I suppose the estimate is based upon the probability that one number would divide another, based on the factors of the numerator. I'll get back to you. > The fact that we would still be running trial factoring up to some > limit (though maybe a little lower than we are at present) would to > some extent remove the objection that an exhaustive search of at > least part of the range of possible factors is useful. As I mentioned earlier. However, we do have loads of factoring data, plenty enough to test conjectures with... (well, probably enough, anyway) Besides, who knows, maybe the factors of Mersenne numbers with small factors of P-1, follow a very strict rule, while they get less predictable when the factors of P-1 get large. > There is going to be another breakeven point between P-1 factoring > and LL testing - if we run a LL test, then (barring accidents) we get > a definitive result in a predictable time, whereas we could run P-1 > "for ever" on even quite a small exponent without arriving at a > definite result. Same is true of trial factoring. What might be useful is if someone were to factor a large number of the k in 2kn+1 (n is the exponent) and see if any patterns emerge (i.e. find out if the p-1 usually takes special factors, other than the usual ones). This would further increase the "deterministic gap," even though it might increase the number of factors found. Man, the p in P-1 and the usual p in Mp are easy to get confused! > Can we speculate on approximately how much memory would be needed, as > a design exercise? In any case, it needn't rule the scheme out > altogether if we find that some systems aren't able to contribute > usefully by reason of limited memory. After all, not all systems can > contribute usefully to some other tasks, e.g. it's a bit pointless to > try to run a LL test on a 7 million range exponent on a 486, though > the program _will_ try, if you ask it to! Well, this might not be a problem. If P-1 tries more than one base, all that is required (per Mn) is *one* gcd. We just multiply the remainders from the bases mod Mn, and then take the gcd on the final remainders. We could have the program prompt the user for the time when the computer is on but not being used when they ask for a P-1 assignment. Or, we could have it run so that the program stops functioning when the computer is being used. It could just save the intermediate files to disk, to free up memory for the user who (graciously) gives us their CPU cycles. -Lucas Wiman _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: FAQ registered with search engines
I added the FAQ to the following search engines: Lycos Excite Yahoo Altavista AOL netfind Webcrawler HotBot InfoSeek -Lucas _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Worth it?
Sorry if this is sending out twice, I wasn't sure that it got sent the first time... >> As I understand the Pollard P-1 algorithm, the time required for 1 bit of >> the exponent would be equal to 1 iteration of the LL test (one squaring >> mod Mp), so values wouldn't be that hard to create. (timing values, for comparison with regular factoring) >> The main problem is >> that to get a bound of any reasonable size, and try multiple bases, you >> are looking at a time comperable to the LL test. (I suppose that on further investigation, with a bound value for factors of the exponent at 10,000 we are looking at about 14,000 squarings mod Mp, which is really not all that many) >> Also, one of the keen >> things about GIMPS is that in its search for primes, it came up with loads >> of factoring data for Mersennes. However, the P-1 algorithm would make any >> factor distribution data a lot less usable (as it would not include P with >> P-1 having a large prime factor). (That is to say, if the P-1 algorithm was used, it still couldn't find all the factors <2^64, unless we are talking about incredibly high bound values) >> On the other hand, the P-1 algorithm can take advantage of the special >> form of Mersenne factors. We know that P-1 must be divisable by the >> Mersenne exponent, and that in 1/2 of the cases, it is divisable by 8. (we know that the factors must be of the form 2*k*p+1, hence the factor-1 must be divisable by 2*p, or in the form 8*n+/-1, hence the factor-1 must be divisable by 2 or 8) > I'm not sure that I understand what you are saying, but the > following are a few observations that I made when I looked at the > problem a few years ago. The major stumbling block for an efficient > P-1 is the implementation of a time and memory efficient GCD. If one > has a good GCD algorithm then a stage 1 only implementation becomes > cost effective for exponents around 3 million. > However, the cost savings is tiny, probably less than a > percent overall. The major benifit is that one does not need to double > check the exponent. Yup, silly me. You are quite correct, of course, that the GCD is the most time consuming part. I imagine that from what you are saying, it gets more cost-effective the higher the exponent. How does it look at around 33219281? -Lucas _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Worth it?
> We should try to increase this probability before starting any > full LL test, perhaps by using better factoring algorithms. > Will v19 have P-1 code that works with numbers of this size? > But even with P-1, we might not be able to factor that much > further. The time consuming part of P-1 are multiplications > mod Mp just as in the LL test, so the crossover point between > raising the factoring limit and starting the LL test will be a function > of p (the number of interations in the LL test) and less than linear, > that is, we might not get very far. > Do we have estimates already what the optimal bound > values will be for trying P-1 on a given Mp, to minimize the > (time of P-1 test) + (time of LL test * chance of not finding any factor) ? As I understand the Pollard P-1 algorithm, the time required for 1 bit of the exponent would be equal to 1 iteration of the LL test (one squaring mod Mp), so values wouldn't be that hard to create. The main problem is that to get a bound of any reasonable size, and try multiple bases, you are looking at a time comperable to the LL test. Also, one of the keen things about GIMPS is that in its search for primes, it came up with loads of factoring data for Mersennes. However, the P-1 algorithm would make any factor distribution data a lot less usable (as it would not include P with P-1 having a large prime factor). On the other hand, the P-1 algorithm can take advantage of the special form of Mersenne factors. We know that P-1 must be divisable by the Mersenne exponent, and that in 1/2 of the cases, it is divisable by 8. -Lucas _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: The $100,000 award for 10,000,000 digit prime
> I hate the charity idea only because it seems to me that a "Mersenne > Scholarship Fund" would do much more for our project in many ways: > > 1. We could control where the money goes to a greater extent. > 2. It would allow us to contribute a great deal more mathematics in > general. > 3. More notariety. I doubt that we could actually get many scholarships out of the $100,000. Maybe scholarships for 6 or 7 people, any more and we start sending them to community colleges. (though, if you want to send someone to college, I wouldn't mind it ;) I like the idea of using some of it to get George some computers, and maybe pay his electric bill for a year :) Ok, that's maybe 10K at the outside, then we run the risk of just cluttering his house with computers. I also like the idea of giving some of it to Scott. And though I think that Colin Percival is right when he says that Scott gets most of the reward from the publicity, he would get this anyway. Especially if newpaper articles read $15,000 was given to Scott Kurkowski, who gives his server time to run the primenet software... Different message, same author: > 10% for George > 10% for Scott > 10% for Discoverer > 10% Charity/Scholarship (The Mersenne Scholarship Fund) > 60% divided evenly to everyone who contributed, based on CPU cycles > contributed after the last Mersenne prime found. ~6,000 people in gimps. $60,000/6,000=$10 on average. Hardly worth doing... Though personally, I'm not to comfortable with the idea of splitting the money away from the winner. I doubt that the winner would actually do anything to deserve the money, but I also think that many, many people would be discouraged to read "if you are the lucky discoverer, you don't get to keep 90 grand that the EFF would give to you were it not for the software you are about to download." This would also entail a restrictive license agreement, which some lawyer would write, and we all know that a "volunteer project's" credibility goes straight down the tubes when lawyers get involved. Hey, if you don't believe it, try reading your bank statment, and your credit card bill's fine print. Then tell me how much respect we would lose in the name of legality. I think the only reasonable way to get any money out of the hands of the finder would be to ask them to give some of it away. I should think that there would be many people who would be willing to do this, but I don't think it would make us look good to write and ask to give it away. -Lucas Wiman _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: Meetings (was $100,000...)
> Have a party... wouldn't YOU like to meet the other people working with > GIMPS? Frankly, this wouldn't be THAT expensive, and we could even make > it a symposium or something call for papers or research in the area of > computational number theory. I like the idea of a symposium, I'll bet that colleges would be willing to host it. In Illinios, we could host it at UIUC (Urbana), ISU (Normal), or U of C (Chicago). Maybe we should set a number of these up. I would personally like to meet the GIMPSers in the midwest. I guess the biggest problem would be coming up with the papers. I don't mean to offend anyone, but I doubt that many of us are involved enough (or know enough) to write papers, and such. I suppose those of us with more interesting computational setups could tell about them, or something. Those of you with ideas for an Illinios/midwest meeting, write me privately. Or we could have monthly meetings in coffee shops like 2600 does... That'd be keen. -Lucas Wiman _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: General release of the FAQ
I think the FAQ is ready for "general" release. I have been working on it for 20 days, and it includes most of the FAQ's and some of the not-so-FAQ's. I have tried to make it as understandable as possible, though I am not a very good writer. Please send me any errors in it (technical, spelling, and gramatical). There were of course many contributers to it other than me, those were: Peter Montgomery Chris Nash Jud McCraine Chris Caldwell Brian Beesley Ken Kriesel Pierre Abbat Jay Hill Vincent Mooney Jr. I would like to thank them all. At many points, I directly quoted these people, so if any of you have problems with that, tell me. I will register the FAQ with the major search engines in the next few days. I really hope this FAQ reduces repetition on the mailing list. thank you all, Lucas Wiman Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne: Adding FFT to the FAQ
All, I tried to add an FFT section to the FAQ, and here is what I got: (please add, or correct errors...) -Lucas Wiman P.S. Sorry if the FAQ is causing more traffic than it is supposed to prevent ;) === Q6.1: How can we perform the massive squarings required for the LL test in reasonable time? A: We use a method known as FFT convolution. In this method, we take the number that we are squaring, and run an FFT on it. This results in an array, and we square each element in that array, and run an IFFT (iverse-FFT). This yields the answer mod some number. This operates in O(n*log(n)) time, which means that it is proportional to n*log(n). This is a signicant improvement over normal multiplication which is O(n^2). === Q6.2: What is an FFT? A: An FFT is a Fast Fourier Transform. These are often used in signal processing, and they are basically transforming a signal into a series of discrete sine and cosine waves. For more information on FTT's, see the following websites: "http://theory.lcs.mit.edu/~fftw/fft-links.html" FFT Introduction (many FFT links) "http://www.spd.eee.strath.ac.uk/~interact/FFT/"Fourier Transform in Signal Processing "http://cfatab.harvard.edu/nr/bookcpdf.html" Numerical Recipes in C (See parts on FFT) I have also heard that the book _Who is Fourier_ is quite good, though I have not read it. Thank you Vincent J. Mooney Jr. Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne: ECPP for intel (linux)
Does anyone know where I can obtain a copy of ECPP for the intel platform, specifcally Linux? I apologize for the slightly off topic-ness of this question... thank you, Lucas Wiman Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Re: Mersenne: subtracting 2: error in FAQ (?)
>>> Speaking of Q2.6, I've heard that with Crandall's DWT, the subtraction >>> 2 step costs nothing at all. It's done automatically within the >>> transformation. Try checking this with George Woltman. >>Is this true? >Not knowing for certain; I thought the DWT did the modulo for you, not the >subtraction? Yes, it does the mod. I read in the archives that x^2-2 could be interpreted as a "delta polynomial" which would give it a valid Fourier transform. I was wondering if this was what was actually performed. I doubt it is as optimizing the -2 step would hardly produce amazing results. Optimizing the -2 step down to nothing (with the amazingly high estimate of 1/50,000th of a sec) would gain only .3 CPU years for all exponents in the 7million range. I was just making sure. -Lucas Wiman Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Re: Mersenne: Proof of factor forms
> Could someone show me a proof for(if there is one): > The number 2^p-1 has factors in the form of 2pk+1 > where k is any positive integer. try http://www.utm.edu/research/primes/notes/proofs/MerDiv.html -Lucas Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne: subtracting 2: error in FAQ
All, I recieved a message pointing out a possible error in my FAQ: > Speaking of Q2.6, I've heard that with Crandall's DWT, the subtraction > 2 step costs nothing at all. It's done automatically within the > transformation. Try checking this with George Woltman. Is this true? -Lucas Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
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
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 .7037112494844799 .17639213071023674558 .0003008716540349 .12470823607869289763 -.00023050052960705550 .09703234411470490163 .00012233110664848727 .07935978659553184394 .00017854054790701622 .06702234078026008669 .7555114964688849 .05768589529843281093 -.00030605167925394399 .05168389463154384794 .00053137218416255899 .04534844948316105368 -.00040904107751407172 -Lucas Wiman Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
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> 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
