Leyland Primes

[storm5510]

Member pxp has a data table of Leyland primes here. I decided to do an experiment based on two items in his table. Lines 519 and 521. (6255,1496) and (6312,1427). I created a sieve within the rules of what rogue's xyyxsieve program would allow. I ran the results with OpenPFGW. I wasn't expecting to find anything, but I did. The below took about 18 hours of run time. I stopped the process at this point.

1347^6200-6200^1347
1449^6218-6218^1449
2282^6221-6221^2282
2301^6212-6212^2301
3068^6219-6219^3068

All of these are 3-PRP yet do not appear in pxp's table. My conclusion is that 3-PRP does not necessarily mean "prime." PRP alone means probably prime. I don't understand the significance of the "3" in front. To prove primality on expressions in this form, a further test must be ran, I suspect. I have no idea what this might be done with.

[paulunderwood]

Originally Posted by storm5510

Member pxp has a data table of Leyland primes here. I decided to do an experiment based on two items in his table. Lines 519 and 521. (6255,1496) and (6312,1427). I created a sieve within the rules of what rogue's xyyxsieve program would allow. I ran the results with OpenPFGW. I wasn't expecting to find anything, but I did. The below took about 18 hours of run time. I stopped the process at this point.



All of these are 3-PRP yet do not appear in pxp's table. My conclusion is that 3-PRP does not necessarily mean "prime." PRP alone means probably prime. I don't understand the significance of the "3" in front. To prove primality on expressions in this form, a further test must be ran, I suspect. I have no idea what this might be done with.

PRP means Probable Prime. That probability might be 99.999999999999% but it is not 100%. Some numbers that are 3-PRP are not prime. For example 91 = 7*13. That is 91 is a base 3 Fermat pseudoprime.

A number n being Fermat 3-PRP means 3^(n-1)==1 mod n. Due to fast left-right exponentiation and for large numbers using FFT further speeds up testing. But is is not 100%. For this we need some other method of proof. If we can get just over 25% factorization of n-1 and n+1, there are quick methods akin in speed to a PRP test.

If no easy method is to be had then we have to use something like ECPP which uses the arithmetic of elliptic curves. The most recent incarnation is Andreas Enge's CM program. A PRP test might take minutes on a single core, whereas ECPP might take weeks on a multicore system.

I think why your found numbers are not in pxp's table is that they are not of the form x^y+y^x.

[kar_bon]

You should look here in this forum for the minus-kind of Leyland numbers and also this page.

All your found PRPs are listed there and already inserted in FactorDB before 2018.

[storm5510]

Originally Posted by paulunderwood

...If no easy method is to be had then we have to use something like ECPP which uses the arithmetic of elliptic curves. The most recent incarnation is Andreas Enge's CM program. A PRP test might take minutes on a single core, whereas ECPP might take weeks on a multicore system.

I think why your found numbers are not in pxp's table is that they are not of the form x^y+y^x.

"Andreas Enge's CM" appears to be a Linux program. I didn't see anything Windows based.

I didn't know Leylands were "+" only. I should have paid more attention. It is even in the topic title.

Originally Posted by kar_bon

You should look here in this forum for the minus-kind of Leyland numbers and also this page.

All your found PRPs are listed there and already inserted in FactorDB before 2018.

I appreciate the links. I looked at both. FactorDB seems a bit difficult to navigate. I need to spend more time with it. Perhaps I could find something in there which might indicate a valid range to test.

I changed the sign in my sieve to "+" and sieved to P = 50,000,000. Instead of having thousands of candidates, there were only 90.

[xilman]

Originally Posted by storm5510

"Andreas Enge's CM" appears to be a Linux program. I didn't see anything Windows based.

"Andreas Enge's CM" is a program.

It works just as well (exactly the same, in fact) under Windows, MacOS, BSD and anything else to which the GMP library has been ported.

The only reason I have not yet run it under Windows is that I haven't yet bothered to try. I plead guilty to the charge of laziness.

That that you didn't see anything says much more about your observational ability than anything else.

[storm5510]

Originally Posted by xilman

..That that you didn't see anything says much more about your observational ability than anything else.

Everything I saw was "tar" and/or "gz." I will have to look again. My observational ability is far less than it used to be. I won't say more because I have already been belittled for it once. I may have to quit on all this in a year or so.

[xilman]

Originally Posted by storm5510

Everything I saw was "tar" and/or "gz." I will have to look again. My observational ability is far less than it used to be. I won't say more because I have already been belittled for it once. I may have to quit on all this in a year or so.

tar and gz are storage formats. They are completely OS agnostic.

Windows has been able to read them for over twenty years to my knowledge - back when I worked for MSFT.