- Hi Harsh,

I had some code to do this with Pari. See below. To get Pari, visit

http://pari.math.u-bordeaux.fr/download.html

Be careful copying the output. You probably will be better off running the

code in Pari. Note

that the large factors are pseudoprimes. To "prove" them use the Pari

isprime(x) function.

Eg., the large factor in 2^197-1 is a proven prime as shown below.

(20:48) gp >

isprime(26828803997912886929710867041891989490486893845712448833)

%1 = 1

\\ Pari script mersenne.gp. Factoring mersenne type numbers b^p-d

\\ b=base, n = max prime, d=amount to subtract. Mersennes are base = 2,d=1

or 2^p-1.

mersenne(b,n,d) =

{ c=0;

forprime(x=2,n,

y = b^x-d;

f=factor(y);

v=component(f,1);

ln = length(v);

print1(b"^"x"-1 = ");

for(i=1,ln,

print1(v[i]",");

);

print()

)

}

Output

factors are seperated by commas. If the right side has only one number, then

2^p - 1 is prime.

2^2-1 = 3,

2^3-1 = 7,

2^5-1 = 31,

2^7-1 = 127,

2^11-1 = 23,89,

2^13-1= 8191,

2^17-1 = 131071,

2^19-1 = 524287,

2^23-1 = 47,178481,

2^29-1 = 233,1103,2089,

2^31-1 = 2147483647,

2^37-1 = 223,616318177,

2^41-1 = 13367,164511353,

2^43-1 = 431,9719,2099863,

2^47-1 = 2351,4513,13264529,

2^53-1 = 6361,69431,20394401,

2^59-1 = 179951,3203431780337,

2^61-1 = 2305843009213693951,

2^67-1 = 193707721,761838257287,

2^71-1 = 228479,48544121,212885833,

2^73-1 = 439,2298041,9361973132609,

2^79-1 = 2687,202029703,1113491139767,

2^83-1 = 167,57912614113275649087721,

2^89-1 = 618970019642690137449562111,

2^97-1 = 11447,13842607235828485645766393,

2^101-1 = 7432339208719,341117531003194129,

2^103-1 = 2550183799,3976656429941438590393,

2^107-1 = 162259276829213363391578010288127,

2^109-1 = 745988807,870035986098720987332873,

2^113-1 = 3391,23279,65993,1868569,1066818132868207,

2^127-1 = 170141183460469231731687303715884105727,

2^131-1 = 263,10350794431055162386718619237468234569,

2^137-1 = 32032215596496435569,5439042183600204290159,

2^139-1 = 5625767248687,123876132205208335762278423601,

2^149-1 = 86656268566282183151,8235109336690846723986161,

2^151-1 = 18121,55871,165799,2332951,7289088383388253664437433,

2^157-1 = 852133201,60726444167,1654058017289,2134387368610417,

2^163-1 = 150287,704161,110211473,27669118297,36230454570129675721,

2^167-1 = 2349023,79638304766856507377778616296087448490695649,

2^173-1 = 730753,1505447,70084436712553223,155285743288572277679887,

2^179-1 = 359,1433,1489459109360039866456940197095433721664951999121,

2^181-1 = 43441,1164193,7648337,7923871097285295625344647665764672671,

2^191-1 = 383,7068569257,39940132241,332584516519201,87274497124602996457,

2^193-1 = 13821503,61654440233248340616559,14732265321145317331353282383,

2^197-1 = 7487,26828803997912886929710867041891989490486893845712448833,

2^199-1 = 164504919713,4884164093883941177660049098586324302977543600799,

2^211-1 =

15193,60272956433838849161,3593875704495823757388199894268773153439,

2^223-1 =

18287,196687,1466449,2916841,1469495262398780123809,59624259998711612841

5063,

2^227-1 =

26986333437777017,7992177738205979626491506950867720953545660121688631,

2^229-1 =1504073,20492753,59833457464970183,

467795120187583723534280000348743236593,

2^233-1 =

1399,135607,622577,116868129879077600270344856324766260085066532853492178431,

2^239-1 = 479,1913,5737,176383,134000609,

7110008717824458123105014279253754096863768062879,

