OEIS - 2^n-5 - LLT-like algorithm for finding PRPs

T.Rex · 2015-08-29, 20:12

Here is a LLT-like algorithm, using cycles instead of a binary tree (which does not exist for this kind of numbers) of the DiGraph under x^2-2 modulo N=2^n-5, which seems to find all PRPs of OEIS sequence A059608, starting with n=4. Note that n must be even after the first unic odd number 3 in OEIS.

The seed is: S0=1154 ( = (6^2-2)^2-2 ) and the number of iteration is: n-2 .

See: OEIS A059608 for details of the sequence.

The PARI/gp code is:

Code:

for(i=2,5000, n=2*i; N=2^n-5; S0=1154; x=S0; for(j=1, n-2, x=Mod(x^2-2,N)); if(x==S0, print1(n,", ")))

It generates:

Code:

4 ,6 ,8, 10, 12, 18, 20, 26, 32, 36, 56, 66, 118, 130, 150, 166, 206, 226, 550, 706, 810, 1136, 1228, 1818, 2368, 2400, 3128, 4532, 5112, 8492, ...

As I said in the 4 other threads dealing with: 2^n+3, 2^n+5, and 2^n-3, where I also provided a LLT-like algorithm generating PRPs, the goal of this thread is to show that the LLT algorithm can be used to find PRPs of kinds of numbers different from Mersenne and Fermat numbers.
In fact, IMHO, this algorithm "may" show a deep property of these 2^n-5 prime numbers. I mean to say that I think that this algorithm finds all 2^n-5 primes, and only them. But, without any Math proof, it is only a conjecture.

Anyway, without a proof, it may be possible that there are many/infinitely pseudoprimes that verify this property and are not prime, though results of the algorithm are OK (no false negative, no false positive) up to 8492, and probably higher, like for Wagstaff numbers using Reix-Vrba algorithm where top n for a prime is: 13,372,531 and where they are now looking after: 17,500,000. However, I do not think so, but I have no proof, and it may be difficult to build a proof with today known Number Theory technics.

Anyway, this thread is pure Math: provide experiment data showing that there is something interesting there. But it is only first step. Second step would be providing a Math proof.

paulunderwood · 2015-08-29, 21:21

Code:

? for(i=2,5000, n=2*i; N=2^n-5; if(Mod(2,N)^N==2, print1(n,", ")))
4, 6, 8, 10, 12, 18, 20, 26, 32, 36, 56, 66, 118, 130, 150, 166, 206, 226, 550, 706, 810, 1136, 1228, 1818, 2368, 2400, 3128, 4532, 5112, 8492, ^C

A base 2 Fermat PRP produces the same results. Which of the two methods produces more pseudoprimes is debatable.

Here are the known gigantic PRPs of this form

R.D. Silverman · 2015-08-29, 23:05

Quote:

Originally Posted by T.Rex

Here is a LLT-like algorithm, using cycles instead of a binary tree (which does not exist for this kind of numbers) of the DiGraph under x^2-2 modulo N=2^n-5, which seems to find all PRPs of OEIS sequence A059608, starting with n=4. Note that n must be even after the first unic odd number 3 in OEIS.

The seed is: S0=1154 ( = (6^2-2)^2-2 ) and the number of iteration is: n-2 .

See: OEIS A059608 for details of the sequence.

The PARI/gp code is:

Code:

for(i=2,5000, n=2*i; N=2^n-5; S0=1154; x=S0; for(j=1, n-2, x=Mod(x^2-2,N)); if(x==S0, print1(n,", ")))

It generates:

Code:

4 ,6 ,8, 10, 12, 18, 20, 26, 32, 36, 56, 66, 118, 130, 150, 166, 206, 226, 550, 706, 810, 1136, 1228, 1818, 2368, 2400, 3128, 4532, 5112, 8492, ...

As I said in the 4 other threads dealing with: 2^n+3, 2^n+5, and 2^n-3, where I also provided a LLT-like algorithm generating PRPs, the goal of this thread is to show that the LLT algorithm can be used to find PRPs of kinds of numbers different from Mersenne and Fermat numbers.
In fact, IMHO, this algorithm "may" show a deep property of these 2^n-5 prime numbers. I mean to say that I think that this algorithm finds all 2^n-5 primes, and only them. But, without any Math proof, it is only a conjecture.

