PRPs that are composites

[Jens K Andersen]

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

are there any records for prps that are composite

A base b Fermat prp test on a number form involving a power of b can easily give a b-psp (a base b pseudoprime). I recommend against it unless you know how the form behaves for that base. Base 3 is default in pfgw. Use another base N with pfgw -bN, for example:
pfgw -b2 -q"655030086*3^3-1"

655030086*3^3-1 is composite: [014267D38] (0.0001s+0.0002s)

Do not use base 2 on Mersenne numbers. They are all 2-prp.
There are ways to generate large psp's so meaningful record categories would need restrictions.
http://www.worldofnumbers.com/em125.htm and A068216 show the smallest n-digit 2-psp for up to 20 digits where it's 10^19+494514450733. Continuing looks hard.

[gd_barnes]

Don't worry Chris, at the lower n-ranges you were probably saving time not trial factoring using -f100. It's at the higher n-ranges where you would lose substantial time. Still, it's better to do SOME trial factoring at the lower limits so you don't have so many composite PRP's to mess with.

I suggest -f100 for most testing to any reasonably large n-limit. But if you're testing, say, only n=1-1000, then -f10 is faster.

For testing n=1-25000 like we're doing for Riesel base 3, -f100 is slower than no trial factoring at the low n-ranges but is faster for n>5K-10K and MUCH faster for n>10K.

Somebody would have to test this to verify it but here is what I THINK would be the fastest way to test base 3 if you don't mind the manual intervention:

Use -f10 up to n=1000.
Use -f30 to -f50 for n=1000-5000.
Use -f100 for all n>5000.

That's just a theory based on experience but gives you an idea of what works best.

Personally, I don't want the manual intervention so I just put it on -f100 and let 'er rip from n=1 to 10K. Then its good old sieving time.

I don't recommend anything above -f100 except perhaps non-standard forms. I believe that PFGW has an algorithm that it uses to determine what the optimum trial-factoring limit is for each test. If anyone can think of a reason to use higher than -f100, than I'd like to hear it.

BTW, to be included in the table above, you have to use -f100. To do otherwise is cheating. (lol)


Gary

[gd_barnes]

Everyone post your list of composite PRP's here using the -f100 (or -f) switch and I'll add them to the list above. Also post what n-value returned a prime.

If you feel like it, feel free to post the factors of the composite PRPs also. If not, I can quickly do it. Alperton's site here has a batch process at the bottom of the page that quickly gives the factors of as many numbers at once as you would like. That is what I use.


Gary

[Flatlander]

Given a composite PRP, what is the quickest way of finding the first real prime for that k?
(k*3^n-1)

[gd_barnes]

Originally Posted by Flatlander

Given a composite PRP, what is the quickest way of finding the first real prime for that k?
(k*3^n-1)

Manually using Alperton's site shown in the last post or with PFGW using a loop starting with the n-value 1 higher than the composite PRP.

[XYYXF]

(3^37159+1)/4 is divisible by 250154389. It was found by Henri Lifchitz as 3-PRP, but then a factor was discovered (by me).

[Jens K Andersen]

Originally Posted by XYYXF

(3^37159+1)/4 is divisible by 250154389. It was found by Henri Lifchitz as 3-PRP, but then a factor was discovered (by me).

ABC2 (3^$a+1)/4
a:primes from 10000 to 10100

(3^10007+1)/4 is 3-PRP! (1.0020s+0.0004s)
(3^10009+1)/4 is 3-PRP! (0.9993s+0.0009s)
(3^10037+1)/4 is 3-PRP! (1.0373s+0.0008s)
(3^10039+1)/4 is 3-PRP! (1.0126s+0.0009s)
(3^10061+1)/4 is 3-PRP! (1.0093s+0.0008s)
(3^10067+1)/4 is 3-PRP! (1.0153s+0.0010s)
(3^10069+1)/4 is 3-PRP! (1.0278s+0.0011s)
(3^10079+1)/4 is 3-PRP! (1.0229s+0.0020s)
(3^10091+1)/4 is 3-PRP! (1.0267s+0.0011s)
(3^10093+1)/4 is 3-PRP! (1.0259s+0.0011s)
(3^10099+1)/4 is 3-PRP! (1.0280s+0.0012s)

