 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 : , Conjecture : , , , Maxima Implementation of the test   2014-08-14, 12:46   #2
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

838410 Posts Quote:
 Originally Posted by primus so basically with and   2014-08-14, 14:04 #3 CRGreathouse   Aug 2006 135338 Posts How far have you tested this?   2014-08-14, 14:59   #4
primus

Jul 2014
Montenegro

2·13 Posts Quote:
 Originally Posted by CRGreathouse How far have you tested this?

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

22×5×373 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

3×1,993 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

27·7·11 Posts Quote:
 Originally Posted by science_man_88 so basically with and
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

20C016 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

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

27×7×11 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

985610 Posts Quote:
 Originally Posted by primus Definition : , Conjecture : , , ,
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=x; v=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

100000110000002 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=x; v=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   Thread Tools Show Printable Version Email this Page 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 04:45.

Fri Jul 1 04:45:37 UTC 2022 up 78 days, 2:46, 0 users, load averages: 1.31, 1.40, 1.43