mersenneforum.org  

Go Back   mersenneforum.org > Math Stuff > Computer Science & Computational Number Theory

Reply
 
Thread Tools
Old 2014-08-14, 05:45   #1
primus
 
Jul 2014
Montenegro

328 Posts
Default 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}

primus is offline   Reply With Quote
Old 2014-08-14, 12:46   #2
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by primus View Post
\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)
science_man_88 is offline   Reply With Quote
Old 2014-08-14, 14:04   #3
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

586210 Posts
Default

How far have you tested this?
CRGreathouse is offline   Reply With Quote
Old 2014-08-14, 14:59   #4
primus
 
Jul 2014
Montenegro

2·13 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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)))$
primus is offline   Reply With Quote
Old 2014-08-14, 16:17   #5
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

25×233 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
How far have you tested this?
The conjecture seems to be a disguised Frobenius test.
R.D. Silverman is offline   Reply With Quote
Old 2014-08-14, 17:13   #6
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

2×3×977 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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.
CRGreathouse is offline   Reply With Quote
Old 2014-08-14, 17:52   #7
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(3,3^1118781+1)/3

100011011001012 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
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
Batalov is offline   Reply With Quote
Old 2014-08-14, 18:08   #8
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by Batalov View Post
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
science_man_88 is offline   Reply With Quote
Old 2014-08-14, 18:15   #9
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(3,3^1118781+1)/3

13×17×41 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
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 is offline   Reply With Quote
Old 2014-08-14, 22:00   #10
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(3,3^1118781+1)/3

13×17×41 Posts
Question

Quote:
Originally Posted by primus View Post
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))))
Batalov is offline   Reply With Quote
Old 2014-08-14, 22:26   #11
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts
Default

Quote:
Originally Posted by Batalov View Post
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
science_man_88 is offline   Reply With Quote
Reply

Thread Tools


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

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

Mon Jul 13 05:07:36 UTC 2020 up 110 days, 2:40, 0 users, load averages: 1.93, 1.98, 1.93

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.