mersenneforum.org PRPs that are composites
 Register FAQ Search Today's Posts Mark Forums Read

 2008-07-13, 03:53 #1 gd_barnes     May 2007 Kansas; USA 23×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 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 (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 Last fiddled with by gd_barnes on 2009-01-01 at 05:52 Reason: add prp's
 2008-11-17, 18:31 #2 Flatlander I quite division it     "Chris" Feb 2005 England 207710 Posts 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 I'll leave the maths as an exercise for the reader. Last fiddled with by Flatlander on 2008-11-17 at 18:32
2008-11-17, 19:46   #3
mdettweiler
A Sunny Moo

Aug 2007
USA (GMT-5)

3·2,083 Posts

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

 2008-11-17, 20:07 #4 henryzz 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
2008-11-17, 20:14   #5
KEP

May 2005

3C416 Posts

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

2008-11-17, 21:21   #6
Flatlander
I quite division it

"Chris"
Feb 2005
England

40358 Posts

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

Last fiddled with by Flatlander on 2008-11-17 at 21:23

2008-11-17, 23:04   #7
Jens K Andersen

Feb 2006
Denmark

2×5×23 Posts

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

 2008-11-18, 20:06 #8 henryzz Just call me Henry     "David" Sep 2007 Cambridge (GMT/BST) 2·29·101 Posts 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 Last fiddled with by henryzz on 2008-11-18 at 20:16
2008-11-18, 20:12   #9
Flatlander
I quite division it

"Chris"
Feb 2005
England

31·67 Posts

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

2008-11-18, 20:18   #10
henryzz
Just call me Henry

"David"
Sep 2007
Cambridge (GMT/BST)

10110111000102 Posts

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

2008-11-18, 21:58   #11
Flatlander
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. 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???
Attached Files
 results.txt (807 Bytes, 154 views)

 Similar Threads Thread Thread Starter Forum Replies Last Post Batalov And now for something completely different 10 2019-09-12 13:31 PawnProver44 Information & Answers 95 2016-05-20 18:24 T.Rex Miscellaneous Math 10 2015-09-01 18:07 schickel FactorDB 1 2015-08-03 02:50 Random Poster FactorDB 0 2012-07-24 10:53

All times are UTC. The time now is 13:44.

Mon Apr 19 13:44:29 UTC 2021 up 11 days, 8:25, 0 users, load averages: 2.88, 2.90, 2.79