2^241-1=

22000409,160619474372352289412737508720216839225805656328990879953332340439,

2^251-1 = 503,54217,178230287214063289511,61676882198695257501367,

12070396178249893039969681,

Have Fun,

Cino

"Behavior is not for the pursuit of survival but because of it."

>From: "eharsh82" <harsh@...>

_________________________________________________________________

>To: primenumbers@yahoogroups.com

>Subject: [PrimeNumbers] Factors of mersenne numbers

>Date: Mon, 12 Jan 2004 02:09:24 -0000

>

>I am looking for all the factors of mersenne numbers under 2^256-1.

>that is 2^n-1, n from 1 to 256

>

>Could you please provide me with a website where I can download these

>numbers.

>

>Thanks,

>Harsh Aggarwal

>

>

High-speed users�be more efficient online with the new MSN Premium Internet

Software. http://join.msn.com/?pgmarket=en-us&page=byoa/prem&ST=1 - -----BEGIN PGP SIGNED MESSAGE-----

Hash: SHA1

On Monday 12 January 2004 03:09, cino hilliard wrote:

> Hi Decio,

>

> The Pari script I posted using the Pari Factor() function took 13.5 min to

> test primes only.

> This is the one for composites (I e-mailed direct to him)

> mrsenne(b, n, d) =

> c=0;for(x=2,n,if(!isprime(x),y=b^x-d;f=factor(y);v=f[,1];ln=

> length(v);print1(b"^"x"-"d"=");for(i=1,ln,print1(v[i]","););print()))

> Also I got this for 2^254-1

> *** Warning: MPQS: the factorization of this number will take several

> hours

> It was not true as is stated below.

>

> For the second request from Harsh to do the composits, it took 24 min.That

> is a total of 37.5 min.

> I realized that the request made was for a small number and figured that an

> answer, albiet slow

> would surface much faster than coding a factorization project. However, for

> n = 1024 there is

> no other way. Assuming your results are correct, your method is 37.5/10.7

> = 3.5 times faster

> than the Pari function. I have been looking at the Lucus Lehmer test. Maybe

> it will help speed the

> calculation of factors. I would like to try your method. Can you post the

> script so i can play?

OK, the script that I had would only factor and throw away the results (I

didn't want them, I just wanted to time how long it would take). I've made it

output numbers much like your format, and here it is (hoping that there

aren't many bugs):

mersenne(b, n, d) =

{

for(k = 1,n,

polfact = factor(x^k-d);

x = b;

factors = eval(polfact);

kill(x);

myfactors = matrix(2,0);

for(j = 1,matsize(factors)[1],

myfactors = vecsort(

concat(

myfactors~,

factorint(factors[j,1]^factors[j,2])~

),1

)~;

);

print1(b"^"k"-"d" = ");

i = 1;

while(i < matsize(myfactors)[1],

if(myfactors[i,1] != myfactors[i+1,1],

print1(myfactors[i,1]);

if(myfactors[i,2] > 1,

print1("^"myfactors[i,2]);

);

print1(",");

i++;

,

count = 0;

start = i;

while(i <= matsize(myfactors)[1] &&

myfactors[i,1] == myfactors[start,1],

count += myfactors[i,2];

i++;

);

print1(myfactors[start,1]"^"count",");

);

);

if(i == matsize(myfactors)[1],

print1(myfactors[i,1]);

if(myfactors[i,2] > 1,

print1("^"myfactors[i,2]);

);

print();

,

print();

);

);

}

> Maybe Pari could use a mersenne function similar to the one above but with

> your speed up.

The problem here is that when you type factorint(2^64-1), say, PARI/GP parses

this as factorint(18446744073709551615), losing the `algebraic structure' if

I may call it that. There'd have to be a function that took a string as input

or something.

Décio

-----BEGIN PGP SIGNATURE-----

Version: GnuPG v1.2.3 (GNU/Linux)

iD8DBQFAAon1FXvAfvngkOIRAgFDAJ4tKrUHscJvMeu8f+glPKGkyHpXjgCeN/bU

bsUYEitTLHLgF2EucpIVldI=

=kWAt

-----END PGP SIGNATURE-----