Mersenne: Re: digits vs exponents FAQ
At 09:09 AM 1999/06/29 -0400, Jud McCranie [EMAIL PROTECTED] wrote: At 04:16 AM 6/29/99 -0400, Lucas Wiman wrote: All, Here is version 1.1 of the FAQ. Here's a question that needs to be addressed: how to go from digits to exponents, and exponent to digits. By all means include it in the faq; there's been too much repetition, including wrong responses, now and in past months. Here's a draft: Sometimes it is useful to know the relationship between the exponent of a mersenne number and the number of digits it has in some number base. How do we calculate in either direction? (q) How many digits are there in the binary representation of 2^n-1 (or any number 2^(n-1) = x = 2^n - 1) ? (a) n Examples: n=1, 2^(1-1)=2^0=1= 1(2); 2^1-1= 1 =1(2). n=2, 2^(2-1)=2^1=2= 10(2); 2^2-1= 3 = 11(2). n=3, 2^(3-1)=2^2=4= 100(2); 2^3-1= 7 = 111(2). n=4, 2^(4-1)=2^3=8=1000(2); 2^4-1= 15 = (2). Hey, a pattern's emerging here. (q) How many digits are there in the hexadecimal representation of 2^n-1? (a1) int((n+3)/4) (a2) take the number of binary digits, divide by 4, then round up. (q) How many digits are there in the decimal representation of 2^n-1 ? (a) D = int(n * log_10_(2) + 1); log_10_(2) ~= 0.301029995664 = log (base 10) of 2 Examples: n=1, int(1* .3010... + 1) = 1; n=2, int(2* .3010... + 1) = 1; n=3, int(3* .3010... + 1) = 1; n=4, int(4* .3010... + 1) = 2; ... n=10, 2^n-1=1023; int(10*.3010...+1) ~= int(4.01029995664) = 4; n= 3321925, int(3321925* .3010...+1) ~= int(100.068346) = 10^6 n= 33219281, int(33219278* .3010...+1)~= int(1000.1123) = 10^7 n= 332192807,int(332192807*.3010...+1)~=int( 1.2508)= 10^8 n= 3321928095,int(3321928092*.3010..+1)~=int(10.131)= 10^9 (q) What about in some arbitrary number base? (a) For base a as in arbitrary, 2^n -1 will have r digits where r=int(n*log_a_(2) + 1-epsilon), or rather r=ceil(n*log_a_(2)) (allowing for the base a to possibly be a prime number), Example: a=7, n=3, log_2_(7)~= 2.807354922058; log_7_(2)~= 0.356207187108 2^3-1= 7 = 10(base 7) Derivation: 2^n-1 = a^r-1 or it won't fit in r digits in base a 2^n = a^r n * log_a_(2) = r (q) What is the minimum exponent n for 2^n - 1 to have at least D decimal digits? (a) 2^n-1 10^(D-1) -1 2^n 10^(D-1) n log_2_( 10^(D-1) ) n log_2_(10) * (D-1); log_2_(10) ~= 3.321928094887 Examples: D=1, n log_2_(1); n 0 D=2, n log_2_(10); n 3.321...;2^4-1=15; 2^3-1-7 D=3, n log_2_(100); n 6.642...; 2^7-1=127; 2^6-1=63 D=10, n log_2_(10)*9; n 29.897... 2^30=1,073,741,824 D=100, n log_2_(10)*99; n328.87.. 2^329= 1.093625362392e+99 D=1000, n3318.6 D=1, n33215.95 D=100,000, n332189.48 D=1,000,000, n 3321924.772959 D=10,000,000, n 33219277.62694 D=100,000,000, n 332192806.1668 D=1,000,000,000, n 3321928091.565 Ken Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Re: Mersenne: Re: 10,000,000 digit prime
On 29 Jun 99, at 18:06, Lucas Wiman wrote: Therefore, to find the first one with 10^7 digits, we find ceil(10^7/log_10(2)) which is 33219281. NO! The _correct_ formula is ceil((10^7-1)/log_10(2)) = 33219278. The point is that 2^n have 1 decimal digit for n 4 ;-) As it happens, 33219278, 33219279 33219280 are all composite and therefore are not contenders for generating a Mersenne prime. 33219281 _is_ prime, the status of 2^33219281 is (so far as I know) not known at this time ... unless someone found a factor bigger than my 2^40 search limit. Regards Brian Beesley Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Mersenne: distribution of factors (was 10,000,000 digit prime)
NO! The _correct_ formula is ceil((10^7-1)/log_10(2)) = 33219278. Aww, mine was pretty close ;-) The point is that 2^n have 1 decimal digit for n 4 ;-) As it happens, 33219278, 33219279 33219280 are all composite and therefore are not contenders for generating a Mersenne prime. 33219281 _is_ prime, the status of 2^33219281 is (so far as I know) not known at this time ... unless someone found a factor bigger than my 2^40 search limit. Well, I don't think that 2^33219281 is prime (factors 1, and 2) :-). But 2^33219281-1 has no factor less than 2^52. No I am not searching in this range, but I made a made this a special case. I am currently searching between 2^47, and 2^50. Which should take almost two more months (unless I find a load of factors, that should make things go faster :) In that range, I an finding about 5.5% to have factors. If this holds, that would be about 3970 new factors, added on to all the other factors that I've found, that makes 19868 factors, less than half of those less than 2^40, despite the fact that the range I tested is 1023 times larger. I realize this is probably a FAQ, (and I intend to put it there), why is the distribution of factors so non-linear? -Lucas Wiman Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
SV: Mersenne: M38 guess
On Tue, 29 Jun 1999, Ken Kriesel wrote: Make my guess for M38, p~=6,740,000 I'll guess p~=6,740,001 :-) Kel I would like anyone betting on M38 tu use an exact exponent! Not ~= blahblah If u dont know any exact exponents, then check http://www.entropia.com/primenet/cleared.txt and pick one there that could be close... You wont be able to see the exact exponent of M38 of obvious reasons, but it can give you an idea... Regards, /Lars Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Re: Mersenne: distribution of factors (was 10,000,000 digit prime)
At 03:05 AM 6/30/99 -0400, Lucas Wiman wrote: I realize this is probably a FAQ, (and I intend to put it there), why is the distribution of factors so non-linear? Because small factors are more likely to divide a given number. +--+ | Jud "program first and think later" McCranie | +--+ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Re: Mersenne: Re: digits vs exponents FAQ
On 30 Jun 99, at 0:44, Ken Kriesel wrote: Here's a question that needs to be addressed: how to go from digits to exponents, and exponent to digits. By all means include it in the faq; there's been too much repetition, including wrong responses, now and in past months. Actually, things are a great deal easier than Ken makes out. Notation used, square brackets means the "integer part of". I don't like the notation "int(x)" since this has different interpretations in different languages - does it mean chop to zero, chop down or round to nearest or even? "ceil(x)" and "floor(x)" are precise, but meaningless to C non-programmers. Let k be the logarithm of r to base 2. Note that 2^p has [p/k] + 1 digits when represented in base r. k can be calculated as log(r)/log(2) using logarithms to any arbitary base. (a) If k is not a integer (i.e. r is not an integer power of 2), 2^p-1 has the same number of digits as 2^p, because there can be no integers a, b such that a^b = 2^p unless a is an integer power of 2. (b) If k is an integer (i.e. r is an integral power of 2), subtract 1 from the number of digits in 2^p, provided that k divides p. The reverse algorithm (getting the smallest exponent with n digits) is actually even easier: p = [(n-1)*k] + 1 is the smallest p such that 2^p-1 has n digits when represented in base r. (This works only for n 1 because 2^0-1 = 0 still has 1 digit). Note, the above is actually true irrespective of the numerical value of the symbol "2" - i.e. replace "2" by "3" in the arguments above, and they still work! Regards Brian Beesley Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Re: Mersenne: M38 guess
On Wed, Jun 30, 1999 at 07:43:33AM -0400, St. Dee wrote: I'll guess p~=6,740,001 :-) I'd recommend using a prime, but that's your problem, of course. Well, nobody has gone _over_ your guess, so it probably doesn't matter. (In all other case, choosing the highest non-checked prime above 6,740,000 would have been better.) /* Steinar */ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Mersenne: Re: M#38 and a few questions
Hi all, At 04:02 PM 6/27/99 -0400, Jeff Woods wrote: Because of the EFF award money rules, we "GIMPS at large" will not be permitted to know what the exponent was, or who discovered it, until an article has been published in a peer-review academic research magazine or such. The EFF rules have been clarified such that if two claims are made on the $50,000 award, then the discovery date determines the winner. This gives us plenty of protection in announcing the new prime now. Scott gave out the press release today to the San Jose Mercury News and I should be emailing the list and updating my web pages soon. Note that sometimes these "human interest" type stories are held until the weekend for publication. I'd like to thank everyone for their patience while any kinks were worked out in the EFF claims process. They have never said we couldn't announce the new prime, but I've held off until we were sure it was risk-free to do so. Slowinski used to test huge numbers of primes...is he still doing that? David Slowinski is no longer working for Cray, so I doubt that he is still orchestrating an organized search. GIMPS does have one member who uses Slowinski and Gage's program and a Cray to look for primes. The latest prime is being verified by him. Paul Gage, who still does work for Cray, can then backup the new find. Regards, George Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Mersenne: SF Examiner story
Page A-12 of the June 30, 1999 San Francisco Examiner has a story `Math expert confirms a prime discovery' repeating the Oregonian story abut M38. The report does not give the precise exponent. The report mentions only George Woltman by name. Peter Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Mersenne: M38
I notice that there's a page on the net somewhere that lists M38. I take it that this isn't meant to be public information yet? The page belongs to a previous record holder... Simon (guessing around 6972???, but then I know now :-). Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Re: Mersenne: Is M38 in Seattle Times ?
Yup. Page 3, section A, of Tuesday, June 29, 1999 edition of the Seattle Times. "Largest prime ever weighs in at more than 2 million digits" by Ruth Bennett, Newhouse News Service. Perhaps the most significant additions(and I may have simply overlooked these) to the online article (URL already posted) are: a few details about the discoverer (a Ford Motor company employee) and the observation that the previous record prime (about 0.9 million digits) would, if printed in 12 point type, stretch almost 2.5 miles. Does that mean that M38 is the first known 12pt 5 mile prime? Joth - Original Message - From: Luke Welsh [EMAIL PROTECTED] To: [EMAIL PROTECTED] Sent: Wednesday, June 30, 1999 7:43 PM Subject: Mersenne: Is M38 in Seattle Times ? Anybody in the Seattle area? "front section, page 3 of Seattle Times." of a recent edition? Online search fails. --Luke Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
