Mersenne Digest Sunday, July 11 1999 Volume 01 : Number 596 ---------------------------------------------------------------------- Date: Fri, 9 Jul 1999 12:58:43 -0700 (PDT) From: Kris Garrett <[EMAIL PROTECTED]> Subject: Re: Mersenne: Mersenne Numbers - --- Kris Garrett <[EMAIL PROTECTED]> wrote: > If it has not been proven that all mersenne numbers > greater than one is > prime free then here is a proof for you. > > 2^n-1 mod 4 = 3 while n > 1 because every 2^n while > n > 1 is divisible by 4 itself. > > On the other hand every odd square mod 4 is always 1 > because: > > if the odd number mod 4 is 1 then: > n(4)+1 could represent that number > (4n+1)^2 = 16n^2 + 8n + 1 which mod 4 is 1 > > if the odd number mod 4 is 3 then: > n(4)+3 could represent that number > (4n+3)^2 = 16n^2 + 24n + 9 or 16n^2 + 24n + 4(2) + 1 > which mod 4 is 1 > > thus the numbers can never be the same above one > when > the mersenne number mod 4 is always 3 and the odd > square mod 4 is > always 1. > Sorry I meant all mersenne numbers square free not prime free. _________________________________________________________ > Do You Yahoo!? > Get your free @yahoo.com address at > http://mail.yahoo.com > > ________________________________________________________________ > Unsubscribe & list info -- > http://www.scruz.net/~luke/signup.htm > _________________________________________________________ Do You Yahoo!? Get your free @yahoo.com address at http://mail.yahoo.com ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ Date: Fri, 9 Jul 1999 16:51:23 -0400 From: "Don Leclair - Toggle Software" <[EMAIL PROTECTED]> Subject: RE: Mersenne: Mersenne Numbers Hello, > thus the numbers can never be the same above one > when the mersenne number mod 4 is always 3 and > the odd square mod 4 is always 1. Your analysis is correct but your conclusion is wrong. You've proved that all Mersenne numbers greater than 1 cannot be odd squares but you haven't proved that they can't be square free. >From your analysis you can conclude that if Mn is *not* square-free, then it must have an odd number of factors that are congruent to 3 (mod 4). With M21, for example: M21 = 2^21-1 = 7 * 7 * 127 * 337 Breaks down as: 7 * 7 = 49 == 1 (mod 4) 127 == 3 (mod 4) 337 == 1 (mod 4) The previous conclusion can be generalized to simply: All Mersenne numbers greater than one must have an odd number of factors that are congruent to 3 (mod 4). - -Don Leclair ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ Date: Sat, 10 Jul 1999 14:57:13 +1000 From: Peter Foster <[EMAIL PROTECTED]> Subject: Mersenne: Why can't we... When doing an LL test we are always calculating the same series of numbers. The modulus is different, so we can't use the result of one test to help with another. I'm wondering why we don't do the following: Take 2 Mersenne numbers, m1 and m2 (m1 < m2). Do the usual LL series, but use as the modulus m1*m2. At the appropriate step, check if the remainder is divisible by m1. If so, then m1 is prime. At the end, check if the remainder is divisible by m2. If so, then m2 is prime. This allows us to do two (or more) tests for the price of one. What is the obvious reason we don't do this? Cheers, Peter - -------------------- Peter & Diane Foster Canberra, Australia ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ Date: Sat, 10 Jul 1999 07:34:26 +0200 (MET DST) From: [EMAIL PROTECTED] Subject: Re: Mersenne: Why can't we... Peter Foster asks: > When doing an LL test we are always calculating the > same series of numbers. The modulus is different, so > we can't use the result of one test to help with > another. I'm wondering why we don't do the following: > > Take 2 Mersenne numbers, m1 and m2 (m1 < m2). > Do the usual LL series, but use as the modulus m1*m2. > At the appropriate step, check if the remainder is > divisible by m1. If so, then m1 is prime. > At the end, check if the remainder is divisible by > m2. If so, then m2 is prime. > > This allows us to do two (or more) tests for the price > of one. What is the obvious reason we don't do this? In theory this is fine. But it is likely to cost more than making two separate tests. Suppose m1 = 2^p1 - 1 and m2 = 2^p2 - 1. Residues modulo m1 have p1 bits, and those modulo m2 have p2 bits. The time to square modulo m1 is estimated as O(p1*log(p1)) The time to square modulo m2 is estimated as O(p2*log(p2)). The time to square modulo m1*m2 is estimated as O((p1+p2)*log(p1+p2)). We'll assume p1 and p2 are large but have the same magnitude. For example, each might be between 6332000 and 6333000. Then log(p2) - log(p1) = log(p2/p1) is tiny compared to log(p2) or log(p1), so we approximate log(p2) = log(p1) and log(p1+p2) = log(2*p1) = log(2) + log(p1). The combined time to separately square modulo m1 and modulo m2 becomes O((p1+p2)*log(p1)). A single computation modulo m1*m2 takes time O((p1+p2)*(log(2) + log(p1))). For p1, p2 near 6 million ~= 2^22, the latter time is about 4.5% longer. This estimate is slightly optimistic. The techniques used for reduction modulo 2^p1 - 1 and 2^p2 - 1 don't immediately generalize to reduction modulo (2^p1 - 1)*(2^p2 - 1). Despite this, it may be beneficial writing a program which does several nearby exponents at once. Consider a SIMD (single instruction, multiple data) machine with n processors. Each of the n processors can be assigned a different exponent. All use the same FFT length, operating on local data unique to the processor's exponent. The larger exponents will need a few more LL iterations than the smaller exponents, but this gap in amount of work per processor will typically be under 1%. This scheme would require considerable local memory on each processor. Peter Montgomery ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ Date: Sat, 10 Jul 1999 02:12:31 -0400 (EDT) From: Lucas Wiman <[EMAIL PROTECTED]> Subject: Re: Mersenne: Why can't we... > Take 2 Mersenne numbers, m1 and m2 (m1 < m2). > Do the usual LL series, but use as the modulus m1*m2. > At the appropriate step, check if the remainder is > divisible by m1. If so, then m1 is prime. > At the end, check if the remainder is divisible by > m2. If so, then m2 is prime. > This allows us to do two (or more) tests for the price > of one. What is the obvious reason we don't do this? This would require more than double time. Think about it like this: Take two mersenne numbers 2^p-1, and 2^n-1 with p~=n (For the purpose of clarity we will assume they are close enough to be considered equal) Now, an LL test requires O(p*(p*log(p))) time. (~p multiplications of O(p*log(p)) time) Hence the time required to perform them on p and n is O(2*p^2*log(p)). But, the test you suggest would be require O(p*((2*p)*log(2*p)))=O(2*p^2*(log(p)+log(2))) Thus, your suggestion adds on O(2*p^2*log(2)) time. Hope that helps, - -Lucas Wiman ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ Date: Sat, 10 Jul 1999 07:59:21 +0100 From: "Brian J. Beesley" <[EMAIL PROTECTED]> Subject: Re: Mersenne: Why can't we... On 10 Jul 99, at 14:57, Peter Foster wrote: > When doing an LL test we are always calculating the > same series of numbers. The modulus is different, so > we can't use the result of one test to help with > another. I'm wondering why we don't do the following: > > Take 2 Mersenne numbers, m1 and m2 (m1 < m2). > Do the usual LL series, but use as the modulus m1*m2. > At the appropriate step, check if the remainder is > divisible by m1. If so, then m1 is prime. > At the end, check if the remainder is divisible by > m2. If so, then m2 is prime. > > This allows us to do two (or more) tests for the price > of one. What is the obvious reason we don't do this? I suggested something similar (doing 3 or more tests at once) about 6 months ago. My motivation was to improve the efficiency of testing using programs which have only power-of-two FFT code. There is a small decrease in efficiency in the FFT as the size goes up, but this could be more than offset by the gross saving in being able to do e.g. 3 tests in parallel in a 1024K FFT instead of 3 tests in series each using a 512K FFT. The killer is doing the reduction modulo (2^p-1)(2^q-1)(2^r-1). The point is that the "standard" DWT does the reduction modulo 2^p-1 for free. Unless someone can come up with a clever method of doing the reduction for "general" cases, it looks as though it's going to be a lot more productive to write code for transform sizes which are not powers of 2. Regards Brian Beesley ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ Date: Sat, 10 Jul 1999 13:22:04 +0200 (MET DST) From: Wojciech Florek <[EMAIL PROTECTED]> Subject: Mersenne: Re: Mersenne Wow... > > >HTTP Error 403 > > > > > >403.9 Access Forbidden: Too many users are connected > > > > Sounds like M38 gave www.mersenne.org some extra traffic? > > > This problem has been around for a few days. > > The other explanation is that the server has lost some TCP buffers > due to a driver bug or a denial-of-service attack. Such things are > known 8-( > > My FTP server has been unusually active this week (or, rather, > unusually not inactive!), in particular there seems to be a surge of > interest from Poland, with quite a number of people downloading > prime95.zip 8-) > > > Regards > Brian Beesley On Wed 7.7.99 there was an article in a Polish newspaper on the 38th known Mersenne prime. Scott Kurowski, Entropia.com, and the prize were mentioned. I had informed an author of this article about the discovery, so you can blaim me for this `a surge of interest from Poland' Wojciech Florek (WF, still beyond the first 500) Adam Mickiewicz University, Institute of Physics ul. Umultowska 85, 61-614 Poznan, Poland phone: (++48-61) 8273033 fax: (++48-61) 8257758 email: [EMAIL PROTECTED] www: http://main.amu.edu.pl/~florek ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ Date: Sat, 10 Jul 1999 10:00:10 -0400 From: Jud McCranie <[EMAIL PROTECTED]> Subject: Re: Mersenne: Why can't we... At 02:57 PM 7/10/99 +1000, Peter Foster wrote: >Take 2 Mersenne numbers, m1 and m2 (m1 < m2). >Do the usual LL series, but use as the modulus m1*m2. >At the appropriate step, check if the remainder is >divisible by m1. > >This allows us to do two (or more) tests for the price >of one. What is the obvious reason we don't do this? > If we had the full numbers of the LL sequence, this would work. However, in practice those numbers would get too large to work with. They are reduced mod the number you are working on at each step, and I don't think there is any easy way to make it work for more than one modulus. +----------------------------------------------+ | Jud "program first and think later" McCranie | +----------------------------------------------+ ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ Date: Sun, 11 Jul 1999 18:42:13 -0500 From: Ken Kriesel <[EMAIL PROTECTED]> Subject: Mersenne: Mersenne prime exponent binary representations and 1's frequency (incl M38) The latest mersenne exponent is added below. position p in p # of bit p in hex p mod 4 in list base 10 in base 2 1's places 1 2 10 1 2 2 2 2 3 11 2 2 3 3 3 5 101 2 3 5 1 4 7 111 3 3 7 3 5 13 1101 3 4 D 3 6 17 10001 2 5 11 1 7 19 10011 3 5 13 3 8 31 11111 5 5 1F 3 9 61 111101 5 6 3D 1 10 89 1011001 4 7 59 1 11 107 1101011 5 7 6B 3 12 127 1111111 7 7 7F 3 13 521 1000001001 3 10 209 1 14 607 1001011111 7 10 25F 3 15 1279 10011111111 9 11 4FF 3 16 2203 100010011011 6 12 89B 3 17 2281 100011101001 6 12 8E9 1 18 3217 110010010001 5 12 C91 1 19 4253 1000010011101 6 13 109D 1 20 4423 1000101000111 6 13 1147 3 21 9689 10010111011001 8 14 25D9 1 22 9941 10011011010101 8 14 26D5 1 23 11213 10101111001101 9 14 2BCD 1 24 19937 100110111100001 8 15 4DE1 1 25 21701 101010011000101 7 15 54C5 1 26 23209 101101010101001 8 15 5AA9 1 27 44497 1010110111010001 9 16 ADD1 1 28 86243 10101000011100011 8 17 150E3 3 29 110503 11010111110100111 12 17 1AFA7 3 30 132049 100000001111010001 7 18 203D1 1 31 216091 110100110000011011 9 18 34C1B 3 32 756839 10111000110001100111 11 20 B8C67 3 33 859433 11010001110100101001 10 20 D1D29 1 34 1257787 100110011000100111011 11 21 13313B 3 35 1398269 101010101010111111101 14 21 1555FD 1 36? 2976221 1011010110100111011101 14 22 2D69DD 1 37? 3021377 1011100001101001000001 9 22 2E1A41 1 38? 6972593 11010100110010010110001 11 23 6A64B1 1 total 263 471 # 1's=21 # 3's=16 We'd expect the leading and trailing bits to be 1's except for the sole even, accounting for 75 1 bits and 76 places. The remaining "interior" bits are 1's 188 times out of 395, or 47.6%. Up through 3021377 it was 47.9%. With 2976221 it was 48.6% of the time. Without M2976221 it was 47.9%. The incidence of 1's in the second place from the right (excluding p=2) is 16/(16+21)=43.2%; the incidence in the remaining interior bits is 172/358=48.0% Largest run of 1's: 8 (p=1279) Largest run of 0's: 7 (p=132049) Highest percentage of 1's: 100% (p=3,7,31,127) Lowest percentage of 1's: 30% (p=521; just one more bit than the minimum) Ken ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ End of Mersenne Digest V1 #596 ******************************
