Mersenne Semiprimes
 

A web search on the topic turns up very little. One author calls them [url=http://www.associatedcontent.com/article/685897/what_are_cole_semiprimes.html?cat=72]Cole Semiprimes[/url] but I see no indication that this term has been adopted generally.

It is easy to see that if M(N) is semiprime, then N is prime or N=q^2 where M(q) is a Mersenne prime. For if a > b >=2 then M(ab) is divisible by both M(a) and M(b) and is greater than their product.

The [url=http://oeis.org/A135978]sequence with prime N[/url], i.e., [url=http://oeis.org/A085724]this sequence[/url] with squares removed, is, as expected, quite a bit denser than the familiar sequence of exponents of Mersenne Primes. I don't know if any more are known.

Semiprime Mersennes with N=q^2 are rare. Only three are known, corresponding to q=2, q=3, and q=7. I have verified that M(q^2)/M(q) is composite for all other exponents of Mersenne primes up to and including q=521. In the latter case, trial factoring discovered that 8143231 was a factor of the 81556 digit quotient. Would anyone be interested in trying to extend this list?

[QUOTE=Mr. P-1;238807]

Semiprime Mersennes with N=q^2 are rare. Only three are known, corresponding to q=2, q=3, and q=7. I have verified that M(q^2)/M(q) is composite for all other exponents of Mersenne primes up to and including q=521. [/QUOTE]

Based upon rough probability estimates, we should expect there to be
only finitely many.

~"mersenne semiprimes" returns all OEIS results.
[url]oeis.org/A102029[/url]
[url]www.research.att.com/~njas/sequences/A102029[/url]
[url]www.research.att.com/~njas/sequences/A092561[/url]

[QUOTE=R.D. Silverman;238813]Based upon rough probability estimates, we should expect there to be
only finitely many.[/QUOTE]

If we ask whether [url=http://oeis.org/A156585]M(q^2)/M(q) is prime for arbitrary q[/url] (necessarily prime, but not necessarily the exponent of a Mersenne prime), only one more is known. There should be a lot fewer of these than Mersenne primes, simply because the exponent is squared. How much fewer? By reasoning similar to Wagstaff's heuristic, I would estimate the probability that M(q^2)/M(q) is prime for random prime q to be about A/((q^2 - q)log(2)), where A is a number that takes into account all the prime numbers that cannot be divisors (among them, the myriad algebraic factors of M(q^2)/(M(q) -1 as well as q itself.) This -- and here's where things get a bit handwavy -- looks a bit like A/(q^2), which series converges. So I think only finitely many of these should be prime.

M(q^2) is a semiprime precisely at the intersection between this set of exponents (conjecturaly finite) and those of Mersenne primes (conjecturally infinite, but increasingly sparse). So I agree with your remark. These should be not only be a finite number of them, but a small finite number at that: probably the three we know about and no more.

[QUOTE=Mr. P-1;238807]Semiprime Mersennes with N=q^2 are rare. Only three are known, corresponding to q=2, q=3, and q=7. I have verified that M(q^2)/M(q) is composite for all other exponents of Mersenne primes up to and including q=521. In the latter case, trial factoring discovered that 8143231 was a factor of the 81556 digit quotient. Would anyone be interested in trying to extend this list?[/QUOTE]

I continued factoring with my own c-program with GMP and with mfaktc 1.13 for p<=44497. Currently 15 exponents of the 47 mersenne prime exponents are missing a factor:

[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 No factor 2*k*p[sup]2[/sup]+1 < 2[sup]70[/sup]
3217 102559471991
4253 1844976919,57592220657
4423 No factor 2*k*p[sup]2[/sup]+1 < 2[sup]70[/sup]
9689 76729816024661281759
9941 No factor 2*k*p[sup]2[/sup]+1 < 2[sup]72[/sup]
11213 No factor 2*k*p[sup]2[/sup]+1 < 2[sup]73[/sup]
19937 No factor 2*k*p[sup]2[/sup]+1 < 2[sup]74[/sup]
21701 33907204873,153745627424471
23209 17206738756236217
44497 No factor 2*k*p[sup]2[/sup]+1 < 2[sup]77[/sup]
86243 No factor 2*k*p[sup]2[/sup]+1 < 2[sup]71.5[/sup] (k<230*10[sup]9[/sup])
110503 250836575030879,22513968547647823
132049 No factor 2*k*p[sup]2[/sup]+1 < 2[sup]72.7[/sup] (k<230*10[sup]9[/sup])
216091 No factor 2*k*p[sup]2[/sup]+1 < 2[sup]74.1[/sup] (k<230*10[sup]9[/sup])
756839 696531210655937,63659341689518360417
859433 17727001955737,667717073666057
1257787 No factor 2*k*p[sup]2[/sup]+1 < 2[sup]79.2[/sup] (k<230*10[sup]9[/sup])
1398269 34207412811532057
2976221 No factor 2*k*p[sup]2[/sup]+1 < 2[sup]81.7[/sup] (k<230*10[sup]9[/sup])
3021377 2329356963700884673
6972593 No factor 2*k*p[sup]2[/sup]+1 < 2[sup]84.2[/sup] (k<230*10[sup]9[/sup])
13466917 No factor 2*k*p[sup]2[/sup]+1 < 2[sup]86.1[/sup] (k<230*10[sup]9[/sup])
20996011 899298254940726841
24036583 5274651651287933470393
25964951 20225360412972031
30402457 No factor 2*k*p[sup]2[/sup]+1 < 2[sup]88.4[/sup] (k<230*10[sup]9[/sup])
32582657 3322246487577398706217
37156667 71776963464264825905447
42643801 901972906808890097
43112609 No factor 2*k*p[sup]2[/sup]+1 < 2[sup]89.4[/sup] (k<230*10[sup]9[/sup])
[/CODE]

Be sure to forward your factors to Will Edgington. I checked a handful and did not find them in Will's tables.

[QUOTE=ATH;241699]I continued factoring with my own c-program with GMP and with mfaktc 1.13 for p<=44497. Currently 15 exponents of the 47 mersenne prime exponents are missing a factor:[/QUOTE]

Thanks for doing this work.

[QUOTE]521 ...10857641...[/QUOTE]

Ha! I only went up to 10 Million. Would have gone further if I hadn't already found the smaller factor.

[QUOTE]2281 No factor 2*k*p[sup]2[/sup]+1 < 2[sup]70[/sup][/QUOTE]

At 1,565,561 digits, P-1, ECM, and failing those, PRP ought to be feasible on this one.

[QUOTE]43112609 No factor 2*k*p[sup]2[/sup]+1 < 2[sup]89.4[/sup] (k<230*10[sup]9[/sup])[/QUOTE]

At 559,523,553,364,961 digits this one is probably infeasible.

[QUOTE=Mr. P-1;241742]Thanks for doing this work.



Ha! I only went up to 10 Million. Would have gone further if I hadn't already found the smaller factor.



At 1,565,561 digits, P-1, ECM, and failing those, PRP ought to be feasible on this one.



At 559,523,553,364,961 digits this one is probably infeasible.[/QUOTE]

Is there some point to all this?

[QUOTE=R.D. Silverman;241766]Is there some point to all this?[/QUOTE]Yes, clearly, or it would not have been done.

Perhaps the point is to gain enjoyment from pursuing an activity from which you would not have gained any such reward.

Paul

[QUOTE=xilman;241769]Yes, clearly, or it would not have been done.

Perhaps the point is to gain enjoyment from pursuing an activity from which you would not have gained any such reward.

Paul[/QUOTE]

I too indulge in mental masturbation from time to time. I enjoy it.

But I don't do it in public.

One way that I measure what I do by whether it is useful to others.

This fascination with "semi-primes" just seems like a fetish to me.

[QUOTE=R.D. Silverman;241776]I too indulge in mental masturbation from time to time. I enjoy it.

But I don't do it in public.

One way that I measure what I do by whether it is useful to others.

This fascination with "semi-primes" just seems like a fetish to me.[/QUOTE]Sometimes others have the same "fetishes" as us and it is nice to share. So I guess the point here is:

Poster A has something he enjoys doing and posts it.
Poster B also enjoys it and shares back.

Why should that be wrong?

[QUOTE=R.D. Silverman;241766]Is there some point to all this?[/QUOTE]

I saw this problem Mr. P-1 asked about and thought it sounded interesting. I had fun making my little program and optimizing it, and at the same time I also learned how to use mfaktc on composite exponents. It also looked like I was alone working on it, so it gave a sense of "discovery" because no one else had ever checked which of these M(p^2) might be semi prime, compared to just being 1 among many like in GIMPS and many other projects.

I'm continuing factoring those 15 remaining numbers a bit more.

[QUOTE=ATH;241781]so it gave a sense of "discovery" because no one else had ever checked which of these M(p^2) might be semi prime.[/QUOTE]

You might want to consider the reason why noone else had done it before...

[QUOTE=R.D. Silverman;241785]You might want to consider the reason why noone else had done it before...[/QUOTE]

To paraphrase one of my favorite physicists: "Why should he care what anyone else thinks?"

He derives enjoyment from what he's doing, he's not hurting anyone, and in fact is learning something from what he's doing. I don't understand why we're even having this conversation.

[QUOTE=bsquared;241786]To paraphrase one of my favorite physicists: "Why should he care what anyone else thinks?"

He derives enjoyment from what he's doing, he's not hurting anyone, and in fact is learning something from what he's doing. I don't understand why we're even having this conversation.[/QUOTE]

He doesn't have to care. But if he is going to present ideas in public,
then he can expect feedback from others. One such feedback might
be what I have presented, i.e. "this isn't useful". The OP is, of course,
entitled to ignore said opinion.

Consider the subforum. This is mathematics. I don't see any math.
I do see numerology and mindless computing.

Why is it that noone ever seems to say/ask: "I am new. What would be a
good project to work on?". Instead, people seem to latch onto meaningless
number crunching that really isn't useful. Mental masturbation should be
kept private.

I never suggested that he is not entitled to present his "ideas". But just as
he is free to post numerology, I am free to say "This isn't useful; try something else"

Allow me to quote again: "The purpose of computing is insight, not numbers".

[QUOTE=R.D. Silverman;241789]Allow me to quote again: "The purpose of computing is insight, not numbers".[/QUOTE]

Absolutely.

[QUOTE=R.D. Silverman;241789]Instead, people seem to latch onto meaningless
number crunching that really isn't useful. Mental masturbation should be
kept private.[/QUOTE]

Unless it's the Cunningham project, right?

[QUOTE=CRGreathouse;241794]Absolutely.



Unless it's the Cunningham project, right?[/QUOTE]

[i]As I have said before[/i], I [b]agree[/b] with Oliver Atkin.
The Cunningham project, by itself, is just a stamp collection.

The purpose of the Cunningham project is not to factor certain numbers, but
rather to provide a collection of related numbers (they do have some
historical background) that serve as a useful benchmark for pushing the
state of the art in factoring algorithms. And the factorizations are (rarely, I
would agree) sometimes useful.

Factoring Cunningham numbers does not solve any open mathematical
problems. OTOH, There are projects that [b]are[/b] working on open
problems. e.g. 17 or Bust, the Euler project etc.

I'd like to complete the first edition of the Cunningham book (all that
remains is the current base 2 tables) because I promised Dick Lehmer
that I would push toward finishing them. This is a [i]realizable[/i]
goal. The topic that started this thread is [i]not[/i] a realizable goal.

[QUOTE=R.D. Silverman;241800][i]As I have said before[/i], I [b]agree[/b] with Oliver Atkin.
The Cunningham project, by itself, is just a stamp collection.

The purpose of the Cunningham project is not to factor certain numbers, but
rather to provide a collection of related numbers (they do have some
historical background) that serve as a useful benchmark for pushing the
state of the art in factoring algorithms. And the factorizations are (rarely, I
would agree) sometimes useful.[/QUOTE]

I feel the same way.

[QUOTE=R.D. Silverman;241789]Consider the subforum. This is mathematics. I don't see any math. I do see numerology and mindless computing.

Why is it that noone ever seems to say/ask: "I am new. What would be a
good project to work on?". Instead, people seem to latch onto meaningless
number crunching that really isn't useful. Mental masturbation should be
kept private.[/QUOTE]

Most people round these parts seem to think that the search for Mersenne primes is a good project to work on. That too is numerology and mindless computing for the vast majority of participants.

You're entitled to your view that it should be kept private, of course. Expressing that view in the Mersenne mental masturbators' forum would appear to be..., well, pointless.

[QUOTE=R.D. Silverman;241800][i]As I have said before[/i], I [b]agree[/b] with Oliver Atkin.
The Cunningham project, by itself, is just a stamp collection.

The purpose of the Cunningham project is not to factor certain numbers, but
rather to provide a collection of related numbers (they do have some
historical background) that serve as a useful benchmark for pushing the
state of the art in factoring algorithms.[/QUOTE]

I am at a loss to understand how [URL=http://www.mersenneforum.org/showpost.php?p=240711&postcount=61]soliciting contributions of mindless computation from random passers by[/URL] will in any way contribute to pushing the state of the art in factoring algorithms.

On the other hand, I do see how it would help you complete your stamp collection.

[QUOTE]I'd like to complete the first edition of the Cunningham book (all that
remains is the current base 2 tables) because I promised Dick Lehmer
that I would push toward finishing them.[/QUOTE]

That you made a promise to another person to mentally masturbate on his behalf is probably something to be kept private.

[QUOTE]This is a [i]realizable[/i]
goal. The topic that started this thread is [i]not[/i] a realizable goal.[/QUOTE]

Completing the first edition of the Cunningham book was not foreseeably a realizable goal in 1925 when that book was published. Who knows what will be realizable in eighty-five years from now?

[QUOTE=Mr. P-1;241903]

I am at a loss to understand how soliciting contributions of mindless computation from random passers by will in any way contribute to pushing the state of the art in factoring algorithms.
[/QUOTE]

That is how the community learns to select the parameters for larger
numbers. It is how we learn to tune our code. It is how we learn
whether algorithms match theoretical predictions for their
performance. By actually DOING.

Individuals do not have enough CPUs to do the work, so outside
help is solicited.

Getting back to the pointless computations instead of discussing their pointlessness, at [url]http://donovanjohnson.com/mersenne.html[/url] I think I found the 5 largest known probable Mersenne semiprimes :
M(684127) = 23765203727 * prp205933
M(406583) = 813167 * prp122388
M(271549) = 238749682487 * prp81734
M(271211) = 613961495159 * prp81631
M(221509) = 292391881 * prp66673

The largest proven Mersenne semiprime at [url]http://primes.utm.edu/top20/page.php?id=49[/url] is:
M(17029) = 418879343 * p5118

[QUOTE=R.D. Silverman;241766]Is there some point to all this?[/QUOTE]The learning process you went through (particularly compact because of your natural ability and circumstances) before the Internet is being played out on the Web in public now, which was never before possible. Had it been, one would have seen a similar mix of folks' learning levels exhibited on that earlier Web then, I'm fairly sure.

[QUOTE=R.D. Silverman;241785]You might want to consider the reason why noone else had done it before...[/QUOTE]

I thought "no one" was always two words...

why
 

[QUOTE=NBtarheel_33;242401]I thought "no one" was always two words...[/QUOTE]

why

all attacked, you write "separate"
separate, you write "all attacked"

[QUOTE=NBtarheel_33;242401]I thought "no one" was always two words...[/QUOTE]

Linguistically, it's one word. It's not surprising to me that conventions increasingly support this spelling (though it's still nonstandard at the moment).

A certain person in this forum posted the following line earlier
in this thread:

[quote]You might want to consider the reason why no one else had done it before...
[/quote]in response to another posters explanation of his motivations.

We are GIMPS supporters, not RDSers.

P95 is a great program, but math rules.

Always be skeptical to any news

For more info on why semi-primes are relevant to our search
for Mersennes, see the thread Mersenne-Like in the Puzzles subforum.

Link is: [URL="http://www.mersenneforum.org/showthread.php?t=11418"]Mersenne-Like[/URL]

The list there could be extended.

I trialfactored the last 15 exponent with no factors a bit further but with no luck. I'm stopping for now:


[CODE]
p Factor(s) of M(p[sup]2[/sup])/M(p)
--------------------------------------------------
2281 No factor 2*k*p[sup]2[/sup]+1 < 2[sup]71[/sup] (k<226*10[sup]12[/sup])
4423 No factor 2*k*p[sup]2[/sup]+1 < 2[sup]73[/sup] (k<241*10[sup]12[/sup])
9941 No factor 2*k*p[sup]2[/sup]+1 < 2[sup]75[/sup] (k<191*10[sup]12[/sup])
11213 No factor 2*k*p[sup]2[/sup]+1 < 2[sup]76[/sup] (k<300*10[sup]12[/sup])
19937 No factor 2*k*p[sup]2[/sup]+1 < 2[sup]77[/sup] (k<190*10[sup]12[/sup])
44497 No factor 2*k*p[sup]2[/sup]+1 < 2[sup]80[/sup] (k<305*10[sup]12[/sup])
86243 No factor 2*k*p[sup]2[/sup]+1 < 2[sup]73.7[/sup] (k<1.1*10[sup]12[/sup])
132049 No factor 2*k*p[sup]2[/sup]+1 < 2[sup]75.0[/sup] (k<1.1*10[sup]12[/sup])
216091 No factor 2*k*p[sup]2[/sup]+1 < 2[sup]76.4[/sup] (k<1.1*10[sup]12[/sup])
1257787 No factor 2*k*p[sup]2[/sup]+1 < 2[sup]81.5[/sup] (k<1.1*10[sup]12[/sup])
2976221 No factor 2*k*p[sup]2[/sup]+1 < 2[sup]84.0[/sup] (k<1.1*10[sup]12[/sup])
6972593 No factor 2*k*p[sup]2[/sup]+1 < 2[sup]86.4[/sup] (k<1.1*10[sup]12[/sup])
13466917 No factor 2*k*p[sup]2[/sup]+1 < 2[sup]88.3[/sup] (k<1.1*10[sup]12[/sup])
30402457 No factor 2*k*p[sup]2[/sup]+1 < 2[sup]90.7[/sup] (k<1.1*10[sup]12[/sup])
43112609 No factor 2*k*p[sup]2[/sup]+1 < 2[sup]91.7[/sup] (k<1.1*10[sup]12[/sup])
[/CODE]

Thanks for your efforts.

axn's recent discovery from another thread:

[QUOTE=axn;385016]There is something to be said for dumb luck.
[CODE]M3464473/604874508299177 is a probable prime! We4: E866B6FC,00000000
[/CODE]Still need to do some (slow) independent check with PFGW. Ugh!

EDIT:- Anybody know how to make P95 use a different base to do the PRP test?[/QUOTE]

[QUOTE=alpertron;385025]That's the first Mega-PRP cofactor of a Mersenne number known. Congratulations.[/QUOTE]

Presumably this makes M3464473 the largest known "probable Mersenne semiprime" too, if that is the correct expression?

On a general point, can anyone say what is currently conjectured about the frequency of occurrence of Mersenne semiprimes? Would we expect them to occur with similar order of frequency to that of Mersenne primes? I note RDS' statement in post #2 of this thread that Mersenne semiprimes with exponent the square of the exponent of a Mersenne Prime would be expected to be finite in number, but what about those Mersenne semiprimes with prime exponent?

[QUOTE=Brian-E;385074]
On a general point, can anyone say what is currently conjectured about the frequency of occurrence of Mersenne semiprimes? Would we expect them to occur with similar order of frequency to that of Mersenne primes?
[/QUOTE]

No. A full explanation may be found in Hardy & Wright. We expect them
to occur with the same frequency (up to a small constant necessitated by the form of the numbers) as all other integers with exactly two prime factors.
[QUOTE]

but what about those Mersenne semiprimes with prime exponent?[/QUOTE]

What about them? See Hardy & Wright. Do you expect numbers with exactly two prime factors to be fewer than primes?

[QUOTE=Brian-E;385074]
Presumably this makes M3464473 the largest known "probable Mersenne semiprime" too, if that is the correct expression?[/QUOTE]
You can find at [url]http://www.mersenne.ca/prp.php[/url] the current list of "probably completely factored Mersenne numbers".

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.

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

Is a similar patch also appliable to double Mersenne factors?

[QUOTE=ET_;425067]Is a similar patch also applicable to double Mersenne factors?[/QUOTE]Double Mersenne factor checks already use the optimal (not general) FFT. It is exactly as if it were a 2-PRP test which is cut short (less iterations: 2^p-1 instead of 2*k*(2^p-1)+1).

When we use gwnum-based tools to run ECM, P-1 or PRP on a (k,b,n,c) number [I]divided[/I] by some reasonably small value e (which is provided in "..." field), then all calculations can be done with special mod on (k,b,n,c) basis. Only the last step requires general mod N and then we have the final residue.

In contrast, when we are considering a (k,b,n,c) number divided by something large, then all gwnum based tools by default prepare the N value and then treat it as a general number - which leads to ~2 times larger zero-padded FFT size and using general mod step. So, that's ~2x slower due to FFT size and additional ~2x slower due to general mod. The patch ad hoc reduces this situation to the one above.

[QUOTE=Batalov;425124] (less iterations: 2^p-1 instead of 2*k*(2^p-1)+1).[/QUOTE]
Sloppy phrasing there. What I meant was of course log[SUB]2[/SUB](2^p-1), or simply p steps, instead of log[SUB]2[/SUB](2*k*(2^p-1)+1) steps with an appropriate bit pattern from N.
For the D-Mers divisibility it is easier to use exponentiation of Mod(2, k*2[SUP]p+1[/SUP]-(2*k-1)) to [B]2^p[/B] (no need to mult-by-2 it each iteration) and compare the result to 2.

[QUOTE=Batalov;425039][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.[/QUOTE]

Serge, that is great. You are going to gain instant fame if $\Phi_{p^2}(2) = M_{p^2}/M_p$ is prime for either $p=9941$ or $p=11213$ :exclaim: /JeppeSN

He can at most find a very large PRP. It doesn't seem to me like a real primality test. And he is already famous! (Respect! :bow:)

Yeah, a large PRP is nice (with almost negligible probability though) ...but a large prime that I'd really like to find would be a b[SUP]2[SUP]n+1[/SUP][/SUP] - b[SUP]2[SUP]n[/SUP][/SUP] +1 which is provable. Or any other Phi(3[SUP]n[/SUP]*2[SUP]m[/SUP], b) (a bundle of 3's still leads to a B^2 - B + 1 form -- which is {evidently from its appearance} provable by N-1 method with 150% proof), known as [URL="http://www.linuxjournal.com/article/8096"]P.I.E.S. primes[/URL].

Phi(K[SUP]n[/SUP]*2[SUP]m[/SUP], b), even if found, would also remain a PRP (with K>=5). Same with any other higher cyclotomic.

[QUOTE=Batalov;425160]Phi(K[SUP]n[/SUP]*2[SUP]m[/SUP], b), even if found, would also remain a PRP (with K>=5). Same with any other higher cyclotomic.[/QUOTE]

Isn't it possible to do a CHG proof for K=5, since you get 25% factorization of N-1 for free (plus algebraic factors of the remainder from which some ECM factorizations might also be obtainable)?

Small ones could be proven but not the 388340+ digit numbers (the UTM cutoff).
Even to get to 26% we need another 3883 digits of factors, but a 26% proof would be nearly impossible at that size. (I did do a [URL="http://primes.utm.edu/primes/page.php?id=118734"]29.08% proof[/URL] once ...at that size. I couldn't believe my eyes when the first step of the proof came through overnight. I think a high 28-ish% proof could work -- but that's more than 10000 digits of extra factors to collect, almost impossible.)

[QUOTE=Batalov;425016]
Here is the modified patch:[/QUOTE]

Patch added to prime95 source code. You'll need to put "PhiExtensions=1" in prime.txt.

I'll clean it up some more.
Now that I've used it in action for a while, I noticed that divg() might be not the best way to do it (even though simple to write); it uses quite a bit of RAM which many users might not have. For M98823481/M9941, >55G is used at peak. Then the memory use wanes down for the rest of the run, so I gather that this is the initial divg(). Instead I can code the summation of (-b)[SUP]kq[/SUP], k=0..p-1.

Also, of course, it is only for b=2, for two reasons: a) the array of known M-primes should not be used, and b) the denominator must be itself divided by (b-1) for the second division.

[CODE][Work thread Feb 6 00:44]
[COLOR=Green]M98823481/"1" is not prime. RES64: 333069AAE77863BA. We8: 00000000,00000000[/COLOR]
...
[Work thread Feb 6 00:44]
Starting PRP test of M125731369/"1" using FMA3 FFT length 6720K, Pass1=896, Pass2=7680, 18 threads
[COLOR=DarkRed]Killed[/COLOR]
[/CODE]So, there, I precog'd the future out of memory death (the node has 64Gb); I did get lucky with divg() still fitting in memory for the previous candidate, but this one didn't fit. So, just in time to rewrite the code with summation; here, b=2, all terms with the plus sign, so I can code it easily from the small terms up. Ok, then...
EDIT: this patch-2.0 works much better:
[CODE] *N = allocgiant ((bits >> 5) + 5);
if (*N == NULL) return (OutOfMemory (thread_num));

[COLOR=Blue] if(w->k == 1.0 && w->b == 2 && w->c == -1) { /*=== this input means Phi(n,2) with n semiprime ===*/
int i,k,q, knownSmallMers[] = {3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217,
4253, 4423, 9689, 9941, 11213, 19937, 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) {
giant tmp = allocgiant ((bits >> 5) + 5);
if (!tmp) return (OutOfMemory (thread_num));
ultog (1, tmp);
ultog (1, *N);
gshiftleft (w->n-[/COLOR][COLOR=Blue][COLOR=Blue][COLOR=Blue]w->n/[/COLOR][/COLOR]q, *N);
for(k=2; k < q; k++) {
gshiftleft ([/COLOR][COLOR=Blue][COLOR=Blue]w->n/[/COLOR]q, tmp);
addg (tmp, *N);
}
iaddg (1, *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, "M%d", w->n/q); [/COLOR][COLOR=Blue][COLOR=Blue]if(q != w->n/q) [/COLOR][/COLOR][COLOR=Blue][COLOR=Blue][COLOR=Blue]p += sprintf(buf+p, "/M%d", q);
[/COLOR][/COLOR] w->known_factors = malloc(p+1);
memcpy(w->known_factors, buf, p+1);
}
return (0);
}
}[/COLOR]

ultog (w->b, *N);
[/CODE]

Well, no surprises here, it's composite:
[CODE]M125731369/"1" interim We8 residue EE9CB5973F87EBC5 at iteration 123000000
M125731369/"1" interim We8 residue ED1BBFF1E242A1AC at iteration 124000000
M125731369/"1" interim We8 residue FF77A5DC9D544CBD at iteration 125000000
[Wed Feb 10 22:50:05 2016]
M125731369/M11213 is not prime. RES64: 7B39D9067F3A3A06. We8: 00000000,00000000[/CODE]

Good to know for sure. Nice work making it possible to test them in a reasonable amount of time.

[QUOTE=Batalov;425395]
EDIT: this patch-2.0 works much better:[/QUOTE]

Attached is the updated ecm.c file. It includes this upgrade and another of your Phi changes.

Sieved M(77232917^2) / M(77232917) without finding a factor and sieved some of the lower ones some more without any new factors..


[CODE]p Factor(s) of M(p^2)/M(p) k in 2*k*p^2+1
----------------------------------------------------------------------------------------
2 [COLOR="Lime"]Prime[/COLOR]
3 [COLOR="Lime"]Prime[/COLOR]
5 601,1801 k=12,36
7 [COLOR="Lime"]Prime[/COLOR]
13 4057 k=12
17 12761663 k=22079
19 9522401530937 k=13188921788
31 280651416271709745866686729 k=146020507945738681512324
61 80730817,301780543,281646330073 k=10848,40551,37845516
89 29123869433,49849688719 k=1838396,3146679
107 1167799,377175857 k=51,16472
127 14806423,25044595073,72653532113 k=459,776384,2252264
521 8143231,10857641,4338170063 k=15,20,7991
607 345899921201,166969148315503 k=469400,226583799
1279 103097448872275370551 k=31512062869275
2203 15714690743 k=1619
2281 [COLOR="DeepSkyBlue"]Composite[/COLOR] (No factor 2*k*p^2+1 < 2^73) (k<90*10^13))
3217 102559471991 k=4955
4253 1844976919,57592220657 k=51,1592
4423 [COLOR="DeepSkyBlue"]Composite[/COLOR] (No factor 2*k*p^2+1 < 2^74) (k<48*10^13))
9689 76729816024661281759 k=408673285599
9941 [COLOR="DeepSkyBlue"]Composite[/COLOR] (No factor 2*k*p^2+1 < 2^76) (k<38*10^13))
11213 [COLOR="DeepSkyBlue"]Composite[/COLOR] (No factor 2*k*p^2+1 < 2^77) (k<60*10^13))
19937 [COLOR="Red"]Unknown[/COLOR] (No factor 2*k*p^2+1 < 2^78) (k<38*10^13))
21701 33907204873,153745627424471 k=36,163235
23209 17206738756236217 k=15971868
44497 [COLOR="Red"]Unknown[/COLOR] (No factor 2*k*p^2+1 < 2^81) (k<61*10^13))
86243 [COLOR="Red"]Unknown[/COLOR] (No factor 2*k*p^2+1 < 2^77.9) (k<2*10^13))
110503 250836575030879,22513968547647823 k=10271,921879
132049 [COLOR="Red"]Unknown[/COLOR] (No factor 2*k*p^2+1 < 2^79.2) (k<2*10^13))
216091 [COLOR="Red"]Unknown[/COLOR] (No factor 2*k*p^2+1 < 2^80.6) (k<2*10^13))
756839 696531210655937,63659341689518360417 k=1216,55568048
859433 17727001955737,667717073666057 k=12,452
1257787 [COLOR="Red"]Unknown[/COLOR] (No factor 2*k*p^2+1 < 2^85.7) (k<2*10^13))
1398269 34207412811532057 k=8748
2976221 [COLOR="Red"]Unknown[/COLOR] (No factor 2*k*p^2+1 < 2^88.1) (k<2*10^13))
3021377 2329356963700884673 k=127584
6972593 [COLOR="Red"]Unknown[/COLOR] (No factor 2*k*p^2+1 < 2^90.6) (k<2*10^13))
13466917 [COLOR="Red"]Unknown[/COLOR] (No factor 2*k*p^2+1 < 2^92.5) (k<2*10^13))
20996011 899298254940726841 k=1020
24036583 5274651651287933470393 k=4564764
25964951 20225360412972031 k=15
30402457 [COLOR="Red"]Unknown[/COLOR] (No factor 2*k*p^2+1 < 2^94.9) (k<2*10^13))
32582657 3322246487577398706217 k=1564692
37156667 71776963464264825905447 k=25994507
42643801 901972906808890097 k=248
43112609 [COLOR="Red"]Unknown[/COLOR] (No factor 2*k*p^2+1 < 2^95.9) (k<2*10^13))
57885161 [COLOR="Red"]Unknown[/COLOR] (No factor 2*k*p^2+1 < 2^96.7) (k<2*10^13))
74207281 508014103943653104553301983 k=46126737231
77232917 [COLOR="Red"]Unknown[/COLOR] (No factor 2*k*p^2+1 < 2^97.6) (k<2*10^13))
[/CODE]

