PRPs that are composites

[Batalov]

A rather small composite 3-PRP:
20484176833 = 16261*108^3+1 is 3-PRP!
20484176833 = 84673 * 241921

already in the list

[Mr. P-1]

It was a while ago, but still...

Originally Posted by gd_barnes

Here's a question for the PRP/PSP gurus:

Is it possible to have a 3-PRP or "any" PRP for that matter that has more than 2 prime factors? Are there any examples?

Yes, the Carmichael numbers have at least 3 prime factors.

[Puzzle-Peter]

878519842*3^7-1 = 1,921,322,894,453  = 266,759*7,202,467     prime at n=64
885176830*3^5-1 =  215,097,969,689    = 101,207*2125,327     prime at n=6
830490286*3^6-1 =  605,427,418,493    = 200,903*3,013,531    prime at n=15

[rogue]

Originally Posted by Puzzle-Peter

878519842*3^7-1 = 1,921,322,894,453  = 266,759*7,202,467     prime at n=64
885176830*3^5-1 =  215,097,969,689    = 101,207*2125,327     prime at n=6
830490286*3^6-1 =  605,427,418,493    = 200,903*3,013,531    prime at n=15

Which is why we require primality tests, especially for low n. It might be fixed in gwnum v26.5, but I haven't tested it.

[kar_bon]

Originally Posted by rogue

Which is why we require primality tests, especially for low n. It might be fixed in gwnum v26.5, but I haven't tested it.

LLR V3.8.5 gives:

878519842 > 3^7, so, only a Strong PRP test is done for 878519842*3^7-1.
878519842*3^7-1 is not prime, although base 3-Fermat PSP!!  Time : 26.113 ms.
885176830 > 3^5, so, only a Strong PRP test is done for 885176830*3^5-1.
885176830*3^5-1 is not prime, although base 3-Fermat PSP!!  Time : 21.233 ms.
830490286 > 3^6, so, only a Strong PRP test is done for 830490286*3^6-1.
830490286*3^6-1 is not prime, although base 3-Fermat PSP!!  Time : 19.651 ms.

[rogue]

Originally Posted by kar_bon

LLR V3.8.5 gives:

878519842 > 3^7, so, only a Strong PRP test is done for 878519842*3^7-1.
878519842*3^7-1 is not prime, although base 3-Fermat PSP!!  Time : 26.113 ms.
885176830 > 3^5, so, only a Strong PRP test is done for 885176830*3^5-1.
885176830*3^5-1 is not prime, although base 3-Fermat PSP!!  Time : 21.233 ms.
830490286 > 3^6, so, only a Strong PRP test is done for 830490286*3^6-1.
830490286*3^6-1 is not prime, although base 3-Fermat PSP!!  Time : 19.651 ms.

The issue is still in gwnum v26.5 I've let George know.

[CRGreathouse]

Originally Posted by gd_barnes

Here's a question for the PRP/PSP gurus:

Is it possible to have a 3-PRP or "any" PRP for that matter that has more than 2 prime factors? Are there any examples?

See Sloane's A007011 for examples of the 2-PrP variety. The base-3 equivalent, 91, 286, 11011, 341341, ..., isn't there but should still be infinite.

[gd_barnes]

Originally Posted by rogue

The issue is still in gwnum v26.5 I've let George know.

I'm a little confused. Why is a PRP that is a composite a problem and hence why does it need to be reported to George? It is quite normal that we have a few isolated PRPs such as what Peter has mentioned here that are composites. He is testing millions of k's on base 3 using the PFGW script and so is sure to find a few small composite PRPs. He may be using my recommendation of -f30 to speed up testing somewhat on base 3 to n=25K and so will get more composite PRPs than with -f (or its equivalent -f100). He showed where the k was tested correctly as prime at a higher n than the composite PRP in each case.

In looking at what both Peter and Karsten posted, it appears to me that both PFGW and LLR are acting correctly. Am I missing something?

[rogue]

Originally Posted by gd_barnes

I'm a little confused. Why is a PRP that is a composite a problem and hence why does it need to be reported to George? It is quite normal that we have a few isolated PRPs such as what Peter has mentioned here that are composites. He is testing millions of k's on base 3 using the PFGW script and so is sure to find a few small composite PRPs. He may be using my recommendation of -f30 to speed up testing somewhat on base 3 to n=25K and so will get more composite PRPs than with -f (or its equivalent -f100). He showed where the k was tested correctly as prime at a higher n than the composite PRP in each case.

In looking at what both Peter and Karsten posted, it appears to me that both PFGW and LLR are acting correctly. Am I missing something?

I was concerned that gwnum was choosing an FFT size that was too small, which is why I reported it to George, but I just realized this morning that the PRP test for these small numbers is done with GMP, not gwnum, so there isn't much I can do.

[Puzzle-Peter]

Originally Posted by gd_barnes

I'm a little confused. Why is a PRP that is a composite a problem and hence why does it need to be reported to George? It is quite normal that we have a few isolated PRPs such as what Peter has mentioned here that are composites. He is testing millions of k's on base 3 using the PFGW script and so is sure to find a few small composite PRPs. He may be using my recommendation of -f30 to speed up testing somewhat on base 3 to n=25K and so will get more composite PRPs than with -f (or its equivalent -f100). He showed where the k was tested correctly as prime at a higher n than the composite PRP in each case.

In looking at what both Peter and Karsten posted, it appears to me that both PFGW and LLR are acting correctly. Am I missing something?

I used -f100. But the script recorded those in the appropriate file and went on testing these k's until it found a prime. Which is the expected behavior, isn't it?

[rogue]

Originally Posted by Puzzle-Peter

I used -f100. But the script recorded those in the appropriate file and went on testing these k's until it found a prime. Which is the expected behavior, isn't it?

Yes. Note that -f and -f100 are equivalent. These false PRPs probably would have been factored by -f200, but the extra time to factor is probably not worth it. You could try -b5 to change the base for the PRP test. I don't know if that works with a script though.