20080713, 03:53  #1 
May 2007
Kansas; USA
2^{3}×3×431 Posts 
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 nvalue 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=10M30M 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 3PRP'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/kvalue 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^101 12,526,001,896,157 1,615,421*7,754,017 18 (c) 218343362*3^ 41 17,685,812,321 76,781*230,341 7 (d) 504725030*3^ 31 13,627,575,809 87,011*156,619 11 631020668*3^ 61 460,014,066,971 570,827*805,873 41 631293542*3^ 31 17,044,925,633 75,377*226,129 26 682649738*3^ 41 55,294,628,777 160,637*344,221 14 (b) k divisible by 3 where k/3 has a prime @ n=1 hence cannot be reduced. (c) Reduced from 631020668*3^91. (d) Reduced from 655030086*3^31. 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 Last fiddled with by gd_barnes on 20090101 at 05:52 Reason: add prp's 
20081117, 18:31  #2 
I quite division it
"Chris"
Feb 2005
England
2077_{10} Posts 
From the R. base 3 attack:
Code:
PRPs that proved composite: 511781138*3^21 512485142*3^21 513538278*3^21 513592294*3^31 514433128*3^21 515859254*3^51 516652298*3^21 516841522*3^21 First prime for these Ks: 511781138*3^51 512485142*3^31 513538278*3^51 513592294*3^111 514433128*3^221 515859254*3^791 516652298*3^141 516841522*3^41 Last fiddled with by Flatlander on 20081117 at 18:32 
20081117, 19:46  #3  
A Sunny Moo
Aug 2007
USA (GMT5)
3·2,083 Posts 
Quote:
511781138*3^21 = 4606030241 = 29 * 41 * 269 * 14401 512485142*3^21 = 4612366277 = 29 * 3109 * 51157 513538278*3^21 = 4621844501 = 39251 * 117751 513592294*3^31 = 13866991937 = 499 * 2657 * 10459 514433128*3^21 = 4629898151 = 2779 * 166669 515859254*3^51 = 125353798721 = 32321 * 3878401 516652298*3^21 = 4649870681 = 16073 * 289297 516841522*3^21 = 4651573697 = 29 * 41 * 89 * 113 * 389 

20081117, 20:07  #4 
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
2·29·101 Posts 
have you been doing no trial factoring flatlander
some of those prps have small factors 
20081117, 20:14  #5  
Quasi Admin Thing
May 2005
3C4_{16} Posts 
Quote:
Sorry anyone, but it appears that maybe with the use of f most composite PRPs (if not all) can be avoided KEP 

20081117, 21:21  #6  
I quite division it
"Chris"
Feb 2005
England
4035_{8} Posts 
Quote:
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? Last fiddled with by Flatlander on 20081117 at 21:23 

20081117, 23:04  #7  
Feb 2006
Denmark
2×5×23 Posts 
Quote:
f50 will halve the standard limit, f300 will triple it, and so on. 

20081118, 20:06  #8 
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
2·29·101 Posts 
even with factoring i got one:
655030086*3^31 is 3PRP = 76781 * 230341 655030086*3^61 is prime are there any records for prps that are composite Last fiddled with by henryzz on 20081118 at 20:16 
20081118, 20:12  #9 
I quite division it
"Chris"
Feb 2005
England
31·67 Posts 

20081118, 20:18  #10 
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
1011011100010_{2} Posts 

20081118, 21:58  #11 
I quite division it
"Chris"
Feb 2005
England
31·67 Posts 
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. base3 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??? 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Near and quasirepunit PRPs  Batalov  And now for something completely different  10  20190912 13:31 
Very (large) PRPs?  PawnProver44  Information & Answers  95  20160520 18:24 
OEIS  (2^n5)/3  n odd  LLTlike algorithm for finding PRPs  T.Rex  Miscellaneous Math  10  20150901 18:07 
PRPs not prime  schickel  FactorDB  1  20150803 02:50 
Proven PRPs?  Random Poster  FactorDB  0  20120724 10:53 