Ten Billion Digits Mersenne Numbers

aketilander · 2012-05-10, 20:38

Well, I got a bit carried away and trial factored the smallest 100 Ten Billion Digits Mersenne Numbers with prime exponents (M33,219,280,951 - M33,219,283,529) up till ^70 bits and found 62 factors Here is the result:

Code:

M33219280951 has 0 factors in [2^1, 2^70-1].
M33219281003 has a factor: 61455669855551 - Program: L5.0x
M33219281003 has 1 factors in [2^1, 2^70-1].
M33219281023 has 0 factors in [2^1, 2^70-1].
M33219281027 has 0 factors in [2^1, 2^70-1].
M33219281063 has 0 factors in [2^1, 2^70-1].
M33219281111 has a factor: 2391788239993 - Program: L5.0x
M33219281111 has a factor: 294465063646236102041 - Program: L5.0x
M33219281111 has a factor: 6976049033311 - Program: L5.0x
M33219281111 has 3 factors in [2^1, 2^70-1].
M33219281159 has a factor: 66438562319 - Program: L5.0x
M33219281159 has 1 factors in [2^1, 2^70-1].
M33219281201 has 0 factors in [2^1, 2^70-1].
M33219281213 has 0 factors in [2^1, 2^70-1].
M33219281243 has 0 factors in [2^1, 2^70-1].
M33219281267 has 0 factors in [2^1, 2^70-1].
M33219281269 has a factor: 797262750457 - Program: L5.0x
M33219281269 has 1 factors in [2^1, 2^70-1].
M33219281279 has a factor: 66438562559 - Program: L5.0x
M33219281279 has 1 factors in [2^1, 2^70-1].
M33219281297 has 0 factors in [2^1, 2^70-1].
M33219281299 has 0 factors in [2^1, 2^70-1].
M33219281327 has 0 factors in [2^1, 2^70-1].
M33219281371 has a factor: 16894663979942936777 - Program: L5.0x
M33219281371 has 1 factors in [2^1, 2^70-1].
M33219281383 has 0 factors in [2^1, 2^70-1].
M33219281393 has a factor: 234042327863488769 - Program: L5.0x
M33219281393 has a factor: 150788962099105601 - Program: L5.0x
M33219281393 has 2 factors in [2^1, 2^70-1].
M33219281399 has a factor: 1594525507153 - Program: L5.0x
M33219281399 has a factor: 34880245468951 - Program: L5.0x
M33219281399 has 2 factors in [2^1, 2^70-1].
M33219281411 has 0 factors in [2^1, 2^70-1].
M33219281437 has a factor: 492321512315809895599 - Program: L5.0x
M33219281437 has 1 factors in [2^1, 2^70-1].
M33219281441 has 0 factors in [2^1, 2^70-1].
M33219281449 has a factor: 730824191879 - Program: L5.0x
M33219281449 has 1 factors in [2^1, 2^70-1].
M33219281453 has a factor: 5919675954924601 - Program: L5.0x
M33219281453 has 1 factors in [2^1, 2^70-1].
M33219281467 has 0 factors in [2^1, 2^70-1].
M33219281479 has 0 factors in [2^1, 2^70-1].
M33219281489 has a factor: 116996795601600546271 - Program: L5.0x
M33219281489 has 1 factors in [2^1, 2^70-1].
M33219281497 has a factor: 80462680625025497 - Program: L5.0x
M33219281497 has 1 factors in [2^1, 2^70-1].
M33219281507 has 0 factors in [2^1, 2^70-1].
M33219281521 has a factor: 16476763634417 - Program: L5.0x
M33219281521 has a factor: 689012466796645582273 - Program: L5.0x
M33219281521 has 2 factors in [2^1, 2^70-1].
M33219281531 has 0 factors in [2^1, 2^70-1].
M33219281549 has a factor: 486304386450814108031 - Program: L5.0x
M33219281549 has 1 factors in [2^1, 2^70-1].
M33219281569 has 0 factors in [2^1, 2^70-1].
M33219281587 has a factor: 20728831710289 - Program: L5.0x
M33219281587 has 1 factors in [2^1, 2^70-1].
M33219281629 has 0 factors in [2^1, 2^70-1].
M33219281653 has a factor: 8629771426379647 - Program: L5.0x
M33219281653 has 1 factors in [2^1, 2^70-1].
M33219281677 has 0 factors in [2^1, 2^70-1].
M33219281687 has 0 factors in [2^1, 2^70-1].
M33219281713 has 0 factors in [2^1, 2^70-1].
M33219281737 has a factor: 531508507793 - Program: L5.0x
M33219281737 has 1 factors in [2^1, 2^70-1].
M33219281741 has a factor: 7972627617841 - Program: L5.0x
M33219281741 has 1 factors in [2^1, 2^70-1].
M33219281863 has a factor: 3986313823561 - Program: L5.0x
M33219281863 has 1 factors in [2^1, 2^70-1].
M33219281917 has a factor: 54940373784068791 - Program: L5.0x
M33219281917 has a factor: 6909610638737 - Program: L5.0x
M33219281917 has 2 factors in [2^1, 2^70-1].
M33219281933 has a factor: 797262766393 - Program: L5.0x
M33219281933 has a factor: 7175364897529 - Program: L5.0x
M33219281933 has 2 factors in [2^1, 2^70-1].
M33219281957 has 0 factors in [2^1, 2^70-1].
M33219282001 has 0 factors in [2^1, 2^70-1].
M33219282013 has 0 factors in [2^1, 2^70-1].
M33219282059 has a factor: 18602797953041 - Program: L5.0x
M33219282059 has a factor: 4392386350969217 - Program: L5.0x
M33219282059 has 2 factors in [2^1, 2^70-1].
M33219282067 has 0 factors in [2^1, 2^70-1].
M33219282079 has a factor: 12035375927452699417 - Program: L5.0x
M33219282079 has 1 factors in [2^1, 2^70-1].
M33219282097 has 0 factors in [2^1, 2^70-1].
M33219282101 has a factor: 36076140361687 - Program: L5.0x
M33219282101 has 1 factors in [2^1, 2^70-1].
M33219282121 has a factor: 731938037166137002199 - Program: L5.0x
M33219282121 has 1 factors in [2^1, 2^70-1].
M33219282137 has 0 factors in [2^1, 2^70-1].
M33219282143 has a factor: 5479771195752336793 - Program: L5.0x
M33219282143 has 1 factors in [2^1, 2^70-1].
M33219282203 has a factor: 470385035994481 - Program: L5.0x
M33219282203 has a factor: 42938659516231027201 - Program: L5.0x
M33219282203 has 2 factors in [2^1, 2^70-1].
M33219282211 has 0 factors in [2^1, 2^70-1].
M33219282241 has 0 factors in [2^1, 2^70-1].
M33219282287 has a factor: 151937821815764009 - Program: L5.0x
M33219282287 has 1 factors in [2^1, 2^70-1].
M33219282409 has 0 factors in [2^1, 2^70-1].
M33219282451 has a factor: 92473513137322231 - Program: L5.0x
M33219282451 has 1 factors in [2^1, 2^70-1].
M33219282493 has a factor: 829153291025281 - Program: L5.0x
M33219282493 has 1 factors in [2^1, 2^70-1].
M33219282521 has 0 factors in [2^1, 2^70-1].
M33219282541 has 0 factors in [2^1, 2^70-1].
M33219282589 has 0 factors in [2^1, 2^70-1].
M33219282617 has 0 factors in [2^1, 2^70-1].
M33219282623 has a factor: 16742518441993 - Program: L5.0x
M33219282623 has a factor: 2458226914103 - Program: L5.0x
M33219282623 has 2 factors in [2^1, 2^70-1].
M33219282631 has 0 factors in [2^1, 2^70-1].
M33219282661 has a factor: 921569339581463 - Program: L5.0x
M33219282661 has 1 factors in [2^1, 2^70-1].
M33219282721 has a factor: 178586863908097 - Program: L5.0x
M33219282721 has 1 factors in [2^1, 2^70-1].
M33219282727 has a factor: 4489735680203452409 - Program: L5.0x
M33219282727 has 1 factors in [2^1, 2^70-1].
M33219282773 has 0 factors in [2^1, 2^70-1].
M33219282779 has 0 factors in [2^1, 2^70-1].
M33219282781 has 0 factors in [2^1, 2^70-1].
M33219282821 has a factor: 79104679550253449 - Program: L5.0x
M33219282821 has 1 factors in [2^1, 2^70-1].
M33219282847 has 0 factors in [2^1, 2^70-1].
M33219282869 has 0 factors in [2^1, 2^70-1].
M33219282883 has 0 factors in [2^1, 2^70-1].
M33219282907 has a factor: 797262789769 - Program: L5.0x
M33219282907 has 1 factors in [2^1, 2^70-1].
M33219282923 has a factor: 797262790153 - Program: L5.0x
M33219282923 has 1 factors in [2^1, 2^70-1].
M33219282937 has 0 factors in [2^1, 2^70-1].
M33219282953 has a factor: 797262790873 - Program: L5.0x
M33219282953 has 1 factors in [2^1, 2^70-1].
M33219282979 has 0 factors in [2^1, 2^70-1].
M33219283039 has a factor: 20320368312088457 - Program: L5.0x
M33219283039 has 1 factors in [2^1, 2^70-1].
M33219283063 has 0 factors in [2^1, 2^70-1].
M33219283133 has a factor: 44791286850946817 - Program: L5.0x
M33219283133 has 1 factors in [2^1, 2^70-1].
M33219283147 has a factor: 1044414262141681 - Program: L5.0x
M33219283147 has 1 factors in [2^1, 2^70-1].
M33219283151 has 0 factors in [2^1, 2^70-1].
M33219283183 has a factor: 794416900401712391 - Program: L5.0x
M33219283183 has a factor: 1582367335139023 - Program: L5.0x
M33219283183 has 2 factors in [2^1, 2^70-1].
M33219283217 has a factor: 41658849605921823383 - Program: L5.0x
M33219283217 has 1 factors in [2^1, 2^70-1].
M33219283301 has a factor: 103297620335723969 - Program: L5.0x
M33219283301 has 1 factors in [2^1, 2^70-1].
M33219283319 has 0 factors in [2^1, 2^70-1].
M33219283337 has a factor: 142251814421401423 - Program: L5.0x
M33219283337 has 1 factors in [2^1, 2^70-1].
M33219283351 has a factor: 20662659998588809 - Program: L5.0x
M33219283351 has 1 factors in [2^1, 2^70-1].
M33219283369 has 0 factors in [2^1, 2^70-1].
M33219283373 has a factor: 25682691677033999 - Program: L5.0x
M33219283373 has 1 factors in [2^1, 2^70-1].
M33219283429 has a factor: 114459561135898990799 - Program: L5.0x
M33219283429 has 1 factors in [2^1, 2^70-1].
M33219283519 has a factor: 1328771340761 - Program: L5.0x
M33219283519 has 1 factors in [2^1, 2^70-1].
M33219283529 has a factor: 35725346278427761 - Program: L5.0x
M33219283529 has 1 factors in [2^1, 2^70-1].

