Mersenne Semiprimes

Mr. P-1 · 2010-11-27, 00:40

A web search on the topic turns up very little. One author calls them Cole Semiprimes 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 sequence with prime N, i.e., this sequence 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?

R.D. Silverman · 2010-11-27, 01:13

Quote:

Originally Posted by Mr. P-1

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.

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

science_man_88 · 2010-11-27, 01:14

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

Mr. P-1 · 2010-11-27, 02:58

Quote:

Originally Posted by R.D. Silverman

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

If we ask whether M(q^2)/M(q) is prime for arbitrary q (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.

ATH · 2010-12-14, 00:28

Quote:

Originally Posted by Mr. P-1

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?

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

wblipp · 2010-12-14, 03:38

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

Mr. P-1 · 2010-12-14, 08:25

Quote:

Originally Posted by ATH

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:

Thanks for doing this work.

Quote:

521 ...10857641...

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²+1 < 2⁷⁰

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²+1 < 2^89.4 (k<230*10⁹)

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

R.D. Silverman · 2010-12-14, 12:33

Quote:

Originally Posted by Mr. P-1

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.

Is there some point to all this?

xilman · 2010-12-14, 12:45

Quote:

Originally Posted by R.D. Silverman

Is there some point to all this?

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

R.D. Silverman · 2010-12-14, 13:37

Quote:

Originally Posted by xilman

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

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.

retina · 2010-12-14, 13:44

Quote:

Originally Posted by R.D. Silverman

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.

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?

2010-11-27, 00:40	#1
Mr. P-1 Jun 2003 7×167 Posts	Mersenne Semiprimes A web search on the topic turns up very little. One author calls them Cole Semiprimes 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 sequence with prime N, i.e., this sequence 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? Last fiddled with by Mr. P-1 on 2010-11-27 at 00:49

2010-11-27, 01:14	#3
science_man_88 "Forget I exist" Jul 2009 Dartmouth NS 8,461 Posts	~"mersenne semiprimes" returns all OEIS results. oeis.org/A102029 www.research.att.com/~njas/sequences/A102029 www.research.att.com/~njas/sequences/A092561 Last fiddled with by science_man_88 on 2010-11-27 at 01:14

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Semiprimes factoring. Is deterministic? What is computational complexity?	Alberico Lepore	Alberico Lepore	43	2017-06-10 15:42
Smarandache semiprimes	sean	Factoring	15	2014-11-09 06:05
Semiprimes	Hian	Homework Help	15	2011-05-29 23:48
Factoring semiprimes	robert44444uk	Math	34	2007-07-19 17:23
Mersenne Wiki: Improving the mersenne primes web site by FOSS methods	optim	PrimeNet	13	2004-07-09 13:51

2010-12-14, 03:38	#6
wblipp "William" May 2003 Near Grandkid 5³×19 Posts	Be sure to forward your factors to Will Edgington. I checked a handful and did not find them in Will's tables.