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: [B]S0=1154[/B] ( = (6^2-2)^2-2 ) and the number of iteration is: [B]n-2[/B] .

See: [URL="https://oeis.org/A059608"]OEIS A059608[/URL] for details of the sequence.

The PARI/gp code is:
[CODE]for(i=2,5000, n=2*i; N=2^n-5; [B]S0=1154[/B]; x=S0; for(j=1, [B]n-2[/B], x=Mod(x^2-2,N)); if(x==S0, print1(n,", ")))[/CODE]

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, ...[/CODE]

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.

[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
[/CODE]

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

Here are the [URL="http://www.primenumbers.net/prptop/searchform.php?form=2^n-5&action=Search"]known gigantic PRPs[/URL] of this form :smile:

[QUOTE=T.Rex;409127]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: [B]S0=1154[/B] ( = (6^2-2)^2-2 ) and the number of iteration is: [B]n-2[/B] .

See: [URL="https://oeis.org/A059608"]OEIS A059608[/URL] for details of the sequence.

The PARI/gp code is:
[CODE]for(i=2,5000, n=2*i; N=2^n-5; [B]S0=1154[/B]; x=S0; for(j=1, [B]n-2[/B], x=Mod(x^2-2,N)); if(x==S0, print1(n,", ")))[/CODE]

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, ...[/CODE]

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.[/QUOTE]

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

[QUOTE=R.D. Silverman;409136]Have you considered seeing a psychiatrist? He/she might be able to help your OCD.[/QUOTE]
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).

[QUOTE=LaurV;409163]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).[/QUOTE]

On the contrary. He seems [b]very[/b] 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?

[QUOTE=R.D. Silverman;409176]However, your comment is well taken. Should his obsession not be pointed out?[/QUOTE]

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

[QUOTE=science_man_88;409178]you practice mathematics let someone who practices medicine make the diagnosis, if there's one to be made.[/QUOTE]

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

[QUOTE=R.D. Silverman;409179]One can observe and discern what seems to be an obsession without being an M.D.[/QUOTE]

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.

[QUOTE=R.D. Silverman;409136]Have you considered seeing a psychiatrist? He/she might be able to help your OCD.[/QUOTE]
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 [I]obsession[/I] (as you said) this Thurday. However, after all this personal work, I feel now very good, just crazy as usual.

[QUOTE=R.D. Silverman;409176]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.[/QUOTE]
Explanation is not a proof. Explanation is only words. Would you mind writing a proof ?

"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 [I]obsession[/I] (as you said).
[B]For now, you just talked in English, not in Math language with all needed details required by a complete proof.[/B]

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

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, [B]without finding a pseudoprime[/B]. Not a proof, for sure.

[QUOTE=T.Rex;409209]Explanation is not a proof. Explanation is only words. Would you mind writing a proof ?[/QUOTE]

Not for someone who admits he knows nothing about the math involved.
It would be meaningless to you. As is most everything else about this subject.

[QUOTE=R.D. Silverman;409222]
It would be meaningless to you.[/QUOTE]

equally so about half the things I phrase mathematically incorrect for you, never stopped you chiming in before.

[QUOTE=science_man_88;409224]equally so about half the things I phrase mathematically incorrect for you, never stopped you chiming in before.[/QUOTE]

I have *already* chimed in. Jon Grantham's work established that PRP tests based on Lucas sequences
are a special case of his more general Frobenius PRP tests. However, T.Rex was unwilling to
accept this.

Why should I spend the time writing up 2 to 3 pages of a formal proof for someone who won't understand it?
(neither will you).

His request for a proof was not serious. It was a taunt.