Conjectured Primality Test for Specific Class of k6^n-1
 

[LEFT][B]Definition :[/B] [TEX]\text{Let} [/TEX][TEX] $P_m(x)=2^{-m}\cdot \left(\left(x-\sqrt{x^2-4}\right)^{m}+\left(x+\sqrt{x^2-4}\right)^{m}\right)[/TEX] , [TEX]\text{where}[/TEX] [TEX]m[/TEX] [TEX]\text{and}[/TEX] [TEX]x[/TEX] [TEX] \text{are nonnegative integers .}[/TEX]

[B]Conjecture :[/B] [TEX]\text{Let}[/TEX] [TEX]N=k\cdot 6^n-1[/TEX] [TEX]\text{such that}[/TEX] [TEX]n>2[/TEX] , [TEX]k>0[/TEX] , [TEX]k \equiv 3,9 \pmod{10} [/TEX] [TEX]\text{and}[/TEX] [TEX]k<6^n[/TEX][/LEFT]

[CENTER][TEX]\text{Let}[/TEX] [TEX]S_i=P_6(S_{i-1})[/TEX] [TEX]\text{with}[/TEX] [TEX]S_0=P_{3k}(P_3(3))[/TEX] , [TEX]\text{thus}[/TEX]

[TEX]N[/TEX] [TEX]\text{is prime iff}[/TEX] [TEX]S_{n-2} \equiv 0 \pmod{N}[/TEX][/CENTER]

[LEFT][URL="http://maxima-online.org/?inc=r1613303604"]Maxima Implementation of the test[/URL][/LEFT]

[QUOTE=primus;380341][TEX]\text{Let}[/TEX] [TEX]S_i=P_6(S_{i-1})[/TEX] [TEX]\text{with}[/TEX] [TEX]S_0=P_{3k}(P_3(3))[/TEX]
[/QUOTE]

so basically [TEX]S_i = x^6 - 6x^4 + 9x^2 - 1[/TEX] with [TEX]x= S_{i-1}[/TEX] and [TEX]S_0 =P_{3k}(18)[/TEX]

How far have you tested this?

[QUOTE=CRGreathouse;380359]How far have you tested this?[/QUOTE]

[TEX]\text{For}[/TEX] [TEX]k \in [1 , 109][/TEX] [TEX]\text{with}[/TEX] [TEX]n \in [3 , 300][/TEX]

[B]maxima code to test this conjecture :[/B]

[CODE][LEFT]/* n>2 , k=3,9(mod 10) , k<b^n */
k:109;
for n from 3 thru 300 do
(s:2*chebyshev_t(3*k,chebyshev_t(3,3/2)),N:k*6^n-1,
for i from 1 thru n-2 do (s:mod(2*chebyshev_t(6,s/2),N)),
(if((s=0) and not(primep(N))) then print(n)))$[/LEFT][/CODE]

[QUOTE=CRGreathouse;380359]How far have you tested this?[/QUOTE]

The conjecture seems to be a disguised Frobenius test.

[QUOTE=R.D. Silverman;380368]The conjecture seems to be a disguised Frobenius test.[/QUOTE]

That was my gut reaction as well, but I didn't want to attempt a proof until I knew it worked for a reasonable range.

[QUOTE=science_man_88;380354]so basically [TEX]S_i = x^6 - 6x^4 + 9x^2 - 1[/TEX] with [TEX]x= S_{i-1}[/TEX] and [TEX]S_0 =P_{3k}(18)[/TEX][/QUOTE]
P[SUB]6[/SUB](x) = x^6 - 6x^4 + 9x^2 -[B] 2[/B]
(not -1), because
P[SUB]6[/SUB](x) = P[SUB]2[/SUB](P[SUB]3[/SUB](x)),
where P[SUB]2[/SUB](x) = x^2-2, P[SUB]3[/SUB](x) = x^3-3x

P[SUB]3k[/SUB](x) = P[SUB]k[/SUB](P[SUB]3[/SUB](x)), so
S0 = P[SUB]9k[/SUB](3) = P[SUB]k[/SUB](P[SUB]9[/SUB](3)) = P[SUB]k[/SUB](5778)

Anyway, it looks like a PRP test, but if one wanted to find violations of the test, then for large values it is best to implement P[SUB]2[/SUB](x) and P[SUB]3[/SUB](x) with FFT, and chain them. (P[SUB]2[/SUB](x) is the same as in LL test, so this implementation already exists.)

[QUOTE=Batalov;380378]P[SUB]6[/SUB](x) = x^6 - 6x^4 + 9x^2 -[B] 2[/B]
(not -1), because
P[SUB]6[/SUB](x) = P[SUB]2[/SUB](P[SUB]3[/SUB](x)),
where P[SUB]2[/SUB](x) = x^2-2, P[SUB]3[/SUB](x) = x^3-3x

P[SUB]3k[/SUB](x) = P[SUB]3[/SUB](P[SUB]3[/SUB](...P[SUB]3[/SUB](x))) [TEX]\ \ \ \ [/TEX]{k times}[/QUOTE]

maybe you can tell me where I went wrong then:

[CODE](09:10) gp > (a+b)^6
%1 = a^6 + 6*b*a^5 + 15*b^2*a^4 + 20*b^3*a^3 + 15*b^4*a^2 + 6*b^5*a + b^6
(09:10) gp > (a-b)^6
%2 = a^6 - 6*b*a^5 + 15*b^2*a^4 - 20*b^3*a^3 + 15*b^4*a^2 - 6*b^5*a + b^6
(09:10) gp > %1+%2
%3 = 2*a^6 + 30*b^2*a^4 + 30*b^4*a^2 + 2*b^6[/CODE]

using x^2-4 = b^2

[CODE](09:16) gp > (x^2-4)*(x^2-4)
%5 = x^4 - 8*x^2 + 16
(09:16) gp > (x^2-4)*(x^2-4)*(x^2-4)
%6 = x^6 - 12*x^4 + 48*x^2 - 64[/CODE]

we then get 2*x^6 +30*(x^2-4)*x^4 + 30*(x^4 - 8*x^2 + 16)*x^2 + 2*(x^6 - 12*x^4 + 48*x^2 - 64) = 2*x^6 +30*(x^6-4*x^4) + 30*(x^6 -8*x^4+16*x^2) + 2*(x^6-12*x^4+48*x^2-64) = (2+30+30+2)*x^6 + x* (-120-240-24)*x^4 + (480+96)*x^2-64 = 64*x^6 -384*x^4+576*x^2-64;

multiplying this by 2^-6 gives you:

[CODE](09:35) gp > %9/64
%11 = x^6 - 6*x^4 + 9*x^2 - 1[/CODE]

edit: it looks to me to be like some sort of LL test in that the final condition of N isprime iff [TEX]S_{n-2} \eq 0 \pmod {N}[/TEX]

[QUOTE=science_man_88;380381]maybe you can tell me where I went wrong then:
...we then get 2*x^6 +30*(x^2-4)*x^4 + 30*(x^4 - 8*x^2 + 16)*x^2 + 2*(x^6 - 12*x^4 + 48*x^2 - 64) = 2*x^6 +30*(x^6-4*x^4) + 30*(x^6 -8*x^4+16*x^2) +[COLOR="Red"] 2*[/COLOR](x^6-12*x^4+48*x^2-64) = (2+30+30+2)*x^6 + x* (-120-240-24)*x^4 + (480+96)*x^2[COLOR="red"]-64[/COLOR] = 64*x^6 -384*x^4+576*x^2[COLOR="red"]-64[/COLOR];
[/QUOTE]
There.

[QUOTE=primus;380341][LEFT][B]Definition :[/B] [TEX]\text{Let} [/TEX][TEX] $P_m(x)=2^{-m}\cdot \left(\left(x-\sqrt{x^2-4}\right)^{m}+\left(x+\sqrt{x^2-4}\right)^{m}\right)[/TEX] , [TEX]\text{where}[/TEX] [TEX]m[/TEX] [TEX]\text{and}[/TEX] [TEX]x[/TEX] [TEX] \text{are nonnegative integers .}[/TEX]

[B]Conjecture :[/B] [TEX]\text{Let}[/TEX] [TEX]N=k\cdot 6^n-1[/TEX] [TEX]\text{such that}[/TEX] [TEX]n>2[/TEX] , [TEX]k>0[/TEX] , [TEX]k \equiv 3,9 \pmod{10} [/TEX] [TEX]\text{and}[/TEX] [TEX]k<6^n[/TEX][/LEFT]

[CENTER][TEX]\text{Let}[/TEX] [TEX]S_i=P_6(S_{i-1})[/TEX] [TEX]\text{with}[/TEX] [TEX]S_0=P_{3k}(P_3(3))[/TEX] , [TEX]\text{thus}[/TEX]

[TEX]N[/TEX] [TEX]\text{is prime iff}[/TEX] [TEX]S_{n-2} \equiv 0 \pmod{N}[/TEX][/CENTER]
[/QUOTE]
What is the reason for restriction k ≡ 3,9 (mod 10)?
It is easy to see that k ≡ 0,2,5,7 (mod 10) are not working (many counterexamples), but what about k ≡ 1,4,6,8 (mod 10)? None of them have counterexamples so far.
[CODE]# Pari/GP
allocatemem(1800000000);
KK=7000;
v=vector(KK); v[1]=x; v[2]=x^2-2; for(i=3,KK,v[i]=x*v[i-1]-v[i-2])
P(k,x)=eval(v[k])

t6(k,n)=s=Mod(P(k,5778),k*6^n-1);for(k=1,n-2,s=s*(s^2-3);s=s^2-2);s==0

#for example 1 (mod 10)
forstep(k=1,KK,10,for(n=3,500,if(t6(k,n) && !ispseudoprime(k*6^n-1),print(k" "n))))[/CODE]

