mersenneforum.org > Math Composite PRP
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

2019-05-07, 16:44   #12
paulunderwood

Sep 2002
Database er0rr

425210 Posts

Quote:
 Originally Posted by henryzz 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

2019-05-07, 19:01   #13
henryzz
Just call me Henry

"David"
Sep 2007
Liverpool (GMT/BST)

23×7×107 Posts

Quote:
 Originally Posted by paulunderwood 2^(2^82589933-1)-1 is 2-PRP
And non-trivial

2019-05-07, 19:25   #14
paulunderwood

Sep 2002
Database er0rr

22×1,063 Posts

Quote:
 Originally Posted by henryzz And non-trivial
A little more on the subject... A proof that there are infinitely many pseudoprimes base a

2019-05-09, 07:54   #15
LaurV
Romulan Interpreter

"name field"
Jun 2011
Thailand

3·47·71 Posts

Quote:
 Originally Posted by ATH 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

 2019-05-09, 15:35 #16 chris2be8     Sep 2009 26×37 Posts 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
2019-05-09, 16:01   #17
Dr Sardonicus

Feb 2017
Nowhere

23·11·67 Posts

Quote:
Originally Posted by paulunderwood
Quote:
 Originally Posted by henryzz 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?

2019-05-10, 00:19   #18
JeppeSN

"Jeppe"
Jan 2016
Denmark

B416 Posts

Quote:
 Originally Posted by LaurV 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

2019-05-10, 01:01   #19
a1call

"Rashid Naimi"
Oct 2015
Remote to Here/There

1000110110102 Posts

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/

2019-05-10, 03:42   #20
LaurV
Romulan Interpreter

"name field"
Jun 2011
Thailand

3·47·71 Posts

Quote:
 Originally Posted by JeppeSN 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

2019-05-10, 04:39   #21
GP2

Sep 2003

13×199 Posts

Quote:
 Originally Posted by LaurV 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

2019-05-10, 05:09   #22
JeppeSN

"Jeppe"
Jan 2016
Denmark

22×32×5 Posts

Quote:
 Originally Posted by LaurV 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

 Similar Threads Thread Thread Starter Forum Replies Last Post kruoli FactorDB 5 2018-02-16 16:54 tichy Math 1 2010-12-23 16:47 Carl Fischbach Miscellaneous Math 8 2010-07-02 08:03 Kees Puzzles 14 2007-11-20 15:16 Shaopu Lin Factoring 2 2004-10-31 13:48

All times are UTC. The time now is 01:09.

Sat Aug 13 01:09:57 UTC 2022 up 36 days, 19:57, 2 users, load averages: 0.65, 0.99, 1.10

Copyright ©2000 - 2022, 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.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