mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2019-05-07, 16:44   #12
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

19·173 Posts
Default

Quote:
Originally Posted by henryzz View Post
Carmichael numbers are too easy. What is the largest non-Carmichael number that is known to be b-prp?
2^(2^82589933-1)-1 is 2-PRP
paulunderwood is online now   Reply With Quote
Old 2019-05-07, 19:01   #13
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT)

13·19·23 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
2^(2^82589933-1)-1 is 2-PRP
And non-trivial
henryzz is offline   Reply With Quote
Old 2019-05-07, 19:25   #14
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

63278 Posts
Default

Quote:
Originally Posted by henryzz View Post
And non-trivial
A little more on the subject... A proof that there are infinitely many pseudoprimes base a
paulunderwood is online now   Reply With Quote
Old 2019-05-09, 07:54   #15
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

2×5×859 Posts
Default

Quote:
Originally Posted by ATH View Post
There are no composite 3-PRP of the form 2n-1 for all n<100,000 (including composite n).
And there may be none at all. Something similar to Pepin test for Fermats may go also for Mersennes, but this is still an open question (as opposite to a "conjecture", where we can "guess" or "heuristically prove" one way or the other, here we have no clue). My belief is that a mersenne number which is 3-PRP is also prime, and this also applies to mersenne factors, if we restrict the exponent to be prime. But of course, I have no clue how could we prove that. This falls in the same category as the infinitude of Wieferich primes, or the mersenne numbers with prime exponents being square free - we have no guess, in either direction.

Last fiddled with by LaurV on 2019-05-09 at 07:58
LaurV is offline   Reply With Quote
Old 2019-05-09, 15:35   #16
chris2be8
 
chris2be8's Avatar
 
Sep 2009

432 Posts
Default

Has anyone checked for a Mersenne number that's a Lucas pseudoprime? Any such would also be a BPSW pseudoprime which would be an interesting discovery. Or can it be proved there are none such?

Chris
chris2be8 is offline   Reply With Quote
Old 2019-05-09, 16:01   #17
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

2·3·547 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
Quote:
Originally Posted by henryzz View Post
Carmichael numbers are too easy. What is the largest non-Carmichael number that is known to be b-prp?
2^(2^82589933-1)-1 is 2-PRP
How do you know it isn't a Carmichael number?
Dr Sardonicus is offline   Reply With Quote
Old 2019-05-10, 00:19   #18
JeppeSN
 
"Jeppe"
Jan 2016
Denmark

1768 Posts
Cool

Quote:
Originally Posted by LaurV View Post
My belief is that a mersenne number which is 3-PRP is also prime, and this also applies to mersenne factors, if we restrict the exponent to be prime.
239 is a prime. The Mersenne number 2^239-1 has as a factor the number 10974881. That number, 10974881, is really a 3-PRP. So by your belief, 10974881 should be a prime.

But as you may have guessed, 10974881 is not a 5-PRP. In fact:

10974881 = 1913 * 5737

Can someone come up with a conjecture on the number of counterexamples of this type?

/JeppeSN
JeppeSN is online now   Reply With Quote
Old 2019-05-10, 01:01   #19
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Out of my Body

31×59 Posts
Default

Quote:
Largest fake prime number holds 300 billion digits
A 300-billion-digit number is the biggest known pseudoprime
...
To hunt out the fakes, Shallue and colleague Steven Hayman created an algorithm that looks at a list of numbers to find a subset that, when multiplied together, produces a particular target – in this case, a pseudoprime that passes Fermat’s test.
https://www.newscientist.com/article...illion-digits/
a1call is offline   Reply With Quote
Old 2019-05-10, 03:42   #20
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

2·5·859 Posts
Default

Quote:
Originally Posted by JeppeSN View Post
239 is a prime. The Mersenne number 2^239-1 has as a factor the number 10974881. That number, 10974881, is really a 3-PRP
Whoops...
Never managed to do any tests, it was some small light blinking in a corner of my mind, and bothering me regularly from time to time, but I never invested the time to check.
Now I am very glad you found that! It settles the blinking light... hehe
It is a pity that in this case we still can't declare the "probable fully factored" mersennes that GP2 (and others) are putting a lot of effort into, to be "fully factored for sure" ...

Last fiddled with by LaurV on 2019-05-10 at 03:48 Reason: spaces
LaurV is offline   Reply With Quote
Old 2019-05-10, 04:39   #21
GP2
 
GP2's Avatar
 
Sep 2003

A1316 Posts
Default

Quote:
Originally Posted by LaurV View Post
It is a pity that in this case we still can't declare the "probable fully factored" mersennes that GP2 (and others) are putting a lot of effort into, to be "fully factored for sure" ...
But we test the cofactor to multiple bases, and then Paul Underwood tests for Lucas PRP. So it's not "for sure", but a lot more than just 3-PRP.

Edit: actually, FactorDB only stores PRPs for Mersenne cofactors for exponents up to about 500k. So for the larger ones, there is no record of testing them to any base other than 3. You could do it with PFGW. In any case Paul Underwood posts his Lucas PRP results to the "disbelievers" thread.

Last fiddled with by GP2 on 2019-05-10 at 04:49
GP2 is offline   Reply With Quote
Old 2019-05-10, 05:09   #22
JeppeSN
 
"Jeppe"
Jan 2016
Denmark

2·32·7 Posts
Smile

Quote:
Originally Posted by LaurV View Post
Whoops...
If you let n run through all odd composite 3-PRP, and test if znoroder(Mod(2, n)) is a prime, you get the counterexamples in a sorted way. The sequence goes:

10974881, 193949641, 717653129, 8762386393

I am considering submitting it to OEIS.

/JeppeSN
JeppeSN is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Composite being Prime kruoli FactorDB 5 2018-02-16 16:54
S_N cycles in LL done on composite M(p) tichy Math 1 2010-12-23 16:47
The composite conjecture Carl Fischbach Miscellaneous Math 8 2010-07-02 08:03
Composite checkerboard Kees Puzzles 14 2007-11-20 15:16
F10,21=10^(2^21)+1 is composite Shaopu Lin Factoring 2 2004-10-31 13:48

All times are UTC. The time now is 21:05.

Tue Jul 14 21:05:08 UTC 2020 up 111 days, 18:38, 0 users, load averages: 2.84, 2.24, 2.01

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.