Anyway, without a proof, it may be possible that there are many/infinitely pseudoprimes that verify this property and are not prime, though results of the algorithm are OK (no false negative, no false positive) up to 8492, and probably higher, like for Wagstaff numbers using Reix-Vrba algorithm where top n for a prime is: 13,372,531 and where they are now looking after: 17,500,000. However, I do not think so, but I have no proof, and it may be difficult to build a proof with today known Number Theory technics.

Anyway, this thread is pure Math: provide experiment data showing that there is something interesting there. But it is only first step. Second step would be providing a Math proof.

Have you considered seeing a psychiatrist? He/she might be able to help your OCD.

LaurV · 2015-08-30, 09:27

Quote:

Originally Posted by R.D. Silverman

Have you considered seeing a psychiatrist? He/she might be able to help your OCD.

This was uncalled for, and it does not bring anything positive in the discussion. We know your opinion (I even agreed with it), but this is misc math subforum, I thought you are not reading this crap.. Beside of including quote for all previous post (considered impolite by the netiquette). I suggest moving to the "less useful" topic (my post included).

R.D. Silverman · 2015-08-30, 14:36

Quote:

Originally Posted by LaurV

This was uncalled for, and it does not bring anything positive in the discussion. We know your opinion (I even agreed with it), but this is misc math subforum, I thought you are not reading this crap.. Beside of including quote for all previous post (considered impolite by the netiquette). I suggest moving to the "less useful" topic (my post included).

On the contrary. He seems very obsessed. He is willfully ignorant, and seems to deliberately reject
well established mathematics. (i.e. the group-theoretic basis for his PRP algorithms)

I have told them that the PRP algorithms are legit. But I also pointed out that the obsession with "proofs"
are misguided. And I EXPLAINED WHY. But T.Rex does not listen.

This thread was started in the math sub-forum. If people don't want my comments, then don't
post there.

However, your comment is well taken. Should his obsession not be pointed out?

science_man_88 · 2015-08-30, 14:42

Quote:

Originally Posted by R.D. Silverman

However, your comment is well taken. Should his obsession not be pointed out?

you practice mathematics let someone who practices medicine make the diagnosis, if there's one to be made.

R.D. Silverman · 2015-08-30, 15:13

Quote:

Originally Posted by science_man_88

you practice mathematics let someone who practices medicine make the diagnosis, if there's one to be made.

One can observe and discern what seems to be an obsession without being an M.D.

science_man_88 · 2015-08-30, 15:16

Quote:

Originally Posted by R.D. Silverman

One can observe and discern what seems to be an obsession without being an M.D.

seems being the key word there. However a proper diagnosis should be done first which does require a doctor knowledgeable in the subject matter needed for diagnosis.

T.Rex · 2015-08-30, 20:07

Quote:

Originally Posted by R.D. Silverman

Have you considered seeing a psychiatrist? He/she might be able to help your OCD.

Thanks for the advice ! However, after the death of my wife in 2006, I see a psychiatrist every week since 2007. If I have time, I'll talk with him about my Math obsession (as you said) this Thurday. However, after all this personal work, I feel now very good, just crazy as usual.

T.Rex · 2015-08-30, 20:10

Quote:

Originally Posted by R.D. Silverman

I have told them that the PRP algorithms are legit. But I also pointed out that the obsession with "proofs" are misguided. And I EXPLAINED WHY.

Explanation is not a proof. Explanation is only words. Would you mind writing a proof ?

T.Rex · 2015-08-30, 20:35

"They didn't know that it was impossible, so they did it".
"Without deviation from the norm, progress is not possible".

Provide a Math proof, and I'll stop this obsession (as you said).
For now, you just talked in English, not in Math language with all needed details required by a complete proof.

Either we find a LLT-cycle pseudoprimes for Wagstaff or you provide a complete Math proof of YOUR obsession.

Remember that, till Lehmer provided a proof of LLT, LLT was only a way for finding PRPs, since Lucas never provided a complete proof.

The "Searching for Wagstaff PRP" team has checked exponents up to 5,000,000 and maybe more (300,000 to 500,000 exponents), now factoring above 17,000,000, without finding a pseudoprime. Not a proof, for sure.