the small ones (13, 17, 19) can be easily full factored (19^2-19=384-19 bits, about 100 digits)
[CODE]
gp > factorint(m2(p))
time = 647 ms.
[ 4057 1]
[ 6740339310641 1]
[3340762283952395329506327023033 1][/CODE]

[QUOTE=Jens K Andersen;242124]Getting back to the pointless computations instead of discussing their pointlessness, at [url]http://donovanjohnson.com/mersenne.html[/url] I think I found the 5 largest known probable Mersenne semiprimes :
M(684127) = 23765203727 * prp205933
M(406583) = 813167 * prp122388
M(271549) = 238749682487 * prp81734
M(271211) = 613961495159 * prp81631
M(221509) = 292391881 * prp66673

The largest proven Mersenne semiprime at [url]http://primes.utm.edu/top20/page.php?id=49[/url] is:
M(17029) = 418879343 * p5118[/QUOTE]

Updating the above post from 2010, which is about the boring kind:

The original list above is missing the entries:

M(611999) = 18464214225958267477777390354183 * prp184199
M(432457) = 1672739247834685086279697 * prp130159

Of course, every unfactored Mersenne number of prime exponent is potentially a semiprime, so more entries may be added at any time as new factors are found.


The largest known probable Mersenne semiprimes are:

M(7313983) = 305492080276193 * prp2201714
M(5240707) = 75392810903 * prp1577600
M(4187251) = 72234342371519 * prp1260475
M(3464473) = 604874508299177 * prp1042896
M(2327417) = 23915387348002001 * prp700606

The largest proven Mersenne semiprime is:

M(63703) = 42808417 * p19169

and the next semi-feasible candidate for Primo certification is:

M(86371) = 41681512921035887 * prp25984

[QUOTE=GP2;482974]Updating the above post from 2010, which is about the boring kind:

The original list above is missing the entries:

M(611999) = 18464214225958267477777390354183 * prp184199
M(432457) = 1672739247834685086279697 * prp130159

[/QUOTE]
These do not appear in that list because they were found after 2010. There are lots of Mersenne semiprimes, but the problem is to find the smallest prime factor.

PS. Maybe in the future someone will find an algorithm to quickly detect probable semiprimes. In [url]http://physics.open.ac.uk/~dbroadhu/cert/semgpch.gp[/url] you can find a 5061-digit proven semiprime, but the certificate does not need the prime factors.