Batalov · 2012-05-10, 22:42

Why stop there? We should start testing trillion-digit numbers already.

Code:

M3321928096379 has a factor 6643856192759
M3321928097483 has a factor 6643856194967
M3321928097759 has a factor 6643856195519
M3321928098803 has a factor 6643856197607
M3321928100303 has a factor 6643856200607
M3321928102019 has a factor 6643856204039
M3321928104431 has a factor 6643856208863
M3321928132499 has a factor 664385626499801
M3321928147817 has a factor 664385629563401
M3321928390169 has a factor 664385678033801
M3321928439759 has a factor 664385687951801
M3321928556909 has a factor 664385711381801
M3321928559699 has a factor 664385711939801
M3321928570811 has a factor 664385714162201
M3321928639961 has a factor 664385727992201
M3321928651313 has a factor 664385730262601
M3321928799261 has a factor 664385759852201
M3321928836311 has a factor 664385767262201
M3321929068193 has a factor 664385813638601
M3321928164167 has a factor 3986313797000401
M3321928736839 has a factor 3986314484206801
M3321929056309 has a factor 3986314867570801
M3321928125443 has a factor 737016261623285753
M3321928177429 has a factor 4080603422302944737

wblipp · 2012-05-11, 00:47

Let me know the web pages for these and I'll add a link to the them.