2015-08-29, 20:12	#1
T.Rex Feb 2004 France 1624₈ Posts	OEIS - 2^n-5 - LLT-like algorithm for finding PRPs Here is a LLT-like algorithm, using cycles instead of a binary tree (which does not exist for this kind of numbers) of the DiGraph under x^2-2 modulo N=2^n-5, which seems to find all PRPs of OEIS sequence A059608, starting with n=4. Note that n must be even after the first unic odd number 3 in OEIS. The seed is: S0=1154 ( = (6^2-2)^2-2 ) and the number of iteration is: n-2 . See: OEIS A059608 for details of the sequence. The PARI/gp code is: Code: for(i=2,5000, n=2i; N=2^n-5; S0=1154; x=S0; for(j=1, n-2*, x=Mod(x^2-2,N)); if(x==S0, print1(n,", "))) It generates: Code: 4 ,6 ,8, 10, 12, 18, 20, 26, 32, 36, 56, 66, 118, 130, 150, 166, 206, 226, 550, 706, 810, 1136, 1228, 1818, 2368, 2400, 3128, 4532, 5112, 8492, ... As I said in the 4 other threads dealing with: 2^n+3, 2^n+5, and 2^n-3, where I also provided a LLT-like algorithm generating PRPs, the goal of this thread is to show that the LLT algorithm can be used to find PRPs of kinds of numbers different from Mersenne and Fermat numbers. In fact, IMHO, this algorithm "may" show a deep property of these 2^n-5 prime numbers. I mean to say that I think that this algorithm finds all 2^n-5 primes, and only them. But, without any Math proof, it is only a conjecture. Anyway, without a proof, it may be possible that there are many/infinitely pseudoprimes that verify this property and are not prime, though results of the algorithm are OK (no false negative, no false positive) up to 8492, and probably higher, like for Wagstaff numbers using Reix-Vrba algorithm where top n for a prime is: 13,372,531 and where they are now looking after: 17,500,000. However, I do not think so, but I have no proof, and it may be difficult to build a proof with today known Number Theory technics. Anyway, this thread is pure Math: provide experiment data showing that there is something interesting there. But it is only first step. Second step would be providing a Math proof.

2015-08-29, 21:21	#2
paulunderwood Sep 2002 Database er0rr 2×3²×11×19 Posts	Code: ? for(i=2,5000, n=2i; N=2^n-5; if(Mod(2,N)^N==2, print1(n,", "))) 4, 6, 8, 10, 12, 18, 20, 26, 32, 36, 56, 66, 118, 130, 150, 166, 206, 226, 550, 706, 810, 1136, 1228, 1818, 2368, 2400, 3128, 4532, 5112, 8492, ^C A base 2 Fermat PRP produces the same results. Which of the two methods produces more pseudoprimes is debatable. Here are the known gigantic PRPs of this form Last fiddled with by paulunderwood on 2015-08-29 at 21:24*

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Endorsement Prime Numbers finding algorithm	marouane	Computer Science & Computational Number Theory	18	2017-11-06 15:41
pari-algorithm for finding Gaussian integer bases	devarajkandadai	Software	0	2017-10-05 04:54
OEIS - (2^n-5)/3 - n odd - LLT-like algorithm for finding PRPs	T.Rex	Miscellaneous Math	10	2015-09-01 18:07
OEIS - A050414 - 2^n-3 - LLT-like algorithm for finding PRPs	T.Rex	Miscellaneous Math	16	2015-08-31 02:32
New Prime-Finding Algorithm Discovered! L00K HERE!	dilip_1bhowmik	Miscellaneous Math	22	2009-01-09 23:39

2015-08-30, 20:35	#11
T.Rex Feb 2004 France 916₁₀ Posts	"They didn't know that it was impossible, so they did it". "Without deviation from the norm, progress is not possible". Provide a Math proof, and I'll stop this obsession (as you said). For now, you just talked in English, not in Math language with all needed details required by a complete proof. Either we find a LLT-cycle pseudoprimes for Wagstaff or you provide a complete Math proof of YOUR obsession. Remember that, till Lehmer provided a proof of LLT, LLT was only a way for finding PRPs, since Lucas never provided a complete proof. The "Searching for Wagstaff PRP" team has checked exponents up to 5,000,000 and maybe more (300,000 to 500,000 exponents), now factoring above 17,000,000, without finding a pseudoprime. Not a proof, for sure.