Mersenne Semiprimes

[Brian-E]

Thanks RDS and alpertron for the reactions and pointers.

[R.D. Silverman]

Originally Posted by Brian-E

Thanks RDS and alpertron for the reactions and pointers.

Further hint:

Estimate 2*pi(n/2) + 3*pi(n/3) + 5*pi(n/5) + ...... sqrt(n) pi(sqrt(n)).

This is an easy Stieltje's integration. Or, if you want an error term,
just apply Euler-MacLauren. Use the PNT to estimate pi(n).

[CRGreathouse]

Originally Posted by R.D. Silverman

Further hint:

Estimate 2*pi(n/2) + 3*pi(n/3) + 5*pi(n/5) + ...... sqrt(n) pi(sqrt(n)).

For a Mersenne semiprime?

[R.D. Silverman]

Originally Posted by CRGreathouse

For a Mersenne semiprime?

No, for a semiprime in general, of course. Since Mersenne numbers are co-prime, one could not apply a similar sum to them. One can set up a Stieltje's
integral that runs over the Mersenne numbers, but a prime that divides
M_p can only divide one of them, so a sieve type sum will not work.


I'd want to re-read Sam Wagstaff's paper on estimating Mersenne prime frequency before trying to estimate Mersenne semiprimes.

[CRGreathouse]

Originally Posted by R.D. Silverman

I'd want to re-read Sam Wagstaff's paper on estimating Mersenne prime frequency before trying to estimate Mersenne semiprimes.

IIRC it just treats Mersenne numbers (with prime exponents) as random numbers their size which have smallest prime factor at least (smallest candidate factor). It doesn't feel like it should be a good model but I guess it does well enough.

[ATH]

Found factor of M(p²)/M(p) for p=74207281:
508014103943653104553301983 = 2 * 46126737231 * 74207281² + 1

I also continued factoring the numbers in the list without factors, but no luck on those. Thanks to Ernst for letting me use Mlucas factoring code.

p	Factor(s) of M(p2)/M(p)
--------------------------------------------------
2	Prime
3	Prime
5	601,1801
7	Prime
13	4057
17	12761663
19	9522401530937
31	280651416271709745866686729
61	80730817,301780543,281646330073
89	29123869433,49849688719
107	1167799,377175857
127	14806423,25044595073,72653532113
521	8143231,10857641,4338170063
607	345899921201,166969148315503
1279	103097448872275370551
2203	15714690743
2281	(C) No factor 2*k*p2+1 < 273 (k<907*1012)
3217	102559471991
4253	1844976919,57592220657
4423	(C) No factor 2*k*p2+1 < 274 (k<482*1012)
9689	76729816024661281759
9941	(C) No factor 2*k*p2+1 < 276 (k<382*1012)
11213	(C) No factor 2*k*p2+1 < 277 (k<601*1012)
19937	(U) No factor 2*k*p2+1 < 278 (k<380*1012)
21701	33907204873,153745627424471
23209	17206738756236217
44497	(U) No factor 2*k*p2+1 < 281 (k<610*1012)
86243	(U) No factor 2*k*p2+1 < 275.9 (k<5*1012)
110503	250836575030879,22513968547647823
132049	No factor 2*k*p2+1 < 277.2 (k<5*1012)
216091	No factor 2*k*p2+1 < 278.6 (k<5*1012)
756839	696531210655937,63659341689518360417
859433	17727001955737,667717073666057
1257787	No factor 2*k*p2+1 < 283.7 (k<5*1012)
1398269	34207412811532057
2976221	No factor 2*k*p2+1 < 286.1 (k<5*1012)
3021377	2329356963700884673
6972593	No factor 2*k*p2+1 < 288.6 (k<5*1012)
13466917	No factor 2*k*p2+1 < 290.5 (k<5*1012)
20996011	899298254940726841
24036583	5274651651287933470393
25964951	20225360412972031
30402457	No factor 2*k*p2+1 < 292.9 (k<5*1012)
32582657	3322246487577398706217
37156667	71776963464264825905447
42643801	901972906808890097
43112609	No factor 2*k*p2+1 < 293.9 (k<5*1012)
57885161	No factor 2*k*p2+1 < 295.4 (k<5*1012)
74207281	508014103943653104553301983

[JeppeSN]

Interesting thread!

ATH, thanks for finding a non-trivial factor of $M(74207281^2)$.

I think the table could be improved a bit by noting for each row where no factor of $\frac{M(p^2)}{M(p)}$ is known, whether a PRP test has confirmed that this number is in fact composite, or whether the primality status is still open.

For example it is known from a 2013 comment by Charles R Greathouse IV in A085724 (also linked in the first post of this thread) that $\frac{M(2281^2)}{M(2281)}$ is composite. So its row in the above table could look like this:

2281        Composite; no factor 2*k*p2+1 < 273 (k<907*1012)

Just a suggestion.

/JeppeSN

PS! One can verify that 2281 does not give a new semiprime, with command line:

.\pfgw64.exe -f0 -V -q"(2^(2281^2)-1)/(2^2281-1)"

but it runs for many hours (I am still waiting for the result).

[JeppeSN]

Originally Posted by JeppeSN

PS! One can verify that 2281 does not give a new semiprime, with command line:

.\pfgw64.exe -f0 -V -q"(2^(2281^2)-1)/(2^2281-1)"

but it runs for many hours (I am still waiting for the result).

This was run on a laptop machine that was often paused (put in sleep mode) during the computation, but in case anyone wants to compare with their residue, here is the output from the test:

PFGW Version 3.7.9.64BIT.20141125.Win_Dev [GWNUM 28.6]
 
No factoring at all, not even trivial division

Generic modular reduction using generic reduction AVX FFT length 560K, Pass1=448, Pass2=1280 on A 5200682-bit number
 
(2^(2281^2)-1)/(2^2281-1) is composite: RES64: [2D2764F7AB292478] (452428.4684s+0.0137s)

/JeppeSN

[Batalov]

With a small code patch (like the one described earlier), we can use AVX or FMA3 FFT length 288K PRP test. Much faster. It only takes a couple hours on 2-4 threads.

This is because the tested value is a Phi(p*q, 2) where 2^p-1 is prime; earlier I used this code for Phi(3*p, -b), and now we can use it for any Phi(p*q, 2) including Phi(p^2, 2).

Here is the modified patch:

*** ecm.c.orig       2015-10-07 11:53:54.000000000 +0000
--- ecm.c    2016-02-02 23:36:35.510300832 +0000
***************
*** 1032,1037 ****
--- 1032,1062 ----
        bits = (unsigned long) (w->n * log ((double) w->b) / log ((double) 2.0));
        *N = allocgiant ((bits >> 5) + 5);
        if (*N == NULL) return (OutOfMemory (thread_num));
+
+       if(w->k == 1.0 && abs(w->c) == 1) { /*=== this input means Phi(n,b) with n semiprime ===*/
+           int i,q, knownSmallMers[] = {3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217,
+              4253, 4423, 9689, 9941, 11213, 999999999}; /* for now, just the cases where w->n = p * q, and 2^q-1 is prime */
+           for(i=0; (q=knownSmallMers[i]) < w->n || q*q <= w->n;i++) if((w->n%q) == 0) { /*=== this input means Phi(3,-b^(n/3)) ===*/
+           giant tmp = allocgiant ((bits >> 5) + 5);
+           if (!tmp) return (OutOfMemory (thread_num));
+           ultog (w->b, tmp);
+           power (tmp, q);
+           gtog (tmp, *N);
+           power (*N, w->n/q);
+           iaddg (w->c, *N);
+           iaddg (w->c, tmp);
+           divg (tmp, *N);
+           if(q != w->n/q) {
+             ultog (w->b, tmp);
+             power (tmp, w->n/q);
+             iaddg (w->c, tmp);
+             divg (tmp, *N);
+           }
+           free (tmp);
+           /* w->forced_fftlen = w->n; */ /*=== too late to do this here. Moved before gwsetup() --SB. */
+           if(!w->known_factors || !strcmp(w->known_factors,"1")) {
+                 p = sprintf(buf, "(%lld^%d%+d)", w->b, w->n/q, w->c);
+                 w->known_factors = malloc(p+1);
+                 memcpy(w->known_factors, buf, p+1);
+           }
+           return (0);
+                 }
+       }
+
        ultog (w->b, *N);
        power (*N, w->n);
        dblmulg (w->k, *N);
*** commonc.c.orig      2016-02-02 23:58:06.488286517 +0000
--- commonc.c   2016-02-02 23:47:24.089230397 +0000
***************
*** 3050,3056 ****
  /* should never be asked to factor a number more than we are capable of. */

            if (w->k == 1.0 && w->b == 2 && !isPrime (w->n) && w->c == -1 &&
!               w->work_type != WORK_ECM && w->work_type != WORK_PMINUS1) {
                char    buf[80];
                sprintf (buf, "Error: Worktodo.txt file contained composite exponent: %ld\n", w->n);
                OutputBoth (MAIN_THREAD_NUM, buf);
--- 3050,3056 ----
  /* should never be asked to factor a number more than we are capable of. */

            if (w->k == 1.0 && w->b == 2 && !isPrime (w->n) && w->c == -1 &&
!               w->work_type != WORK_ECM && w->work_type != WORK_PMINUS1 && w->work_type != WORK_PRP) {
                char    buf[80];
                sprintf (buf, "Error: Worktodo.txt file contained composite exponent: %ld\n", w->n);
                OutputBoth (MAIN_THREAD_NUM, buf);

and the worktodo.txt file

[Worker #1]
PRP=1,2,5202961,-1,"1"

[Batalov]

I can run these guys at a leisurely pace

2281        No factor 2*k*p2+1 < 273 (k<907*1012) (known comp.)
4423        No factor 2*k*p2+1 < 274 (k<482*1012) 
...but perhaps not these :-)
9941        No factor 2*k*p2+1 < 276 (k<382*1012) 
11213       No factor 2*k*p2+1 < 277 (k<601*1012)
...even though someone like David 'Squirrels' Stanfill just might!

[Batalov]

[Wed Feb  3 01:19:54 2016 UTC]
M5202961/M2281 is not prime.  RES64: 2D2764F7AB292478. We8: 00000000,00000000
[Wed Feb  3 04:36:31 2016 UTC]
M19562929/M4423 is not prime.  RES64: 83DA690553D9EE3C. We8: 00000000,00000000
...
[Work thread Feb 3 05:02] Starting PRP test of M98823481/M9941 using FMA3 FFT length 5376K, Pass1=896, Pass2=6K, 18 threads
...
[Work thread Feb 3 05:47] Iteration: 200000 / 98813540 [0.20%], ms/iter:  2.215, ETA: 60:41:15
[Work thread Feb 3 05:48] Iteration: 210000 / 98813540 [0.21%], ms/iter:  2.216, ETA: 60:41:25

That's not bad for a "M98823481" candidate size! I am going to run these last two, too.