NBtarheel_33 · 2012-05-11, 02:53

The question now, of course, is whether the EFF prizes are paid cumulatively, if a prime happens to be found that is both 100M and 1B digits in size. And would they institute higher prizes for higher orders of magnitude of digits. Hmm....

axn · 2012-05-11, 03:10

Quote:

Originally Posted by NBtarheel_33

The question now, of course, is whether the EFF prizes are paid cumulatively

No, they're not. HTH.

LaurV · 2012-05-11, 04:29

Cute, haha, but what's the point? I am sure Serge's post was a joke, as he usually does (see his algorithm with adding 13). Here is a single line in pari:

Code:

(10:25:19) gp > p=nextprime(10^20*log(10)/log(2)); cnt=0; while(1,if(p%4==3&&isprime(q=2*p+1),print("M"p" has a factor "q);cnt++);p=nextprime(p++))
M332192809488736240559 has a factor 664385618977472481119
M332192809488736242551 has a factor 664385618977472485103
M332192809488736243919 has a factor 664385618977472487839
M332192809488736247123 has a factor 664385618977472494247
M332192809488736248023 has a factor 664385618977472496047
M332192809488736261391 has a factor 664385618977472522783
M332192809488736261991 has a factor 664385618977472523983
M332192809488736267871 has a factor 664385618977472535743
<...>
<snip 400 lines with factors removed (about)>
<...>
M332192809488737637371 has a factor 664385618977475274743
M332192809488737640659 has a factor 664385618977475281319
M332192809488737642603 has a factor 664385618977475285207
M332192809488737648999 has a factor 664385618977475297999
M332192809488737649143 has a factor 664385618977475298287
<...>
<snip 400 lines with factors removed (about)>
<ctrl C pressed>
  ***   at top-level: ...cnt=0;while(1,if(p%4==3&&isprime(q=2*p+1),pri
  ***                                             ^--------------------
  *** isprime: user interrupt after 5,297 ms.
  ***   Break loop: type <Return> to continue; 'break' to go back to GP
break> cnt
814
break>^C
(10:25:27) gp >

or if you have a very simple TF routine, done long time ago, as I have (one of the first things I ever did in pari

)

(the second parameter is starting k, the third is ending k, in 2*k*p+1)

Code:

(10:33:32) gp > \r tf
(10:33:34) gp > p=nextprime(10^20*log(10)/log(2)); while(1, printf("%d: ",p); tf(p,0,10^6,0); p=nextprime(p++))
332192809488736234933: Factor not found, try higher start/stop values.
332192809488736234949: Factor not found, try higher start/stop values.
332192809488736234993: Factor not found, try higher start/stop values.
332192809488736235033: Factor found: 2^332192809488736235033-1 is divisible by 1979869144552867960796681
<...>
<lots of lines with no factors scissored out, I will let only the one with factors>
<...>
332192809488736235227: Factor found: 2^332192809488736235227-1 is divisible by 118006180485921727784628119
332192809488736235309: Factor found: 2^332192809488736235309-1 is divisible by 2657542475909889882473
332192809488736235513: Factor found: 2^332192809488736235513-1 is divisible by 1993156856932417413079
332192809488736235779: Factor found: 2^332192809488736235779-1 is divisible by 725509095923399938941337
332192809488736235981: Factor found: 2^332192809488736235981-1 is divisible by 239178822831890089906321
332192809488736236499: Factor found: 2^332192809488736236499-1 is divisible by 3774374701411021119101639
332192809488736236983: Factor found: 2^332192809488736236983-1 is divisible by 725509095923399941570873
332192809488736237123: Factor found: 2^332192809488736237123-1 is divisible by 13287712379549449484921
332192809488736237339: Factor found: 2^332192809488736237339-1 is divisible by 79726274277296696961361
332192809488736237793: Factor found: 2^332192809488736237793-1 is divisible by 7972627427729669707033
332192809488736238023: Factor found: 2^332192809488736238023-1 is divisible by 183370430837782403388697
332192809488736238521: Factor found: 2^332192809488736238521-1 is divisible by 1993156856932417431127
332192809488736238593: Factor found: 2^332192809488736238593-1 is divisible by 940105650853123555218191
332192809488736238767: Factor found: 2^332192809488736238767-1 is divisible by 39863137138648348652041
332192809488736238953: Factor found: 2^332192809488736238953-1 is divisible by 7308241808752197256967
332192809488736238989: Factor found: 2^332192809488736238989-1 is divisible by 432515037954334583163679

So, what is the point? We can "generate" this "small factors" (i.e. with small k) in milliseconds, in ANY quantity we want, millions of them. But there is no use and no value in it. The amount of exponents left behind is millions of millions of millions, and we would not be able to LL even ONE of them in the next few hundred years... And if we ever will be able to LL any of them, then with such a powerful computer/system, who would care about such factors those systems could produce in picoseconds?

aketilander · 2012-05-11, 06:19

Quote:

Originally Posted by LaurV

Cute, haha, but what's the point? I am sure Serge's post was a joke, as he usually does (see his algorithm with adding 13).

No I don't think there is a point. I was as I said "a bit carried away", but since you asked the question I was starting to think about it and thinking more about it its a very good question. Formulated in a different way: "Could there be a point ...?"

Well maybe. Generally speaking it could have some value to know that the distribution of factors are as expected even very high up among the Mersenne numbers. Some things about the Mersenne numbers/primes are just taken for granted but there is no mathematical proof of it, so at least it could be good to have empirical proofs. If I remember it rightly (I am on the run just now so I don't have the time to make a proper check) there is not even a mathematical proof of wether there are infinitely many composite (prime exponent) Mersenne numbers or not? All of us take this for granted, but showing that there are composites high up confirms this at least up to that limit.

So thinking more about it I really think there is a good point in having sets of Mersenne numbers trail factored way up which could be studied more closely.

But that wasn't really why I did it. It was more because it was nice doing it and nice finding a bunch of factors like that and after all Operation Billion Digits is a whimsical project.

Quote:

Originally Posted by wblipp

Let me know the web pages for these and I'll add a link to the them.

There is no webpage, sorry.

And I have googled all 62 factors without finding any of them on the internet.

They are not included in Will Edgington's list here: http://www.garlic.com/~wedgingt/resu...k.split.aw.bz2

And they did not appear neither on PrimeNet nor on Mersenne aries since they don't cover these ranges.
I have submitted them to Mersenne aries now and you can find them under the largest exponent covered by the database here:
http://mersenne-aries.sili.net/expon...61455669855551

And I have, of course, searched this forum as well without finding any mention of them before.

So to the best of my knowledge they were not known before.

ET_ · 2012-05-11, 08:54

I think Will Edgington may enjoy them...

Luigi

James Heinrich · 2012-08-20, 20:29

Quote:

Originally Posted by LaurV

Here is a single line in pari
So, what is the point? We can "generate" this "small factors" (i.e. with small k) in milliseconds, in ANY quantity we want, millions of them. But there is no use and no value in it.

Not entirely true; I found your 1-line program very useful since I wanted to fill in the known-factor list quickly on http://mersenne-aries.sili.net for the beyond-PrimeNet M(10⁹)-M(2³²) range. I had already generated about 10000 factors with k<10 in a far more inefficient manner; your PARI code was much much much faster, so I'm taking it up a bit.

Quote:

Originally Posted by aketilander

I have submitted them to Mersenne aries now and you can find them under the largest exponent covered by the database here:
http://mersenne-aries.sili.net/expon...61455669855551

I probably rearranged stuff and broke your link, sorry. The factor you linked to is for an exponent 10x larger than what's currently supported on Mersenne-aries: it currently supports only prime Mersenne exponents up to M(2³²).

Incidentally, I now generate a daily exponent status report in the same format at PrimeNet, but for M(10⁹)-M(2³²):
mersenne-aries.sili.net/primenet_gimps_summary_1G/
PM or email me if you have any interest in doing broad TF pre-factoring in this range.

ixfd64 · 2012-08-21, 02:45

A factor I found several years ago:

Quote:

M404253979041338401 has a factor: 4272353326450636394907689

LaurV · 2012-08-21, 04:45

Quote:

Originally Posted by James Heinrich

I found your 1-line program very useful since I wanted to fill in the known-factor list quickly <snip>. your PARI code was much much much faster, so I'm taking it up a bit.

Thanks. Why you didn't say something (here or PM)?. I played with this "elementary" things since ages and I have much faster (optimized, well, as much as pari can do) routines for eliminating small factors, and also I have files with ALL factors for Mp with p<10 billions (ten times the range of GIMPS, includes the 3.x billions of the OBD range) for up to 49 bits or so, many megabytes and few months of work. Here for example is a routine to eliminate the SG primes wich are 3 mod 4 (their correspondent mersenne are all composite, as discussed below in the thread, I think I posted variations of this many times).

Code:

elimSGp3m4(start,stop,file,pflag)=
{
    my(p,d,cnt);
    p=max(start,5);
    cnt=0;
    while(p<stop, 
        until(p%4==3 && isprime(d=2*p+1), 
            p=nextprime(p+1)
        ); 
        if(p<stop,
            if(bitand(pflag,1), printf("...%d...%c",p,13));
            if(bitand(pflag,2), print("M"p" is divisible by "d));
            if(bitand(pflag,4), write(file,p,",",d));
            cnt++
        )
    );
    return(cnt)
};

"file" is the output, pflag is to print them on screen or not. Later on you can use a perl script to eliminate those in "file" from the prime candidate list.

Here is some TF variation, which can be used to eliminate very fast exponents with small k, up to 2^30 or so. About half of them will be gone with this "filtering". There is also a function called "ratf" (random tf) which does the same but looking for k first. Ratfpro is its "pro" version which splits the output file in different files according with bit level and exponent size. For this ratfpro, you can create a file called "flags.txt" to "gracefully shut it down", you create that file and put a single line in it, containing a "0" (ascii char code 48, then end of line). When you want your program to stop, edit the file and put a "1" and it will stop after the next save checkpoint, so you can resume next time without losing candidates (no gaps).

Code:

ten=log(10);
two=log(2);

/* p= exponent, start/stop=values of k in 8*k*p+{s*p}+1 */
tf(p,start,stop,fisout)=
{
    if(p<3 || !isprime(p),print("p has to be an odd prime"); return(0));
    
    if(p<11,print("2^"p"-1 is prime!"); return(2));
    
    gettime();
    /*m=1<<p-1;*/
    if(stop==0, error("No Stop"));/*stop=sqrtint(m)\(8*p)+1);*/
    sp0=2*(4-p%4)*p;
    sp1=8*p-sp0;
    k=start;
    if(k==0,d=sp0+1;t=1,d=8*k*p+1;t=0);
    
/*    while(k<=stop && (n=m%d) /* faster than exponentiation n=(lift(Mod(2,d)^p)-1)*/   
    while(k<=stop && (n=lift(Mod(2,d)^p)-1) !=0,
        if(t==0, d+=sp0, d+=sp1; k+=t); 
        t=1-t; 
        if(bitand(k,1048575)==0 && t==0,
            printf("... %d bMit (k: %d) -- last tested: %d, %d digits (2^%d++), %11.6f ms/iter ...%c",
                    k>>20,k,d,ceil(log(d)/ten),floor(log(d)/two),gettime()/1048576.0,13);
            if(fisout<>0, write(fisout,k-1))
        )
    ); 
    
    if(n==0, 
/*        print("Factor found: 2^"p"-1 = "m" is divisible by "d); return(1), */
        print("Factor found: 2^"p"-1 is divisible by "d); return(1),
    /*else*/
/*        if(stop>=sqrtint(m)\(8*p)+1,
            print("2^"p"-1 = "m" is prime!"); return(2),
        /*else*/
            print("Factor not found, try higher start/stop values."); return(0)
/*        )*/
    );
}

/* get the k in 8*k*p+{s*p}+1 (negativ for s!=0. else positiv)  */
getk(d,p)=
{
    if(Mod(2,d)^p!=Mod(1,d),print("Not a factor!");return);
    
    if((a=((d-1)/p))%8==0,return(a/8),return(-(a-2*(4-p%4))/8));
}

/*get smallest p such as n divides 2^p-1*/
getp(n,limt)=
{
    if(n<3 || n%2==0, print("Only odd positive numbers!");return);
    
    rg=1;
    sm=0;
    until(rg==1 || sm>=limt, 
        rg+=n;
        while(rg%2==0 && sm<limt, 
            rg>>=1;
            sm++;
            if(bitand(sm,1048575)==0, print(sm));
        )
    );
    return(sm);
}

/*getp for a prime n (in this case p is a divisor of n-1*/
getpfp(n)=
{
    my(c);
    c=divisors(n-1);
    for(i=1,#c,
        if(c[i]<1000000000 && Mod(2,n)^c[i]==1, return(c[i]))
    );
    return(0);
}

/* "random" trial factoring, specify a starting possible factor and the outfput file */
ratf(a,fis)=
{
    if(fis==0, print("Specify an output file!"); return(0));
    while(1,
        until(a%8==1 || a%8==7,a=nextprime(a+1));
        c=factorint(a-1)[,1]~;
        for(i=1,#c,
            if(c[i]<1000000000 && Mod(2,a)^c[i]==1, print(a","c[i]); write(fis,a","c[i]))
        )
    );
}

/*same as above, but split the output to different files depending on n and k
  -if a=-1, it will read the last_k from the file, assuming the file has ONE LINE only
  -use the flags.txt file to gracefully stop it
*/
ratfpro(a,printstep)=
{
    my(tnextpr,tmod,tfactint,telse);
    if(a==-1, a=read("fact_last_k.txt"));
    print("Starting/continuing from: "a);
    tnextpr=tfactint=tmod=telse=0;
    if(printstep==0,printstep=2^20);
    prst=a;
    gettime();
    while(1,
        telse+=gettime();
        until(a%8==1 || a%8==7,a=nextprime(a+1));
        tnextpr+=gettime();
        if(a>prst, 
            prst=a+printstep;
            printf("... %d, (%d digits, 2^%d++) --- Timers:  %6.4f,  %6.4f,  %6.4f,  %6.4f  (seconds)\n",
                    a,ceil(log(a)/ten),floor(log(a)/two),
                    tnextpr/1000, tfactint/1000, tmod/1000, telse/1000);
            extern("del fact_last_k.bak");
            extern("ren fact_last_k.txt fact_last_k.bak");
            write("fact_last_k.txt",a-1);
            shouldstop=read("flags.txt");
            if(shouldstop==1,break)
        );
        telse+=gettime();
        c=factorint((a-1)>>1)[,1]~;
        tfactint+=gettime();
        for(i=1,#c,
            if(c[i]<10000000000,
                telse+=gettime();
                if(Mod(2,a)^c[i]==1, 
                    tmod+=gettime();
                    print(a","c[i]"  ");
                    if(c[i]<1000000000,fis="fact_0B_",
                      if(c[i]<2000000000,fis="fact_1B_",
                        if(c[i]<3000000000,fis="fact_2B_",
                          if(c[i]<4000000000,fis="fact_3B_",
                            if(c[i]<5000000000,fis="fact_4B_",
                              if(c[i]<6000000000,fis="fact_5B_",
                                if(c[i]<7000000000,fis="fact_6B_",
                                  if(c[i]<8000000000,fis="fact_7B_",
                                    if(c[i]<9000000000,fis="fact_8B_",
                                      fis="fact_9B_"; 
                                      break)))))))));
                    expo=40;
                    k=1<<expo;
                    for(j=1,40,
                        if(a<k,fis=concat(fis,expo); break,
                            k<<=1; expo++));
                    write(fis,a","c[i]),
                /*else*/
                    tmod+=gettime()
                ),
            /*else*/
                break
            )
        )
    );
}

/*same as above, but use modular order instead of factoring k-1*/
/*for bigger stuff it may become faster than factoring k-1*/
ratfzno(a,printstep)=
{
    my(tnextpr,tprchk,tznord,telse);
    if(a==-1, a=read("fact_last_k"));
    tnextpr=tznord=tprchk=telse=0;
    gettime();
    if(printstep==0,printstep=2^20);
    prst=a;
    while(1,
        until(a%8==1 || a%8==7,a=nextprime(a+1));
        tnextpr+=gettime();
        if(a>prst, 
            prst=a+printstep;
            printf("... %d, (%d digits, 2^%d++) --- Timers: %10.4f, %10.4f, %10.4f, %10.4f seconds\n",
                    a,ceil(log(a)/ten),floor(log(a)/two),
                    tnextpr/1000, tznord/1000, tprchk/1000, telse/1000);
            write("fact_last_k",a));
        telse+=gettime();
        c=znorder(Mod(2,a));
        tznord+=gettime();
        if(isprime(c),
            tprchk+=gettime();
            if(c<1000000000,fis="fact_0B_",
              if(c<2000000000,fis="fact_1B_",
                if(c<3000000000,fis="fact_2B_",
                  if(c<4000000000,fis="fact_3B_",
                    if(c<5000000000,fis="fact_4B_",
                      if(c<6000000000,fis="fact_5B_",
                        if(c<7000000000,fis="fact_6B_",
                          if(c<8000000000,fis="fact_7B_",
                            if(c<9000000000,fis="fact_8B_",
                              if(c<10000000000,fis="fact_9B_",
                                telse+=gettime();
                                next))))))))));
            expo=40;
            k=1<<expo;
            for(j=1,40,
                if(a<k,fis=concat(fis,expo); break,
                    k<<=1; expo++));
            print(a","c"  ");
            write(fis,a","c);
            telse+=gettime()
        );
        tprchk+=gettime()
    );
}

/* it will look for prime factors of the form 2*pr(v)+1
   v can include 2, p and other odd primes (or else)

call sample (copy/paste):
 > p=23; xx=[0,0,0]; while((xx=pptf([2,p],xx[2],xx[2]+10^4,10^6,0,0))[3]!=p,); xx

immediate subsequent calls (to find other small factors):
 > xx=%; while((xx=pptf([2,p],xx[2],xx[2]+10^4,10^6,0,0))[3]!=p,); xx

*/
pptf(v,k,limt,iter,pp,pv)=
{
    gata=0;
    a=0;  /*not necessary*/
    pr=prod(i=1,#v,v[i]);
    while(k<li

I did this long ago, if you have trouble with some of them, give me a sign.

I am currently playing with implementing P-1 on cuda. For that, I started with a pari implementation, to see how the things go around. If you are interested in going "deeper" with the "filtering", then you can play with the next pari script too:
[edit limit, I cut it out, let's see with attach]
[grr need to rename it txt]

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Operation: Billion Digits	clowns789	Operation Billion Digits	575	2023-01-02 18:57
Thank you for a database capable of holding a billion+ numbers	rcv	FactorDB	1	2017-10-02 06:18
The "one billion minus 999,994,000" digits prime number	a1call	Miscellaneous Math	179	2015-11-12 14:59
Program to TF Mersenne numbers with more than 1 sextillion digits?	Stargate38	Factoring	24	2011-11-03 00:34
question range 1 billion to 2 billion?	Unregistered	Information & Answers	7	2010-08-12 06:25

2012-05-11, 00:47	#3
wblipp "William" May 2003 Near Grandkid 100101000110₂ Posts	Let me know the web pages for these and I'll add a link to the them.

2012-05-11, 02:53	#4
NBtarheel_33 "Nathan" Jul 2008 Maryland, USA 45B₁₆ Posts	The question now, of course, is whether the EFF prizes are paid cumulatively, if a prime happens to be found that is both 100M and 1B digits in size. And would they institute higher prizes for higher orders of magnitude of digits. Hmm....

2012-05-11, 08:54	#8
ET_ Banned "Luigi" Aug 2002 Team Italia 2×7×347 Posts	I think Will Edgington may enjoy them... Luigi