Mersenne Digest Saturday, June 19 1999 Volume 01 : Number 584
----------------------------------------------------------------------
Date: Fri, 18 Jun 1999 16:04:58 -0500 (CDT)
From: Robert Stalzer <[EMAIL PROTECTED]>
Subject: Mersenne: Duplicate Computer IDs
According to the FAQ, "PrimeNet knows when a test result was computed on a
different computer. It will accept your results for the master database
log, but it will not credit your account for the test work."
(1) Does this cause a credit problem when a team member gives 2 PCs the
same Computer ID? Each PC has its own connection to the internet.
(2) Shouldn't I discourage team members from duplicating Computer IDs?
Robert Stalzer
[EMAIL PROTECTED]
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Fri, 18 Jun 1999 18:56:36 EDT
From: [EMAIL PROTECTED]
Subject: Mersenne: TI Factoring
<<Uh, that's exactly what Prime95 does. To test whether a potential factor f
divides 2^p-1, we use a standard binary powering algorithm to compute 2^p
modulo f; it requires roughly log2(p) operations on numbers no bigger than
f, and we never have to store the full representation of 2^p-1. I'm sure
that this could be done on a TI. I don't know about ECM though.>>
So, is this:
(2^p mod f) - 1
Congruent to this:
(2^p -1) mod f
I believe so. If that's true, whoo hoo! I have code to do this already. And
it's relatively speedy. (It makes up the core of my RSA key generation and
encryption machine, which of course is heavy on exponentiation modulo some
other number).
This is doubly great, because TI-92s can go up to 614 decimal digit
precision, so I can store the entire factor.
<<Its not all that complex here is a calc
program to find a^b mod c (which I think explains things better than 2 pages
of mathematical ranting)>>
I am completely and utterly C illiterate. Mathematical ranting makes more
sense. BASIC is also good. But it doesn't matter, because I have a TI-92
function already that does a^b mod c.
<<Note that if 2^p==1 mod c then c is a factor.>>
If this is correct, I will craft a TI-92 program immediately to factor
Mersenne numbers. *drool drool* An untapped source of computing power exists.
Even if we can't factor up to 2^62 like larger computers can, TI users will
be able to scan low factors. Not sure how fast, though. Yippee!
<<However, I cannot think of any way to do an LL test without storing the
number in memory. Is there way?>>
Neither can I. And TIs don't have 4MB RAM. *sob*.
S.T.L.
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Fri, 18 Jun 1999 19:10:25 EDT
From: [EMAIL PROTECTED]
Subject: Mersenne: TI-92 Factoring, again
Using the wonderful modpwr() from Paul Pollack's NTH library for the TI-92, I
have quickly verified the following results I found on Entropia.com:
7017133 61 F 1901619961404080441 14-May-99 11:35 jay2001
PII_40
7029787 62 F 3764452186385609519 31-May-99 02:47 love_fest
synergy
9780157 55 F 49538835694371671 17-Jun-99 07:45 Vincent
vinc
For each of them, the TI-92 quickly returned that 2^exponent mod factor = 1,
and very quickly too (yay!). A calculator factoring program is a real
possibility. I'll get to work coding a "front-end" right away. However, I
think I recently read that some people had their computers race ahead and
factor large exponents (like 25million) up to some small number, like 2^40.
Have those results been posted anywhere? If this TI-92 program is distributed
far and wide, repeating already-done work would be a waste. Thanks.
S.T.L.
Happily coding away in TI-92+ BASIC.
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Fri, 18 Jun 1999 19:39:45 EDT
From: [EMAIL PROTECTED]
Subject: Mersenne: :-( TI factoring is slow
I hacked up a quick TI-92 factoring program. It is slower than I wanted. :-(
It's "testing" 2^25,000,009 - 1 right now. It can test one factor every 1.3
seconds. AUGH! At that rate it would take 95 *billion* years to trial divide
by all odd numbers under 2^62. Noooo.
However, a semi-reasonable task would be to test numbers for factors up to
2^16. Pitiful, I know, but a TI could test a single number in 12 hours
(running constantly - hah, no multitasking here). So, I have two questions:
A) Where would the numbers start that haven't been factored at ALL, to ANY
extent?
B) To Mr. Woltman or Mr. Kurowski - how "useful" would factoring (most likely
very large) exponents to only 2^16 be? Or have "real" computers already
quickly scanned very high for such small factors?
S.T.L.
Who wishes TI-92s came with 500MHz processors.
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Fri, 18 Jun 1999 20:25:46 -0700
From: Will Edgington <[EMAIL PROTECTED]>
Subject: Re: Mersenne: Mersenne Primes - what'd you expect?
Foghorn Leghorn writes:
>Could you factor a Mersenne number without storing it in memory?
>(Answer: I don't *think* so....) Ptoo bad. If we could factor
>Mersenne numbers on an unmodified TI-92+, then there'd be a lot of
>people who'd run that program.
Uh, that's exactly what Prime95 does. To test whether a potential
factor f divides 2^p-1, we use a standard binary powering algorithm
to compute 2^p modulo f; it requires roughly log2(p) operations on
numbers no bigger than f, and we never have to store the full
representation of 2^p-1. I'm sure that this could be done on a
TI. I don't know about ECM though.
I'm not sure about ECM either, but P-1 can be done using this same
algorithm to do most of it's work. And I _think_ ECM can use this as
well, just not for the entire job.
See merspm1.c of the mers package for a very simple (and slow)
implementation of P-1. There is a faster one out there, based on
George Woltman's FFT code from prime95, called Factor98.
Will
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Fri, 18 Jun 1999 20:05:47 -0700
From: Will Edgington <[EMAIL PROTECTED]>
Subject: Re: Mersenne: Mersenne Primes - what'd you expect?
lrwiman writes:
However, I cannot think of any way to do an LL test without storing
the number in memory. Is there way?
Yes. All of the GIMPS programs do the LL test without the Mersenne
number itself.
The LL test programs do, however, need to store numbers as large as
the Mersenne number itself, which factorers do not need to do.
I would guess that the "trick" you are missing is that the Mersenne
number itself is not needed to do the mod by it:
(a*2^n + b) (mod 2^n - 1) = (a*(2^n - 1) + a + b) (mod 2^n - 1)
= (a*0 a + b) (mod 2^n - 1)
That is, if you have a number that is larger than 2^n, split it every
n bits, shift all the "pieces" down into the 0 thru (n - 1) bits, add,
and repeat while the sum is larger than 2^n - 1 (i.e., occupies more
than the lowest n bits).
Will
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Fri, 18 Jun 1999 20:42:32 -0700
From: Will Edgington <[EMAIL PROTECTED]>
Subject: Mersenne: TI Factoring
[EMAIL PROTECTED] writes:
So, is this:
(2^p mod f) - 1
Congruent to this:
(2^p -1) mod f
Yes, though be careful about the case of 2^p mod f being 0. The first
will give you -1 and the second is f-1. They are congruent, mod f, of
course, but not identical.
This is doubly great, because TI-92s can go up to 614 decimal digit
precision, so I can store the entire factor.
So you should be able to test factors up to about 307 digits. Not
bad.:)
I am completely and utterly C illiterate. Mathematical ranting makes more
sense. BASIC is also good. But it doesn't matter, because I have a TI-92
function already that does a^b mod c.
It's probably the same algorithm; it's quite well known. (Though I
didn't know about it until George pointed it out to me when I joined
GIMPS back in Jan. of 1996; sped up my pre-GIMPS factorer by a factor
of three!).
If this is correct, I will craft a TI-92 program immediately to
factor Mersenne numbers. *drool drool* An untapped source of
computing power exists. Even if we can't factor up to 2^62 like
larger computers can, TI users will be able to scan low
factors. Not sure how fast, though. Yippee!
Actually, you can go farther; 2^62 is only about 20 digits. But
perhaps too slowly, as you note in a later message. And the mers
package programs can factor arbitrarily far, but also slower than
George's programs.
<<However, I cannot think of any way to do an LL test without
storing the number in memory. Is there way?>>
Neither can I. And TIs don't have 4MB RAM. *sob*.
As I've (just) pointed out, the LL test doesn't need the Mersenne
number itself either. However, it does need numbers just as large,
which is what prevents doing LL on TIs.
Will
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Sat, 19 Jun 1999 05:41:50 +0200 (MET DST)
From: [EMAIL PROTECTED]
Subject: Re: Mersenne: Mersenne Primes - what'd you expect?
Will Edgington <[EMAIL PROTECTED]> writes:
> Foghorn Leghorn writes:
> >Could you factor a Mersenne number without storing it in memory?
> >(Answer: I don't *think* so....) Ptoo bad. If we could factor
> >Mersenne numbers on an unmodified TI-92+, then there'd be a lot of
> >people who'd run that program.
> Uh, that's exactly what Prime95 does. To test whether a potential
> factor f divides 2^p-1, we use a standard binary powering algorithm
> to compute 2^p modulo f; it requires roughly log2(p) operations on
> numbers no bigger than f, and we never have to store the full
> representation of 2^p-1. I'm sure that this could be done on a
> TI. I don't know about ECM though.
> I'm not sure about ECM either, but P-1 can be done using this same
> algorithm to do most of it's work. And I _think_ ECM can use this as
> well, just not for the entire job.
Like the LL algorithm, P-1 and ECM need to store residues as large
as 2^p-1. LL needs only one such residue, P-1 needs a few, ECM needs many.
P-1 and ECM need a GCD (Greatest Common Divisor) routine, which
will need many temporaries if it uses fast algorithms.
Peter Montgomery
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Sat, 19 Jun 1999 00:11:20 EDT
From: [EMAIL PROTECTED]
Subject: Mersenne: D'oh.
In my haste in programming that TI-92 Mersenne factoring program, I
*completely* forgot about the special structure of Mersenne factors, of which
several people hastened to remind me. :-O I should have known better. I
actually did. My memory must be going. (Not to mention my brain drain before
this - as soon as I saw the modpwr() function for my calculator, I should
have thought Mersenne factoring).
So, of course this changes everything. Perhaps it WON'T take 95 billion years
to factor a single number. I'll retool my program and test it again.
S.T.L.
Yup, feeling like a moron.
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Fri, 18 Jun 1999 21:08:19 -0400
From: Chris Nash <[EMAIL PROTECTED]>
Subject: Re: Mersenne: :-( TI factoring is slow
> However, a semi-reasonable task would be to test numbers for factors up to
> 2^16.
Done.
> Pitiful, I know, but a TI could test a single number in 12 hours.
An optimized algorithm will do it in about zero seconds.
> B) To Mr. Woltman or Mr. Kurowski - how "useful" would factoring (most
likely
> very large) exponents to only 2^16 be? Or have "real" computers already
> quickly scanned very high for such small factors?
The smallest factor of 2^p-1, p a prime, is at least as big as 2p+1. All
factors of a Mersenne number of prime exponent are of the form 2kp+1 -
similarly for all 'new' factors of a composite exponent (ie that haven't
appeared in any Mersenne number with an exponent that is a factor of the
original one).
Chris Nash
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Fri, 18 Jun 1999 22:24:55 -0700
From: Will Edgington <[EMAIL PROTECTED]>
Subject: Mersenne: TI-92 Factoring, again
[EMAIL PROTECTED] writes:
Using the wonderful modpwr() from Paul Pollack's NTH library for
the TI-92, I have quickly verified the following results I found on
Entropia.com: [...]
Good.:)
For each of them, the TI-92 quickly returned that 2^exponent mod
factor = 1, and very quickly too (yay!). A calculator factoring
program is a real possibility. I'll get to work coding a
"front-end" right away. However, I think I recently read that some
people had their computers race ahead and factor large exponents
(like 25million) up to some small number, like 2^40. Have those
results been posted anywhere? If this TI-92 program is distributed
far and wide, repeating already-done work would be a waste. Thanks.
I have that data, including some that Brian Beesley just sent me, but
I do not have enough space on the web to store it. I do, however,
create an pre-Primenet DATABASE file that contains enough data to
support this kind of effort: finding new first factors of prime
exponent Mersennes. It is the DATABASE file in:
http://www.garlic.com/~wedgingt/mersdata.tgz
mersdata.zip
The extract program of the mers package can print DATABASE files in a
simple human readable format; grab mers.tgz or mers.tar.gz as well to
get extract.c.
I have just updated my web pages, including this DATABASE file, so it
now includes the new data from Brian on prime exponent Mersenne
numbers with just over 10 million digits.
[EMAIL PROTECTED] writes:
I hacked up a quick TI-92 factoring program. It is slower than I
wanted. :-( It's "testing" 2^25,000,009 - 1 right now. It can test
one factor every 1.3 seconds. AUGH! At that rate it would take 95
*billion* years to trial divide by all odd numbers under
2^62. Noooo.
Hm. Are you forgetting that factors of prime exponent Mersennes must
be 1 or 7 mod 8 and 2*k*p + 1 where p is the prime exponent? And the
Prime95 and mersfac* programs also do some sieving of the possible
factors, so they don't try ones that themselves have small factors.
However, a semi-reasonable task would be to test numbers for
factors up to 2^16. Pitiful, I know, but a TI could test a single
number in 12 hours (running constantly - hah, no multitasking
here).
If it really is that bad, then it's probably not worth doing. I once
tested all the prime exponent Mersennes with exponents from about 10
million thru about 21 million for factors smaller than 2^33 or so,
using mersfacgmp on a Pentium 90MHz, in a couple of days.
A) Where would the numbers start that haven't been factored at ALL,
to ANY extent?
There are some prime exponents in this category between 21.5 and 22
million, but not many. And, now that I have more disk space, I'm
likely to "cure" this sometime soon, by factoring to 2^33 or more all
the way past the next likely GIMPS limit (exponents less than 41
million).
B) To Mr. Woltman or Mr. Kurowski - how "useful" would factoring
(most likely very large) exponents to only 2^16 be? Or have "real"
computers already quickly scanned very high for such small factors?
Actually, I believe that George and Scott are not concerned with the
larger exponents (above the current GIMPS limit near 20.5 million).
Certainly, George has known for a long time that I have some data for
larger exponents and hasn't asked for it yet.
Will
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Fri, 18 Jun 1999 23:31:55 -0700
From: Will Edgington <[EMAIL PROTECTED]>
Subject: Re: Mersenne: :-( TI factoring is slow
Chris Nash writes:
The smallest factor of 2^p-1, p a prime, is at least as big as
2p+1. All factors of a Mersenne number of prime exponent are of the
form 2kp+1 - similarly for all 'new' factors of a composite
exponent (ie that haven't appeared in any Mersenne number with an
exponent that is a factor of the original one).
Everything here is correct except that many "primitive" factors of
composite exponent Mersennes are _not_ congruent to 1 mod twice the
exponent. There are numerous counter-examples, starting with 5, which
is a factor of M(4) = 15 but not a factor of any smaller Mersenne.
All "primitive" factors are, however, congruent to 1 mod the exponent,
even for composite exponents and factors.
Will
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Sat, 19 Jun 1999 08:47:00 +0200 (MET DST)
From: [EMAIL PROTECTED]
Subject: Re: Mersenne: primitive factors (was :-( TI factoring is slow)
Will Edgington commented:
> Chris Nash writes:
>
> The smallest factor of 2^p-1, p a prime, is at least as big as
> 2p+1. All factors of a Mersenne number of prime exponent are of the
> form 2kp+1 - similarly for all 'new' factors of a composite
> exponent (ie that haven't appeared in any Mersenne number with an
> exponent that is a factor of the original one).
>
> Everything here is correct except that many "primitive" factors of
> composite exponent Mersennes are _not_ congruent to 1 mod twice the
> exponent. There are numerous counter-examples, starting with 5, which
> is a factor of M(4) = 15 but not a factor of any smaller Mersenne.
> All "primitive" factors are, however, congruent to 1 mod the exponent,
> even for composite exponents and factors.
Both of Chris Nash's remarks are intended for odd p.
The factor 3 of 2^2 - 1 is not congruent to 1 modulo 2*2.
"Primitive factors" should be restricted to primitive prime factors.
The factor 1057 = 7*151 of 2^15-1 = 7*31*151 does not divide any
M(n) with 1 <= n < 15, yet 1057 is not 1 modulo 15
(however the new prime 151 has this form).
Peter Montgomery
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Sat, 19 Jun 1999 08:12:37 +0100
From: "Brian J. Beesley" <[EMAIL PROTECTED]>
Subject: Re: Mersenne: TI-92 Factoring, again
> If it really is that bad, then it's probably not worth doing. I once
> tested all the prime exponent Mersennes with exponents from about 10
> million thru about 21 million for factors smaller than 2^33 or so,
> using mersfacgmp on a Pentium 90MHz, in a couple of days.
The factoring program I used to trial-factor the 10 million plus
digit Mersenne numbers with exponents up to 36 million up to 2^40
takes only 20 _seconds_ to trial factor all 159,975 numbers to a
depth of 2^32 on a PII-350. That's including the disk I/O involved in
reading the exponents from a file & writing the results. Possible
factors were checked for +/-1 (mod 8) and screened for divisibility
by the smallest 10 primes before passing to the factoring routine,
which was called 1,267,515 times.
The slower your factoring routine is, the more sieving out of trial
factors helps the execution speed. Though there is always a cutoff
point - executing even just a Fermat test to base 2 (to determine
whether the trial factor is probably prime, with low confidence)
takes longer than the actual trial factoring (the code involved is
pretty well the same, but 2kp+1 > p).
>
> There are some prime exponents in this category between 21.5 and 22
> million, but not many. And, now that I have more disk space, I'm
> likely to "cure" this sometime soon, by factoring to 2^33 or more all
> the way past the next likely GIMPS limit (exponents less than 41
> million).
v19 has FFT sizes up to 2^22 (4 million), it should be capable of
handling exponents up to approx. 80 million. Which is more than
makes sense with current hardware.
> B) To Mr. Woltman or Mr. Kurowski - how "useful" would factoring
> (most likely very large) exponents to only 2^16 be? Or have "real"
> computers already quickly scanned very high for such small factors?
Sorry, but useless. Since the smallest possible factor of 2^p-1 (when
p is prime) is 2p+1, only exponents less than 2^15 can have factors
less than factors less than 2^16. We probably know almost all of the
factors of 2^p-1 for prime p < 16384 that it would be possible to
find with a TI-92, any remaining will likely have at least 15 digits.
Regards
Brian Beesley
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Sat, 19 Jun 1999 09:39:27 -0400
From: Jud McCranie <[EMAIL PROTECTED]>
Subject: Mersenne: Mersenne exponent growth
There is a conjecture that the nth Mersenne exponent resulting in a prime
is approximately (3/2)^n. Consider Mersenne primes through M37. (I don't
know exactly what M38 is yet, and there may be other small ones. Also, the
double checks of the range through M37 haven't been completed.)
You can see the basis of this conjecture if you use semi-log graph paper
and graph the index of the Mersenne exponents along the X axis and the
exponents on the Y axis. If you don't have semi-log graph paper, graph the
log of the exponent. (Or you can use software!) The data is pretty close
to a straight line.
If you do a linear regression of the log of the exponent vs. the index, you
get a correlation coefficient of 0.996 - which indicates a very strong
linear relationship. The linear regression parameters yield the relation
M(n) = 1.4796^n + c, where c is a small constant. 1.4796 is pretty close
to 3/2.
This is one reason why we need to have a complete list of Mersenne primes
up through some value.
+----------------------------------------------+
| Jud "program first and think later" McCranie |
+----------------------------------------------+
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Sat, 19 Jun 1999 08:16:57 -0600
From: "Aaron Blosser" <[EMAIL PROTECTED]>
Subject: RE: Mersenne: :-( TI factoring is slow
> Chris Nash writes:
>
> The smallest factor of 2^p-1, p a prime, is at least as big as
> 2p+1. All factors of a Mersenne number of prime exponent are of the
> form 2kp+1 - similarly for all 'new' factors of a composite
> exponent (ie that haven't appeared in any Mersenne number with an
> exponent that is a factor of the original one).
>
> Everything here is correct except that many "primitive" factors of
> composite exponent Mersennes are _not_ congruent to 1 mod twice the
> exponent. There are numerous counter-examples, starting with 5, which
> is a factor of M(4) = 15 but not a factor of any smaller Mersenne.
But since 4 is not prime, I doubt that would (pardon the pun) be a factor
when looking for divisors of 2^p-1 (where p is prime).
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Sat, 19 Jun 1999 08:22:30 -0600
From: "Aaron Blosser" <[EMAIL PROTECTED]>
Subject: RE: Mersenne: Mersenne exponent growth
> There is a conjecture that the nth Mersenne exponent resulting in a prime
> is approximately (3/2)^n. Consider Mersenne primes through M37. (I don't
> know exactly what M38 is yet, and there may be other small ones.
> Also, the
> double checks of the range through M37 haven't been completed.)
>
> You can see the basis of this conjecture if you use semi-log graph paper
> and graph the index of the Mersenne exponents along the X axis and the
> exponents on the Y axis. If you don't have semi-log graph paper,
> graph the
> log of the exponent. (Or you can use software!) The data is pretty close
> to a straight line.
>
> If you do a linear regression of the log of the exponent vs. the
> index, you
> get a correlation coefficient of 0.996 - which indicates a very strong
> linear relationship. The linear regression parameters yield the relation
> M(n) = 1.4796^n + c, where c is a small constant. 1.4796 is pretty close
> to 3/2.
So, based on this conjecture, what would you guess M38 to be (roughly)?
Should we start a pool to see who can guess the closest to the real
exponent? And those of you who know for sure cannot participate! :-) It'd
be an interesting "experiment" to see just how much this new one fits any
type of pattern.
Aaron
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Sat, 19 Jun 1999 15:53:27 +0100 (BST)
From: Chris Jefferson <[EMAIL PROTECTED]>
Subject: Mersenne: More factoring..
I've been looking through various bits of factoring code and I really
can't find any speed increases, unsuprisingly :). Managed to get some very
nice equations out of euler's algorithm, but none that compute any
faster...
However, a couple of things did crop up. Firstly, if two numbers have a
similar binary expansion, e.g. only the last few bit are different,
although it would double memory requirements, ould it be worth trying to
factor both at the same time?
Also, to ease finding factors, using a number which is a multiple of 8 is
a good idea. However, how much work has been done on checking other mods
other than 120? Like 80, or even 720 to see what happens? just
wondering...
- ------------------------------------
Chris Jefferson, Girton College, Cambridge, [EMAIL PROTECTED]
- ------------------------------------
Someone may have beaten me to Fermat's Last Theorem, but I've done
Riemann's general equation. However it won't fit in my signature file...
- ------------------------------------
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Sat, 19 Jun 1999 12:03:55 -0400
From: Jud McCranie <[EMAIL PROTECTED]>
Subject: RE: Mersenne: Mersenne exponent growth
At 08:22 AM 6/19/99 -0600, Aaron Blosser wrote:
>So, based on this conjecture, what would you guess M38 to be (roughly)?
On the average, the ratio of successive exponents that result in prims is about
3/2, but that doesn't help with individual ones. For the first 37, the ratio
varies from 1.015 to 4.102.
+----------------------------------------------+
| Jud "program first and think later" McCranie |
+----------------------------------------------+
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Sat, 19 Jun 1999 12:17:12 -0400
From: Jud McCranie <[EMAIL PROTECTED]>
Subject: Mersenne: Mersenne 3/2 conjecture
If you take the following comma delimited file into a spreadsheet, and
graph it (say with a line chart) it shows the relationship of Mersenne
exponents to their index, for the first 37 Mersenne primes. The first
column is the log of (3/2)^n, the second column is the log of the exponent
of the nth Mersenne prime.
0.405,0.693
0.811,1.099
1.216,1.609
1.622,1.946
2.027,2.565
2.433,2.833
2.838,2.944
3.244,3.434
3.649,4.111
4.055,4.489
4.460,4.673
4.866,4.844
5.271,6.256
5.677,6.409
6.082,7.154
6.487,7.698
6.893,7.732
7.298,8.076
7.704,8.355
8.109,8.395
8.515,9.179
8.920,9.204
9.326,9.325
9.731,9.900
10.137,9.985
10.542,10.052
10.948,10.703
11.353,11.365
11.758,11.613
12.164,11.791
12.569,12.283
12.975,13.537
13.380,13.664
13.786,14.045
14.191,14.151
14.597,14.906
15.002,14.921
+----------------------------------------------+
| Jud "program first and think later" McCranie |
+----------------------------------------------+
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Sat, 19 Jun 1999 12:55:46 -0400
From: Jeff Woods <[EMAIL PROTECTED]>
Subject: RE: Mersenne: Mersenne exponent growth
At 08:22 AM 6/19/99 -0600, you wrote:
> >There is a conjecture that the nth Mersenne exponent resulting in a prime
> >is approximately (3/2)^n. linear relationship. The linear
> regression >parameters yield the relation M(n) = 1.4796^n + c, where c
> is a small >constant. 1.4796 is pretty close to 3/2.
>
>So, based on this conjecture, what would you guess M38 to be (roughly)?
>Should we start a pool to see who can guess the closest to the real
>exponent? And those of you who know for sure cannot participate! :-)
Also one must take into account the "pseudo-conjecture" that Curt Noll (I
believe -- if I've misattributed, please forgive) has made about "Mersenne
Islands". If you look at the distribution, they tend to clump, like
galaxy clusters, with large voids between the islands.
Starting at about M13, you see that there are indeed islands:
13 521 \______ island centered at 564
14 607 /
15 1279 standalone
16 2203 \______ island centered at 2242
17 2281 /
18 3217 standalone
19 4253 \______ island centered at 4338
20 4423 /
21 9689 \______ island centered at 9815 (11213 MAY be part of this)
22 9941 /
23 11213 standalone
24 19937 \
25 21701 >----- island centered at 21615
26 23209 /
27 44497 \______ POSSIBLE island at 65370
28 86243 /
29 110503 \______ island centered at 121276
30 132049 /
31 216091 standalone
32 756839 \______ island centered at 808136
33 859433 /
34 1257787 \______ island centered at 1328028
35 1398269 /
?? 2976221 \______ island centered at 2998799
?? 3021377 /
Now, fit the center of the ISLANDS that have more than one member into a
linear progression:
564
2242
4338
9815
21615
65370
121276
216091
808136
1328028
2998799
Graph that you, and you get a VERY close linear fit. I haven't done it
mathematically, but at first glance a guestimate (first suggested by Noll,
IIRC) is that Mersenne Primes are distributed into islands ROUGHLY a linear
double from the last island, with the occasional empty "gap" (such as the
region around p=400000, where if island theory held, we should have
expected a couple primes).
Given this fit, I will estimate that Curt is correct, and that the
potential M38 is in the region of the next island (where heavy testing
recently occured) which should be around 6,300,000. If the pattern holds,
M39 may be relatively close to M38, too, so we ought not be too long in a
fifth success, assuming M38 is valid, too, and not someone's cruel idea of
a hoax...
IMO, the longer it takes us to hear the official word on M38, the more
likely it is NOT a valid prime, but some dimwit trying to submit a zero
residue for prize money. If the "confirming test" comes back NON-prime,
then several additional tests will have to be done to find out for sure,
and that will take longer.
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Sat, 19 Jun 1999 18:06:20 +0100 (BST)
From: Chris Jefferson <[EMAIL PROTECTED]>
Subject: Re: Mersenne: More factoring..
> Also, to ease finding factors, using a number which is a multiple of 8 is
> a good idea. However, how much work has been done on checking other mods
> other than 120? Like 80, or even 720 to see what happens? just
> wondering...
As often happens (to me at least), as soon as I tell someone something, I
suddenly realise it is wrong!
I know that the number you do modulus to has to be a multiple of 8, to use
that number must be +/- 1 mod 8, After that you want to put as many prime
factor in number as possible, say 8*3,8*5, or as we use, 8*3*5
So, any other numbers you used would want to be in this form. As far as i
can see, the only number worth investigating looks like 840, which instead
of having 7*16 passes, will have about 8 less. Not realy worth it i
think...
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Sat, 19 Jun 1999 13:05:25 -0700
From: Will Edgington <[EMAIL PROTECTED]>
Subject: Re: Mersenne: primitive factors (was :-( TI factoring is slow)
[EMAIL PROTECTED] writes:
Both of Chris Nash's remarks are intended for odd p.
Hm; yes, I didn't notice that all the exceptions were for even
exponents.
The factor 3 of 2^2 - 1 is not congruent to 1 modulo 2*2.
"Primitive factors" should be restricted to primitive prime factors.
Well, I was thinking of prime & proper factors, but I didn't say that
explicitly and see your points.
The factor 1057 = 7*151 of 2^15-1 = 7*31*151 does not divide any
M(n) with 1 <= n < 15, yet 1057 is not 1 modulo 15
(however the new prime 151 has this form).
Yup. The ecm3 program of the mers package tries very hard to print
only prime factors that are not also factors of smaller Mersennes, and
this was the situation that I was thinking of.
In fact, ecm3 will print a warning if it's given composite factors. Or
when it's given prime factors of a smaller Mersenne number. My
automatic update scripts use this output to factor the composite
factors and figure out which smaller exponent the others really
"belong" to.
Will
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Sat, 19 Jun 1999 14:04:59 -0600
From: "Aaron Blosser" <[EMAIL PROTECTED]>
Subject: Mersenne: Mersenne exponent growth
> >So, based on this conjecture, what would you guess M38 to be (roughly)?
>
> On the average, the ratio of successive exponents that result in
> prims is about
> 3/2, but that doesn't help with individual ones. For the first
> 37, the ratio
> varies from 1.015 to 4.102.
I see...I didn't really think there was any real predictability, since there
are several that are real close together and some that are far apart,
relatively.
It's like saying that the average American family has 2.5 kids, when, in
fact, I would *hope* that no family actually had 2.5 kids. :-)
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Sat, 19 Jun 1999 14:06:28 -0600
From: "Aaron Blosser" <[EMAIL PROTECTED]>
Subject: RE: Mersenne: Mersenne 3/2 conjecture
> If you take the following comma delimited file into a spreadsheet, and
> graph it (say with a line chart) it shows the relationship of Mersenne
> exponents to their index, for the first 37 Mersenne primes. The first
> column is the log of (3/2)^n, the second column is the log of the exponent
> of the nth Mersenne prime.
One more reason why I'd like to "fill in the gaps" because, otherwise, such
statistics are invalid until we've double-checked all exponents below any
given Mersenne prime.
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Sat, 19 Jun 1999 14:24:08 -0600
From: "Aaron Blosser" <[EMAIL PROTECTED]>
Subject: Mersenne: Islands? No islands?
> Also one must take into account the "pseudo-conjecture" that Curt Noll (I
> believe -- if I've misattributed, please forgive) has made about
> "Mersenne
> Islands". If you look at the distribution, they tend to clump, like
> galaxy clusters, with large voids between the islands.
On a whim, I figured I'd do a rough calculation of the %deviation from each
exponent to it's "center", based on the numbers you gave and see if they fit
any sort of pattern. Then, if you find one, you might be able to narrow
down where a potential "Gilligan" (Island Buddy) would be (I figure the
first one found would be "Skipper"). :-) I hereby release any claim on my
made up terms for island partners :-)
> Starting at about M13, you see that there are indeed islands:
>
> 13 521 \______ island centered at 564
> 14 607 /
~ 8.25% from center
> 16 2203 \______ island centered at 2242
> 17 2281 /
~ 1.7%
> 19 4253 \______ island centered at 4338
> 20 4423 /
~ 2.0%
> 21 9689 \______ island centered at 9815 (11213 MAY be part of this)
> 22 9941 /
~ 1.3%
> 24 19937 \
> 25 21701 >----- island centered at 21615
> 26 23209 /
~ 7.8%/7.4% (for smallest and largest exponents...a bit iffy)
> 27 44497 \______ POSSIBLE island at 65370
> 28 86243 /
~ 31.9% (this one is iffy also)
> 29 110503 \______ island centered at 121276
> 30 132049 /
~ 8.9%
> 32 756839 \______ island centered at 808136
> 33 859433 /
~ 6.3%
> 34 1257787 \______ island centered at 1328028
> 35 1398269 /
~ 5.3%
> ?? 2976221 \______ island centered at 2998799
> ?? 3021377 /
~ 0.8%
I'd say that from looking at the deviations between pairs in the "islands",
I'm not so sure we can call them pairs. The "groupings" we see between
them, especially given the "standalones" is more likely to be purely
coincidental and perhaps a bit of a projection on our part. When analyzed
strictly, I don't see any pattern there. Some of the definitions of pairs
are a bit fast and loose also. Perhaps we should only term two Mersenne
primes a pair if the exponents are less than 2% apart from their
average...just as a general guideline? Meaning that a good number of those
"pairs" above are nothing near each other, especially M27 and M28.
> Given this fit, I will estimate that Curt is correct, and that the
> potential M38 is in the region of the next island (where heavy testing
> recently occured) which should be around 6,300,000. If the
> pattern holds,
Perhaps the "center" points of the pair examples you gave appear to have a
loose linear correlation, but I think we may be playing a bit fast and loose
with the definition of a pair here...
> M39 may be relatively close to M38, too, so we ought not be too long in a
> fifth success, assuming M38 is valid, too, and not someone's
> cruel idea of
> a hoax...
It'd be silly for anyone to try and cheat the system, knowing there would be
double and triple checks on any claim. But then again, some people are
rather silly.
Aaron
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
End of Mersenne Digest V1 #584
******************************