See post 12.

[Flatlander]

Originally Posted by gd_barnes

Everyone post your list of composite PRP's here using the -f100 (or -f) switch and I'll add them to the list above. Also post what n-value returned a prime.

If you feel like it, feel free to post the factors of the composite PRPs also. If not, I can quickly do it. Alperton's site here has a batch process at the bottom of the page that quickly gives the factors of as many numbers at once as you would like. That is what I use.
Gary

Composite PRPs (found with -f):
631020668*3^6-1 = 460014066971 = 570827 * 805873
631293542*3^3-1 = 17044925633 = 75377 * 226129
636386826*3^9-1 = 12526001896157 = 1615421 * 7754017

Real Primes:
631020668*3^41-1
631293542*3^26-1
636386826*3^17-1

[gd_barnes]

Originally Posted by Jens K Andersen

ABC2 (3^$a+1)/4
a:primes from 10000 to 10100

(3^10007+1)/4 is 3-PRP! (1.0020s+0.0004s)
(3^10009+1)/4 is 3-PRP! (0.9993s+0.0009s)
(3^10037+1)/4 is 3-PRP! (1.0373s+0.0008s)
(3^10039+1)/4 is 3-PRP! (1.0126s+0.0009s)
(3^10061+1)/4 is 3-PRP! (1.0093s+0.0008s)
(3^10067+1)/4 is 3-PRP! (1.0153s+0.0010s)
(3^10069+1)/4 is 3-PRP! (1.0278s+0.0011s)
(3^10079+1)/4 is 3-PRP! (1.0229s+0.0020s)
(3^10091+1)/4 is 3-PRP! (1.0267s+0.0011s)
(3^10093+1)/4 is 3-PRP! (1.0259s+0.0011s)
(3^10099+1)/4 is 3-PRP! (1.0280s+0.0012s)

See post 12.

AMAZING!! I just ran this script for primes from n=2 to 11000. Every one of them shows 3-PRP if I set trial factoring off with -f0 !!

I turned factoring on with -f100 and it quickly found the smallest composite PRPs for the form:
(3^11+1)/4 = 44287 = 67*661
(3^17+1)/4 = 32285041 = 103*307*1021

BTW, what program for a factoring novice such as me do you recommend for factoring larger numbers? I use alpertron.com for factoring smaller numbers or for finding smaller factors (perhaps < 10M) of large numbers up to 10000 digits. But it is not good at all at finding large factors of large numbers such as was demontrasted by XYYXF earlier. It is much too slow for that. It wouldn't even need to find one that big.

Thanks for the very interesting piece of work Jens!

To all,

My intent of this thread is to only list the Riesel and Sierp conjecture 3-PRP's in the 1st post here. But I'm always quite interested in hearing more about the topic so continue posting the links and showing us interesting tidbits of information about PRP's, PSP's, etc.


Gary

[gd_barnes]

Originally Posted by Flatlander

Composite PRPs (found with -f):
631020668*3^6-1 = 460014066971 = 570827 * 805873
631293542*3^3-1 = 17044925633 = 75377 * 226129
636386826*3^9-1 = 12526001896157 = 1615421 * 7754017

Real Primes:
631020668*3^41-1
631293542*3^26-1
636386826*3^17-1

Thanks. The last one was normalized to k=212128942 in the same manner as would be done on the top-5000 site.

[Jens K Andersen]

Originally Posted by gd_barnes

BTW, what program for a factoring novice such as me do you recommend for factoring larger numbers?

It varies what I use and when time is not critical it's often determined by convenience for a given problem. Things I use include PFGW, PARI/GP, NewPGen, GMP-ECM, and own unpublished sieves and trial factoring programs in C.

I don't follow Conjectures 'R Us and haven't examined what is convenient for problems here. I noticed this thread title in New Posts.