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

primus · 2014-08-14, 05:45

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

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

$\text{Let}$ $S_i=P_6(S_{i-1})$ $\text{with}$ $S_0=P_{3k}(P_3(3))$ , $\text{thus}$

$N$ $\text{is prime iff}$ $S_{n-2} \equiv 0 \pmod{N}$

Maxima Implementation of the test

science_man_88 · 2014-08-14, 12:46

Quote:

Originally Posted by primus

$\text{Let}$ $S_i=P_6(S_{i-1})$ $\text{with}$ $S_0=P_{3k}(P_3(3))$

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

CRGreathouse · 2014-08-14, 14:04

How far have you tested this?

primus · 2014-08-14, 14:59

Quote:

Originally Posted by CRGreathouse

How far have you tested this?

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

maxima code to test this conjecture :

Code:

/* 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)))$

R.D. Silverman · 2014-08-14, 16:17

Quote:

Originally Posted by CRGreathouse

How far have you tested this?

The conjecture seems to be a disguised Frobenius test.

CRGreathouse · 2014-08-14, 17:13

Quote:

Originally Posted by R.D. Silverman

The conjecture seems to be a disguised Frobenius test.

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.

Batalov · 2014-08-14, 17:52

Quote:

Originally Posted by science_man_88

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

P₆(x) = x^6 - 6x^4 + 9x^2 - 2
(not -1), because
P₆(x) = P₂(P₃(x)),
where P₂(x) = x^2-2, P₃(x) = x^3-3x

P_3k(x) = P_k(P₃(x)), so
S0 = P_9k(3) = P_k(P₉(3)) = P_k(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₂(x) and P₃(x) with FFT, and chain them. (P₂(x) is the same as in LL test, so this implementation already exists.)

science_man_88 · 2014-08-14, 18:08

Quote:

Originally Posted by Batalov

P₆(x) = x^6 - 6x^4 + 9x^2 - 2
(not -1), because
P₆(x) = P₂(P₃(x)),
where P₂(x) = x^2-2, P₃(x) = x^3-3x

P_3k(x) = P₃(P₃(...P₃(x))) $\ \ \ \$ {k times}

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

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

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

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

Batalov · 2014-08-14, 18:15

Quote:

Originally Posted by science_man_88

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) + 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;

There.

Batalov · 2014-08-14, 22:00

Quote:

Originally Posted by primus

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

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

$\text{Let}$ $S_i=P_6(S_{i-1})$ $\text{with}$ $S_0=P_{3k}(P_3(3))$ , $\text{thus}$

$N$ $\text{is prime iff}$ $S_{n-2} \equiv 0 \pmod{N}$

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))))

science_man_88 · 2014-08-14, 22:26

Quote:

Originally Posted by Batalov

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))))

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.

2014-08-14, 05:45	#1
primus Jul 2014 Montenegro 2×13 Posts	Conjectured Primality Test for Specific Class of k6^n-1 Definition : $\text{Let}$ $$P_m(x)=2^{-m}\cdot \left(\left(x-\sqrt{x^2-4}\right)^{m}+\left(x+\sqrt{x^2-4}\right)^{m}\right)$ , $\text{where}$ $m$ $\text{and}$ $x$ $\text{are nonnegative integers .}$ Conjecture : $\text{Let}$ $N=k\cdot 6^n-1$ $\text{such that}$ $n>2$ , $k>0$ , $k \equiv 3,9 \pmod{10}$ $\text{and}$ $k<6^n$ $\text{Let}$ $S_i=P_6(S_{i-1})$ $\text{with}$ $S_0=P_{3k}(P_3(3))$ , $\text{thus}$ $N$ $\text{is prime iff}$ $S_{n-2} \equiv 0 \pmod{N}$ Maxima Implementation of the test

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Lucasian Pseudoprimality Hypothesis for Specific Class of k 2^n-1	primus	Miscellaneous Math	14	2015-07-04 15:42
Pseudoprimality Hypothesis for Specific Class of Generalized Fermat Numbers	primus	Miscellaneous Math	1	2015-03-25 22:18
Conjectured Primality Test for Specific Class of Mersenne Numbers	primus	Miscellaneous Math	1	2014-10-12 09:25
Disproven Primality Test for Specific Class of kb^n-1	primus	Computer Science & Computational Number Theory	8	2014-08-21 15:16
Conjectured Primality Test for 2^p-1, (2^p+1)/3 and (2^2^n+1)	T.Rex	Math	75	2007-09-04 07:53

2014-08-14, 14:04	#3
CRGreathouse Aug 2006 3×1,993 Posts	How far have you tested this?