PRPs that are composites

[gd_barnes]

Post your PRPs that are composites in this thread. Include the form, the decimal expansion, the prime factors, and a higher n-value that makes the form prime.

This should be an interesting listing for historical mathematical reference.

I'll get us started. Today I did proofs on all of my PRP's for Sierp base 3 for k=10M-30M and n=1 to 25K. I normally always do primality proofs after doing intial PRP tests on all bases but this one is so large that I had forgotten to do it. Out of nearly 10 million tests, I found just 11 3-PRP's (barely above 1 in 1 million!) that were composite as shown below.

I was quite disappointed that none of the k's were difficult to find a prime for after discovering the composite PRP for each of them.

As people post their composite PRP's, I will add them to the list in base/k-value order.

                                                          prime
     form              expansion       prime factors        n=   note
Sierp base 3:
   345074*3^11+1      61,128,823,879   132,157*462,547      23   (a)
 15685616*3^ 8+1     102,913,326,557   143,467*717,331       9
 17915936*3^11+1   3,173,754,314,593   629,857*5,038,849    13
 18559230*3^ 7+1      40,589,036,011   70,957*572,023       20   (b)
 19683210*3^ 7+1      43,047,180,271   131,221*328,051      12   (b)
 19813528*3^ 7+1      43,332,185,737   81,649*530,713       10
 26703886*3^ 9+1     525,612,588,139   142,183*3,696,733    19
 28099008*3^ 6+1      20,484,176,833   84,673*241,921        7   (b)
 28462346*3^ 7+1      62,247,150,703   176,419*352,837      19
 28995824*3^13+1  46,228,709,107,153   782,497*59,078,449   14
 29214630*3^ 8+1     191,677,187,431   69,661*2,751,571      9   (b)
 
Riesel base 3:
212128942*3^10-1  12,526,001,896,157   1,615,421*7,754,017  18   (c)
218343362*3^ 4-1      17,685,812,321   76,781*230,341        7   (d)
504725030*3^ 3-1      13,627,575,809   87,011*156,619       11
631020668*3^ 6-1     460,014,066,971   570,827*805,873      41
631293542*3^ 3-1      17,044,925,633   75,377*226,129       26
682649738*3^ 4-1      55,294,628,777   160,637*344,221      14

(a) Reduced from 27950994*3^7+1.
(b) k divisible by 3 where k/3 has a prime @ n=1 hence cannot be reduced.
(c) Reduced from 631020668*3^9-1.
(d) Reduced from 655030086*3^3-1.

For decimal expansion and factors, check out Alpterton's excellent prime factoring web page here.

If the PRP is so large that it takes a long time to factor (highly unlikely), I may ask people if they want to assist in a group effort to do so if people like doing that type of thing. If not, I may take it up in the factoring forum.


Gary

[Flatlander]

From the R. base 3 attack:

PRPs that proved composite:
511781138*3^2-1
512485142*3^2-1
513538278*3^2-1
513592294*3^3-1
514433128*3^2-1
515859254*3^5-1
516652298*3^2-1
516841522*3^2-1

First prime for these Ks:
511781138*3^5-1
512485142*3^3-1
513538278*3^5-1
513592294*3^11-1
514433128*3^22-1
515859254*3^79-1
516652298*3^14-1
516841522*3^4-1

I'll leave the maths as an exercise for the reader.

[mdettweiler]

Originally Posted by Flatlander

From the R. base 3 attack:

PRPs that proved composite:
511781138*3^2-1
512485142*3^2-1
513538278*3^2-1
513592294*3^3-1
514433128*3^2-1
515859254*3^5-1
516652298*3^2-1
516841522*3^2-1

First prime for these Ks:
511781138*3^5-1
512485142*3^3-1
513538278*3^5-1
513592294*3^11-1
514433128*3^22-1
515859254*3^79-1
516652298*3^14-1
516841522*3^4-1

I'll leave the maths as an exercise for the reader.

Decimal expansions/factorizations (courtesy of msieve v1.34):

511781138*3^2-1 = 4606030241 = 29 * 41 * 269 * 14401
512485142*3^2-1 = 4612366277 = 29 * 3109 * 51157
513538278*3^2-1 = 4621844501 = 39251 * 117751
513592294*3^3-1 = 13866991937 = 499 * 2657 * 10459
514433128*3^2-1 = 4629898151 = 2779 * 166669
515859254*3^5-1 = 125353798721 = 32321 * 3878401
516652298*3^2-1 = 4649870681 = 16073 * 289297
516841522*3^2-1 = 4651573697 = 29 * 41 * 89 * 113 * 389

[henryzz]

have you been doing no trial factoring flatlander
some of those prps have small factors

[KEP]

Originally Posted by henryzz

have you been doing no trial factoring flatlander
some of those prps have small factors

I think I'm to blame for the lack of the small factors. I forgot to tell to write the -f after script.pl in WinPFGW.exe, in my instructions. The instructions is now corrected.

Sorry anyone, but it appears that maybe with the use of -f most composite PRPs (if not all) can be avoided

KEP

[Flatlander]

Originally Posted by KEP

I think I'm to blame for the lack of the small factors. I forgot to tell to write the -f after script.pl in WinPFGW.exe, in my instructions. The instructions is now corrected.

Sorry anyone, but it appears that maybe with the use of -f most composite PRPs (if not all) can be avoided

KEP

Aaaaaaaaaaaaargh!

Only kidding.

Actually, sorting out the composite PRPs was becoming a pain so this is good news. (Now I can, hopefully, just compare exact file sizes instead of loading huge files and finding the differences.)
The PFGW documentation says -f100 does 100% of standard factoring, so what does -f do on its own?

[Jens K Andersen]

Originally Posted by Flatlander

The PFGW documentation says -f100 does 100% of standard factoring, so what does -f do on its own?

-f and -f100 do the same. Standard factoring simply means what is done with -f on its own. The standard trial factor limit depends on the size of number and the PFGW version. It does not depend on the form of the number although some forms are prp tested faster so a lower limit would be better for those.
-f50 will halve the standard limit, -f300 will triple it, and so on.

[henryzz]

even with factoring i got one:
655030086*3^3-1 is 3-PRP = 76781 * 230341
655030086*3^6-1 is prime

are there any records for prps that are composite

[Flatlander]

Originally Posted by henryzz

even with factoring i got one:
655030086*3^3-1 is 3-PRP = 76781 * 230341
655030086*3^6-1 is prime

For these small tests, would if be worth me using e.g. -f300 to try to eliminate these composites, or would it slow PFGW signifiicantly?
(Max n is 1000.)

[henryzz]

Originally Posted by Flatlander

For these small tests, would if be worth me using e.g. -f300 to try to eliminate these composites, or would it slow PFGW signifiicantly?
(Max n is 1000.)

i dunno it might be worth u timing a 100000 k range with both

[Flatlander]

For the 19 composite PRPs from me and Gary it took -f1200 to stop any of them being reported as PRPs.

For a small R. base-3 test, 2 < n< 330, k from 600M:
-f took 12m 30sec
-f500 took 16m 45sec.

So it depends how much of a nuisance composite PRPs are to you. (To me they are a pain because of the huge files involved in the R. base 3 attack.)

I suppose this problem will get worse as k get even bigger???