News from sub-project Deep Sieving

[Batalov]

This one doesn't divide. Statistically speaking, additional O(p) primes are needed.

[aketilander]

Originally Posted by Batalov

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! :-)

[Batalov]

It certainly is not an MMp factor, though. (This has been checked.)

[TimSorbet]

Originally Posted by Batalov

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?

[aketilander]

Originally Posted by Batalov

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

[aketilander]

One other thing Batalov: Have you tested all other possible smaller K:s (< 507568) for M1398269 or was this just a storke of luck?

[Batalov]

I haven't checked all possible k's.

I did however check all k values that could produce MMp-divisors, i.e. k 0, 5, 8, 9 (mod 12). That is roughly half of them. I did not check k 2, 3, 6, 11 (mod 12).

[aketilander]

Originally Posted by Batalov

I haven't checked all possible k's.

I did however check all k values that could produce MMp-divisors, i.e. k 0, 5, 8, 9 (mod 12). That is roughly half of them. I did not check k 2, 3, 6, 11 (mod 12).

That is impressive! You must have put a lot of force into that!

[ET_]

Originally Posted by Batalov

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

[Batalov]

Originally Posted by ET_

...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, k₀ = Mod((q-1)/2,q) / (Mod(2,q)^p-1), then eliminate all k = k₀ + mq from an array of k's. For sufficiently large q, this is not even a loop, but only k₀ 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]

Here's the Pari interactive sieving script. It can be stopped periodically, the sieve array saved, and then the sieving can be continued.

# 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.