mersenneforum.org  

Go Back   mersenneforum.org > Prime Search Projects > Conjectures 'R Us

Reply
 
Thread Tools
Old 2008-07-13, 03:53   #1
gd_barnes
 
gd_barnes's Avatar
 
May 2007
Kansas; USA

1024110 Posts
Default 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
gd_barnes is offline   Reply With Quote
Old 2008-11-17, 18:31   #2
Flatlander
I quite division it
 
Flatlander's Avatar
 
"Chris"
Feb 2005
England

81D16 Posts
Default

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
Flatlander is offline   Reply With Quote
Old 2008-11-17, 19:46   #3
mdettweiler
A Sunny Moo
 
mdettweiler's Avatar
 
Aug 2007
USA (GMT-5)

792 Posts
Default

Quote:
Originally Posted by Flatlander View Post
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
mdettweiler is offline   Reply With Quote
Old 2008-11-17, 20:07   #4
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

131678 Posts
Default

have you been doing no trial factoring flatlander
some of those prps have small factors
henryzz is offline   Reply With Quote
Old 2008-11-17, 20:14   #5
KEP
Quasi Admin Thing
 
KEP's Avatar
 
May 2005

24×59 Posts
Default

Quote:
Originally Posted by henryzz View Post
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
KEP is offline   Reply With Quote
Old 2008-11-17, 21:21   #6
Flatlander
I quite division it
 
Flatlander's Avatar
 
"Chris"
Feb 2005
England

31×67 Posts
Default

Quote:
Originally Posted by KEP View Post
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
Flatlander is offline   Reply With Quote
Old 2008-11-17, 23:04   #7
Jens K Andersen
 
Jens K Andersen's Avatar
 
Feb 2006
Denmark

2×5×23 Posts
Default

Quote:
Originally Posted by Flatlander View Post
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.
Jens K Andersen is offline   Reply With Quote
Old 2008-11-18, 20:06   #8
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

34·71 Posts
Default

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
henryzz is offline   Reply With Quote
Old 2008-11-18, 20:12   #9
Flatlander
I quite division it
 
Flatlander's Avatar
 
"Chris"
Feb 2005
England

31×67 Posts
Default

Quote:
Originally Posted by henryzz View Post
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.)
Flatlander is offline   Reply With Quote
Old 2008-11-18, 20:18   #10
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

34·71 Posts
Default

Quote:
Originally Posted by Flatlander View Post
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
henryzz is offline   Reply With Quote
Old 2008-11-18, 21:58   #11
Flatlander
I quite division it
 
Flatlander's Avatar
 
"Chris"
Feb 2005
England

31·67 Posts
Default

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
File Type: txt results.txt (807 Bytes, 123 views)
Flatlander is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Near- and quasi-repunit PRPs Batalov And now for something completely different 10 2019-09-12 13:31
Very (large) PRPs? PawnProver44 Information & Answers 95 2016-05-20 18:24
OEIS - (2^n-5)/3 - n odd - LLT-like algorithm for finding PRPs T.Rex Miscellaneous Math 10 2015-09-01 18:07
PRPs not prime schickel FactorDB 1 2015-08-03 02:50
Proven PRPs? Random Poster FactorDB 0 2012-07-24 10:53

All times are UTC. The time now is 07:33.

Sat Nov 28 07:33:15 UTC 2020 up 79 days, 4:44, 3 users, load averages: 1.12, 1.22, 1.19

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.