[QUOTE=Batalov;380411]What is the reason for restriction k ≡ 3,9 (mod 10)?
It is easy to see that k ≡ 0,2,5,7 (mod 10) are not working (many counterexamples), but what about k ≡ 1,4,6,8 (mod 10)? None of them have counterexamples so far.
[CODE]# Pari/GP
allocatemem(1800000000);
KK=7000;
v=vector(KK); v[1]=x; v[2]=x^2-2; for(i=3,KK,v[i]=x*v[i-1]-v[i-2])
P(k,x)=eval(v[k])

t6(k,n)=s=Mod(P(k,5778),k*6^n-1);for(k=1,n-2,s=s*(s^2-3);s=s^2-2);s==0

#for example 1 (mod 10)
forstep(k=1,KK,10,for(n=3,500,if(t6(k,n) && !ispseudoprime(k*6^n-1),print(k" "n))))[/CODE][/QUOTE]

I think part of it could be that k*6(all powers of 6 are 6 mod 10)-1 = 1,3,7,9 mod 10 gives you that 2,4,8,0 mod 10 divide by 6 mod 10 to give you a prime. which if you look the multiples of 6 mod 10 are 6,2,8,4,0,6 which means k is 0,2,3,4 mod 5. that edit:would be my reasoning for not including 2 of the ones you suggest because both 1 and 6 mod 10 are 1 mod 5.

There are plenty of primes for k ≡ 4,8 (mod 10). The test doesn't produce false positives or negatives (so far!). So why exclude them? It makes an impression of a random statement then. (like "Here is my theorem for all cats that are black or white, but not orange, and only those that were born on Tuesday or Friday".)

For k ≡ 1,6 (mod 10), there are no primes, indeed, because 5 | k*6^n-1. But the test doesn't produce false positives for these either.

P.S. Pari also is supposed to have a polchebyshev() function, but my pari binary is old. So I made up my own P(k,x). Time to rebuild a newer binary...

[QUOTE=Batalov;380411]What is the reason for restriction k ≡ 3,9 (mod 10)?
It is easy to see that k ≡ 0,2,5,7 (mod 10) are not working (many counterexamples), but what about k ≡ 1,4,6,8 (mod 10)? None of them have counterexamples so far.
[CODE]# Pari/GP
allocatemem(1800000000);
KK=7000;
v=vector(KK); v[1]=x; v[2]=x^2-2; for(i=3,KK,v[i]=x*v[i-1]-v[i-2])
P(k,x)=eval(v[k])

t6(k,n)=s=Mod(P(k,5778),k*6^n-1);for(k=1,n-2,s=s*(s^2-3);s=s^2-2);s==0

#for example 1 (mod 10)
forstep(k=1,KK,10,for(n=3,500,if(t6(k,n) && !ispseudoprime(k*6^n-1),print(k" "n))))[/CODE][/QUOTE]

The entire idea is pointless. We know the full factorization of N+1!
Thus, the older methods of Lehmer, Selfridge, Brillhart, et.al. apply
and give a rigorous proof in probabilistic cubic polynomial time.
Just find a primitive root.....

[QUOTE=Batalov;380414]P.S. Pari also is supposed to have a polchebyshev() function, but my pari binary is old. So I made up my own P(k,x). Time to rebuild a newer binary...[/QUOTE]

Yes, absolutely! Lots of fixes, speedups, and new functions added since then.

[QUOTE=R.D. Silverman;380416]The entire idea is pointless. We know the full factorization of N+1!
Thus, the older methods of Lehmer, Selfridge, Brillhart, et.al. apply
and give a rigorous proof in probabilistic cubic polynomial time.
Just find a primitive root.....[/QUOTE]
Well, to play devil's advocate, sometimes a slow but [I]original [/I]method [I]could [/I]be of interest - even if it had no practical value.

In this particular case, though, one must agree. Because Chebyshev's are chainable, this method simply computes P[SUB](N+1)/4[/SUB](3), and why for this subclass of k's "/4" (and not "/2") works can probably be explained (?). With a small modification, it will work for all k, but it will be a PRP test even more obviously once one sees what it does.

[QUOTE=Batalov;380419]Well, to play devil's advocate, sometimes a slow but [I]original [/I]method [I]could [/I]be of interest - even if it had no practical value.[/QUOTE]

Sure. AKS is a great example.

[QUOTE=Batalov;380378]P[SUB]6[/SUB](x) = x^6 - 6x^4 + 9x^2 -[B] 2[/B]
(not -1)[/QUOTE]
I went the same way like you with the calculus up to here, and also didn't find any counterexample as long as my pari didn't step on my patience. This test seems to be some kind of PRP test for a "special base", I see no strong reason why this would be true, but also have no counterexample to give.

p.s. The new pari, after 2.5.0 and including, has the polchebyshev() function (which also evaluates the polynomial in some point, quite fast). You should upgrade to the newer pari, it is much better and faster than the previous versions and it has things for parallel processing (i.e. using all cores of your CPU).

edit: you can use (istead of the forstep with the step 10) something like:
[code]for(n=3,20,forstep(k=3,1000,[B][6,4][/B],N=k*6^n-1; s=...; for(i=1,n-2,s=...)[/code] to go through all k which are 3 or 9 (mod 10).

edit2: very good observation about other k mod 10.