mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Operazione Doppi Mersennes

Reply
 
Thread Tools
Old 2013-09-06, 20:19   #1
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

3×3,109 Posts
Default News from sub-project Deep Sieving

This one doesn't divide. Statistically speaking, additional O(p) primes are needed.
Batalov is offline   Reply With Quote
Old 2013-09-06, 20:59   #2
aketilander
 
aketilander's Avatar
 
"Åke Tilander"
Apr 2011
Sandviken, Sweden

2×283 Posts
Default

Quote:
Originally Posted by Batalov View Post
This one doesn't divide. Statistically speaking, additional O(p) primes are needed.
"Also can be written as 507568*(2^1398269-1)+1"

Congratulations to the prime! Which is also first MMp factor prime on the list of top 5000! :-)

Last fiddled with by aketilander on 2013-09-06 at 21:01
aketilander is offline   Reply With Quote
Old 2013-09-06, 21:08   #3
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

932710 Posts
Default

It certainly is not an MMp factor, though. (This has been checked.)
Batalov is offline   Reply With Quote
Old 2013-09-06, 21:54   #4
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

17·251 Posts
Default

Quote:
Originally Posted by Batalov View Post
It certainly is not an MMp factor, though. (This has been checked.)
Is there a more accurate term for such a find? An "MMp factor-candidate prime", perhaps?
Mini-Geek is offline   Reply With Quote
Old 2013-09-07, 05:07   #5
aketilander
 
aketilander's Avatar
 
"Åke Tilander"
Apr 2011
Sandviken, Sweden

2×283 Posts
Default

Quote:
Originally Posted by Batalov View Post
It certainly is not an MMp factor, though. (This has been checked.)
Oh I know, but I couldn't come up with a better term, I was thinking

MMp factorish prime
MMp factor class prime
MMp possible factor prime

etc.

but none was really good so I simply choose the simplest. It would be good though if we all could agree on a common way of labeling these primes. Maybe we could first collect a number of possibilities and then conduct a vote? Many kind of primes seem to be labeled after the one who "discovered" them or made the significant mathematical analysis ot them, Riesel, Mersenne etc., others seem to have their name from a significant mathematical property like factorial, home etc

Last fiddled with by aketilander on 2013-09-07 at 05:20
aketilander is offline   Reply With Quote
Old 2013-09-07, 07:06   #6
aketilander
 
aketilander's Avatar
 
"Åke Tilander"
Apr 2011
Sandviken, Sweden

2·283 Posts
Default

One other thing Batalov: Have you tested all other possible smaller K:s (< 507568) for M1398269 or was this just a storke of luck?
aketilander is offline   Reply With Quote
Old 2013-09-07, 07:45   #7
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

3×3,109 Posts
Default

I haven't checked all possible k's.

I did however check all k values that could produce MMp-divisors, i.e. k \eq 0, 5, 8, 9 (mod 12). That is roughly half of them. I did not check k \eq 2, 3, 6, 11 (mod 12).
Batalov is offline   Reply With Quote
Old 2013-09-07, 09:22   #8
aketilander
 
aketilander's Avatar
 
"Åke Tilander"
Apr 2011
Sandviken, Sweden

2×283 Posts
Default

Quote:
Originally Posted by Batalov View Post
I haven't checked all possible k's.

I did however check all k values that could produce MMp-divisors, i.e. k \eq 0, 5, 8, 9 (mod 12). That is roughly half of them. I did not check k \eq 2, 3, 6, 11 (mod 12).
That is impressive! You must have put a lot of force into that!
aketilander is offline   Reply With Quote
Old 2013-09-07, 09:23   #9
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

10010110000002 Posts
Default News from sub-project Deep Sieving

Quote:
Originally Posted by Batalov View Post
It certainly is not an MMp factor, though. (This has been checked.)
Should I assume that you are testing/trial-factoring above k=500,000 set up by Tony Forbes, then?

I have recorded all possible k for MM34 and MM35 up to k=500,000 thanks to Tony: I may clear some of them and extend the table limit if you still have your logs...

Luigi

Last fiddled with by ET_ on 2013-09-07 at 09:26
ET_ is offline   Reply With Quote
Old 2013-09-07, 18:47   #10
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

3·3,109 Posts
Default

Quote:
Originally Posted by ET_ View Post
...Tony did his sieving work for MM34 and MM35 up to 20G for k<500,000, so we just double-checked his work for k < 1,000.
I scanned the whole thread and found this note.
I sieved to >20G for k<2,000,000. In just a few hours, on one CPU. It is straightforward with Pari: for each prime q, k0 = Mod((q-1)/2,q) / (Mod(2,q)^p-1), then eliminate all k = k0 + mq from an array of k's. For sufficiently large q, this is not even a loop, but only k0 or nothing at all.

In other words, I don't quite understand why you are so stuck on sieving:
1. Sieving alone is pointless without tests.
2. One should sieve only as long as sieving is faster than actually testing.

I ran LLR for MM35 "divisor pool" (still running, approaching k~1,400,000). This was the only prime so far. This approximately matches the expectation: probability of being prime is O(1/p), and on top of that the probability of dividing MMp would be O(1/k) (unsure)? So, for large p, even finding a prime was relatively lucky, let alone a divisor of MMp.

I also have sieve files for MM34, 36 and 37, but the 36/37 tests are five times slower, and a divisor of MM34 would soon be flushed out of Top-5000, so I concentrated on attacking MM35.
Batalov is offline   Reply With Quote
Old 2013-09-07, 19:08   #11
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

3·3,109 Posts
Default

Here's the Pari interactive sieving script. It can be stopped periodically, the sieve array saved, and then the sieving can be continued.
Code:
# gp -p 2000000
#sieve limit:
M=2000000;
#the P in MMp:
P=1398269;


allocatemem(800000000)
K=vector(M);
forprime(p=5,M, k=Mod((p-1)/2,p)/(Mod(2,p)^P-1);forstep(i=lift(k)+1,M,p,K[i]=1));
p=M;
while(p=nextprime(p+1), if((i=lift(Mod((p-1)/2,p)/(Mod(2,p)^P-1)))<M,K[i+1]=1);K[1]=p);
# can stop with Ctrl-C

#write the sieve file
write("si13y",P); write("si13y","#"K[1]);
forstep(i=5,M-1,[3,1,3,5],if(K[i+1]==0,write("si13y",i)))

#go on
p=K[1];
while(p=nextprime(p+1), if((i=lift(Mod((p-1)/2,p)/(Mod(2,p)^P-1)))<M,K[i+1]=1);K[1]=p);
#etc, after a while stop  with Ctrl-C, write, continue
This probably can be gp2c'd. I didn't bother, the speed was satisfactory for me.
Batalov is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Deep Sieving MM49 in parallel ET_ Operazione Doppi Mersennes 22 2016-07-28 11:23
Deep Hash diep Math 5 2012-10-05 17:44
The news giveth, the news taketh away... NBtarheel_33 Hardware 17 2009-05-04 15:52
Question on going deep and using cores MercPrime Software 22 2009-01-13 20:10
Deep Sieving 10m Digit Candidates lavalamp Open Projects 53 2008-12-01 03:59

All times are UTC. The time now is 08:03.

Sun Feb 28 08:03:29 UTC 2021 up 87 days, 4:14, 0 users, load averages: 2.23, 1.66, 1.46

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.