PRPs that are composites
 

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.


[code]
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
[/code]

(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 [URL="http://www.alpertron.com.ar/ECM.HTM"]here[/URL].

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

From the R. base 3 attack:
[code]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
[/code]I'll leave the maths as an exercise for the reader.

[quote=Flatlander;149663]From the R. base 3 attack:
[code]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
[/code]I'll leave the maths as an exercise for the reader.[/quote]
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

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

[QUOTE=henryzz;149671]have you been doing no trial factoring flatlander
some of those prps have small factors[/QUOTE]

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 :smile:

KEP

[quote=KEP;149672]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 :smile:

KEP[/quote]

Aaaaaaaaaaaaargh!

Only kidding. :wink:

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?

[QUOTE=Flatlander;149678]The PFGW documentation says -f100 does 100% of standard factoring, so what does -f do on its own?[/QUOTE]

-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.

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

[quote=henryzz;149764]even with factoring i got one:
655030086*3^3-1 is 3-PRP = 76781 * 230341
655030086*3^6-1 is prime[/quote]

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.)

[quote=Flatlander;149766]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.)[/quote]
i dunno it might be worth u timing a 100000 k range with both

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???