Vanishing factors

[Batalov]

Find a proper factor of any Mersenne number 2^p-1 where prime p=n!+1.

A little background:
The set of indices n is OEIS A002981: 0, 1, 2, 3, 11, 27, 37, 41, 73, 77, 116, 154, 320, 340, 399, 427, 872, 1477, 6380,...
The set of p is OEIS A088332: 2, 3, 7, 39916801, 10888869450418352160768000001, ...
M2, M3, M7 are prime.
M39916801 is composite without known factors.
For a few larger Mps (n=27, 37, 41), no factors are known with search limits of k<10^13.

The factors of 2^(n!+1)-1 would be of form f = 2k(n!+1)+1 and it is easy to observe that for many small k, f are trivially composite:
f = 2kn!+(2k+1) is composite when gcd(2k+1,n!) > 1. This and the sparseness of the set makes finding specific factors hard, even though it is obvious that almost all mentioned Mersenne numbers are composite.

[Batalov]

After prototyping and bombarding this problem with Pari, I am switching to optimization and trying an order of magnitude deeper.
No solutions so far.

One acceleration is to sieve on gcd(2k+1,n!) condition, another, small one - C instead of Pari.
(Only for M_11!+1, the optimal tool is still mfaktc and some P-1 runs on a side.)
______________

P.S. Built a C binary that is roughly 10 times faster than the Pari/GP test now. On to testing n=27 and 37 to k<10¹⁴...

[Batalov]

For primorials, a similar puzzle is much easier:
firstly, M(7#+1) and M(11#+1) are fully factored, but also M(31#+1) has a factor: 1288202392*(31#+1)+1.

Later, found 11/11 @8PM: 2*26691479416344*(31#+1)+1 | M(31#+1)

[LaurV]

How much I would like you to part with those 10 bucks**, I did a bunch of "random" trial factoring for 11, 27, 37, 41, 73, 77 (for about 1 day in 4 cores), nothing turned in.
I also did this, which took 4 days in 2 cores (but PrimeNet didn't want it)

UID: LaurV/bc1, M39916801 completed 1 ECM curve, B1=1000000, B2=100000000, We1: 0EC42491

-----------------
** edit: Batalov said in a parallel thread that he will donate $10 to the forum for each factor that we can turn in

[ATH]

Originally Posted by Batalov

For primorials, a similar puzzle is much easier:
firstly, M(7#+1) and M(11#+1) are fully factored, but also M(31#+1) has a factor: 1288202392*31#+1.

You mean the factor is: 1288202392*(31#+1)+1 = 1288202392*31#+1288202393


I also tested M(73!+1), M(77!+1), M(116!+1) and M(154!+1) but only up to k=2*10^9

I found out that after trialfactoring candiates 2*k*(150209!+1)+1 it would take ~ 5 days to test 1 candidate on M(150209!+1) with GMP :)

[rajula]

Originally Posted by LaurV

I also did this, which took 4 days in 2 cores (but PrimeNet didn't want it)

UID: LaurV/bc1, M39916801 completed 1 ECM curve, B1=1000000, B2=100000000, We1: 0EC42491

This curve does show up at mersenne.org.

SB: and my (larger) curve shows up in http://www.mersenne.ca/exponent/39916801

[Batalov]

Originally Posted by ATH

You mean the factor is: 1288202392*(31#+1)+1 = 1288202392*31#+1288202393


I also tested M(73!+1), M(77!+1), M(116!+1) and M(154!+1) but only up to k=2*10^9

I found out that after trialfactoring candiates 2*k*(150209!+1)+1 it would take ~ 5 days to test 1 candidate on M(150209!+1) with GMP :)

Yes, exactly, 1288202392*(31#+1)+1. I only found that lonely k (in the first chunk of a rather large region) and wrote the messages too quickly.

[LaurV]

Originally Posted by rajula

This curve does show up at mersenne.org.

Huh? You are right, but in my p95 log file I have an error
It does not seem as it retried to send it...

BTW, how long your curve took?

[Batalov]

A day or something like that (6 threads). t30 (B1=250k) or maybe ~28digit (B1=150k) curves are probably appropriate, given the TF level of 80-bit.
_______________

It would now seem that my money is as safe as John Conway's 20 bucks.

I will post my current limits (and the program) some time later.