Thanks RDS and alpertron for the reactions and pointers.

[QUOTE=Brian-E;385190]Thanks RDS and alpertron for the reactions and pointers.[/QUOTE]

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

[QUOTE=R.D. Silverman;385242]Further hint:

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

For a [i]Mersenne[/i] semiprime? :confused:

[QUOTE=CRGreathouse;385251]For a [i]Mersenne[/i] semiprime? :confused:[/QUOTE]

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.

[QUOTE=R.D. Silverman;385255]I'd want to re-read Sam Wagstaff's paper on estimating Mersenne prime frequency before trying to estimate Mersenne semiprimes.[/QUOTE]

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.

Found factor of M(p[SUP]2[/SUP])/M(p) for p=74207281:
508014103943653104553301983 = 2 * 46126737231 * 74207281[SUP]2[/SUP] + 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.

[CODE]
p Factor(s) of M(p[sup]2[/sup])/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*p[sup]2[/sup]+1 < 2[sup]73[/sup] (k<907*10[sup]12[/sup])
3217 102559471991
4253 1844976919,57592220657
4423 (C) No factor 2*k*p[sup]2[/sup]+1 < 2[sup]74[/sup] (k<482*10[sup]12[/sup])
9689 76729816024661281759
9941 (C) No factor 2*k*p[sup]2[/sup]+1 < 2[sup]76[/sup] (k<382*10[sup]12[/sup])
11213 (C) No factor 2*k*p[sup]2[/sup]+1 < 2[sup]77[/sup] (k<601*10[sup]12[/sup])
19937 (U) No factor 2*k*p[sup]2[/sup]+1 < 2[sup]78[/sup] (k<380*10[sup]12[/sup])
21701 33907204873,153745627424471
23209 17206738756236217
44497 (U) No factor 2*k*p[sup]2[/sup]+1 < 2[sup]81[/sup] (k<610*10[sup]12[/sup])
86243 (U) No factor 2*k*p[sup]2[/sup]+1 < 2[sup]75.9[/sup] (k<5*10[sup]12[/sup])
110503 250836575030879,22513968547647823
132049 No factor 2*k*p[sup]2[/sup]+1 < 2[sup]77.2[/sup] (k<5*10[sup]12[/sup])
216091 No factor 2*k*p[sup]2[/sup]+1 < 2[sup]78.6[/sup] (k<5*10[sup]12[/sup])
756839 696531210655937,63659341689518360417
859433 17727001955737,667717073666057
1257787 No factor 2*k*p[sup]2[/sup]+1 < 2[sup]83.7[/sup] (k<5*10[sup]12[/sup])
1398269 34207412811532057
2976221 No factor 2*k*p[sup]2[/sup]+1 < 2[sup]86.1[/sup] (k<5*10[sup]12[/sup])
3021377 2329356963700884673
6972593 No factor 2*k*p[sup]2[/sup]+1 < 2[sup]88.6[/sup] (k<5*10[sup]12[/sup])
13466917 No factor 2*k*p[sup]2[/sup]+1 < 2[sup]90.5[/sup] (k<5*10[sup]12[/sup])
20996011 899298254940726841
24036583 5274651651287933470393
25964951 20225360412972031
30402457 No factor 2*k*p[sup]2[/sup]+1 < 2[sup]92.9[/sup] (k<5*10[sup]12[/sup])
32582657 3322246487577398706217
37156667 71776963464264825905447
42643801 901972906808890097
43112609 No factor 2*k*p[sup]2[/sup]+1 < 2[sup]93.9[/sup] (k<5*10[sup]12[/sup])
57885161 No factor 2*k*p[sup]2[/sup]+1 < 2[sup]95.4[/sup] (k<5*10[sup]12[/sup])
74207281 508014103943653104553301983
[/CODE]

Great
 

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 [URL="https://oeis.org/A085724"]A085724[/URL] (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:

[CODE]
2281 Composite; no factor 2*k*p[sup]2[/sup]+1 < 2[sup]73[/sup] (k<907*10[sup]12[/sup])
[/CODE]

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

[QUOTE=JeppeSN;424395]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).[/QUOTE]

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:

[CODE]
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)
[/CODE]/JeppeSN

With a small code patch (like the one [URL="http://mersenneforum.org/showthread.php?p=402320#post402320"]described earlier[/URL]), we can use AVX or FMA3 FFT length [B]288K[/B] 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:
[CODE]*** 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);
[/CODE]and the worktodo.txt file
[CODE][Worker #1]
PRP=1,2,5202961,-1,"1"[/CODE]

I can run these guys at a leisurely pace
[CODE]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 :-)
[COLOR="Gray"]9941 No factor 2*k*p2+1 < 276 (k<382*1012)
11213 No factor 2*k*p2+1 < 277 (k<601*1012)[/COLOR]
...even though someone like David 'Squirrels' Stanfill just might![/CODE]

[CODE][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 [COLOR=Blue]5376K[/COLOR], 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: [COLOR=Blue]60:41:25[/COLOR]
[/CODE]That's not bad for a "M98823481" candidate size! I am going to run these last two, too.