Compositeness test using $S_i=4S_{i-1}-7S_{i-2}+4S_{i-3}$ recurrence relation

107 Views Asked by At

Can you prove or disprove the following claim:

Let $S_i=4S_{i-1}-7S_{i-2}+4S_{i-3}$ with $S_0=0$ , $S_1=1$ , $S_2=1$ . Let $n$ be an odd natural number greater than $2$ such that $\operatorname{gcd}(n,7)=1$. Let $\left(\frac{D}{n}\right)$ be the Jacobi symbol where $D$ represents the discriminant of the characteristic polynomial $x^3-4x^2+7x-4$, and let $\delta(n)=n-\left(\frac{1+\left(\frac{D}{n}\right)}{2}\right)$ , then: $$\text{If } n \text{ is a prime then } S_{\delta(n)} \equiv 0 \pmod{n}$$

You can run this test here. Note that $D=-28$

I have verified this claim for all $n$ up to $100000$ .I was searching for counterexample using the following PARI/GP code:

rec(m,P,Q,R)={s0=0;s1=1;s2=1;l=3;while(l<=m,s=P*s2+Q*s1+R*s0;s0=s1;s1=s2;s2=s;l++);return(s);}
RPT(n1,n2)={forprime(n=n1,n2,d=n-((1+kronecker(-28,n))/2);if(Mod(rec(d,4,-7,4),n)!=0,print(n);break))}

P.S.

Wolfram Alpha doesn't give a nice closed form for $S_i$.

.