mersenneforum.org Conjectured Primality Test for Specific Class of k6^n-1
 Register FAQ Search Today's Posts Mark Forums Read

 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
2014-08-14, 12:46   #2
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

839210 Posts

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

 2014-08-14, 14:04 #3 CRGreathouse     Aug 2006 5,981 Posts How far have you tested this?
2014-08-14, 14:59   #4
primus

Jul 2014
Montenegro

110102 Posts

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

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

"Bob Silverman"
Nov 2003
North of Boston

23·3·311 Posts

Quote:
 Originally Posted by CRGreathouse How far have you tested this?
The conjecture seems to be a disguised Frobenius test.

2014-08-14, 17:13   #6
CRGreathouse

Aug 2006

5,981 Posts

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.

2014-08-14, 17:52   #7
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

33×367 Posts

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)$
P6(x) = x^6 - 6x^4 + 9x^2 - 2
(not -1), because
P6(x) = P2(P3(x)),
where P2(x) = x^2-2, P3(x) = x^3-3x

P3k(x) = Pk(P3(x)), so
S0 = P9k(3) = Pk(P9(3)) = Pk(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 P2(x) and P3(x) with FFT, and chain them. (P2(x) is the same as in LL test, so this implementation already exists.)

Last fiddled with by Batalov on 2014-08-14 at 18:04

2014-08-14, 18:08   #8
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

23·1,049 Posts

Quote:
 Originally Posted by Batalov P6(x) = x^6 - 6x^4 + 9x^2 - 2 (not -1), because P6(x) = P2(P3(x)), where P2(x) = x^2-2, P3(x) = x^3-3x P3k(x) = P3(P3(...P3(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}$

Last fiddled with by science_man_88 on 2014-08-14 at 18:10

2014-08-14, 18:15   #9
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

33×367 Posts

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.

2014-08-14, 22:00   #10
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

33×367 Posts

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

2014-08-14, 22:26   #11
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

20C816 Posts

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.

Last fiddled with by science_man_88 on 2014-08-14 at 22:29 Reason: added would be

 Similar Threads Thread Thread Starter Forum Replies Last Post primus Miscellaneous Math 14 2015-07-04 15:42 primus Miscellaneous Math 1 2015-03-25 22:18 primus Miscellaneous Math 1 2014-10-12 09:25 primus Computer Science & Computational Number Theory 8 2014-08-21 15:16 T.Rex Math 75 2007-09-04 07:53

All times are UTC. The time now is 07:27.

Fri Aug 19 07:27:05 UTC 2022 up 1 day, 4:55, 0 users, load averages: 1.25, 1.24, 1.13