20150904, 21:23  #1 
Feb 2004
France
911 Posts 
Conjectured compositeness tests for N=k⋅2n±c by Predrag
Predrag (not sure he wants his name to appear since he published as "MathBot") has published a question in StackExchange about a set of 4 conjectures he has built dealing with: "Conjectured compositeness tests for N=k⋅2n±c".
What he proposes seems to me already VERY great, since the 4 conjectures cover ALL numbers , c odd for sure, with simple but powerful definitions using the LLT () but also higher LLT functions (Chebichev) for the seed and for the last term of the sequence, after iterations. However, I've shown that the 4 conjectures can be generalized into only ONE conjecture which handles all kinds of these numbers. I've provided a PARI/gp for finding counterexamples. For sure, it is ONLY a conjecture. But this conjecture looks really powerful. I'd like to know if someone is aware about such a general conjecture. I should know, but, after years without looking at such research papers, I do not remember. However, as said RDS, I'm not a PhD, so I'd like other people to have a look and add comments. I've read other papers of Pedrag: he has played first with smaller examples. So, I think he then spent some time for grouping several examples into a greater conjecture. So:1) he made experiments, 2) he generalized his findings in something more general. Good work ! And, for sure, what I published recently was only children' game compared to Predrag's conjectures. Here is the PARI/gp program I've written based on work of Predrag, with code for searching counterexamples: Code:
CEk2c(k,c,g)= { a=6; if(c>0,s=1,s=1;c=c); for(n=2*c+1,g, N=k*2^n+s*c; e=c%4; if(e==1,e=1,e=1); d=((ce)%8)/4; B=((1)^d)*s; A=(cB)/2; s0=Mod(2*polchebyshev(k,1,a/2),N); sn=Mod((1)^d*2*polchebyshev(A,1,a/2),N); my(s=s0); for(i=1,n1,s=Mod(s^22,N)); if(s!=sn && isprime(N),print("k: ",k," c: ",c," n: ",n)) ) } for(k=1,100,for(c=0,50,CEk2c(k,2*c+1,1000))) for(k=1,100,for(c=0,50,CEk2c(k,(2*c+1),1000))) Here is the final conjecture I've built after grouping Predrag's 4 conjectures all together. That does not make the task for proving it easier ! But that's so beautiful. And, for sure, we have the usual question: is this only a PRP tool or a true primality test ? Anyway, this conjecture shows how powerful are the ideas that Edouard Lucas discovered about 140 years ago. Last fiddled with by T.Rex on 20150904 at 21:29 
20150904, 21:33  #2 
Feb 2004
France
911 Posts 
Thanks to primus to have warned me about Predrag's publication in StackExchange.

20150904, 22:09  #3 
"Serge"
Mar 2008
Phi(3,3^1118781+1)/3
5·1,811 Posts 
You didn't even consider that they are one and the same?

20150905, 01:28  #4  
"Forget I exist"
Jul 2009
Dumbassville
2^{6}×131 Posts 
Quote:
Code:
CEk2c(k,c,g)= { a=6; h=a/2; if(c>0,s=1,s=1;c*=1); for(n=c<<1+1,g, N=k<<n+s*c; e=c%4; if(e==1,,e=1); d=((ce)%8)/4; f=((1)^d) B=f*s; A=(cB)/2; s0=Mod(polchebyshev(k,1,h)<<1,N); sn=Mod(f*polchebyshev(A,1,h)<<1,N); my(s=s0); forstep(i=n,2,1,s=sqr(s)2); if(s!=sn && isprime(N),print("k: ",k," c: ",c," n: ",n)) ) } for(k=1,100,for(c=0,50,CEk2c(k,2*c+1,1000))) for(k=1,100,for(c=0,50,CEk2c(k,(2*c+1),1000))) 

20150905, 10:26  #5 
Feb 2004
France
911 Posts 

20150905, 10:30  #6  
Feb 2004
France
911 Posts 
Quote:


20150905, 12:23  #7 
Jun 2003
11×421 Posts 

20150905, 13:40  #8 
"Forget I exist"
Jul 2009
Dumbassville
10000011000000_{2} Posts 

20150905, 13:41  #9 
Nov 2003
16426_{8} Posts 

20150905, 14:45  #10 
"Forget I exist"
Jul 2009
Dumbassville
2^{6}·131 Posts 
maybe because they care for other potential groupings around a number like sexy primes or cousin primes ?
Last fiddled with by science_man_88 on 20150905 at 14:46 
20150905, 15:09  #11  
"Serge"
Mar 2008
Phi(3,3^1118781+1)/3
5×1,811 Posts 
Quote:
Think about it. If he wanted to post it himself, under three different names (and on ten other boards, just like inimitable Don Blazys), he would have! And he had already done that. Now he used you to post this tripe once again. Don't you feel used? 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Compositeness test  jnml  Miscellaneous Math  10  20180127 16:20 
Conjectured Primality Test for Specific Class of Mersenne Numbers  primus  Miscellaneous Math  1  20141012 09:25 
Conjectured Primality Test for Specific Class of k6^n1  primus  Computer Science & Computational Number Theory  16  20140815 01:15 
Conjectured Primality Test for 2^p1, (2^p+1)/3 and (2^2^n+1)  T.Rex  Math  75  20070904 07:53 
PRP => LLtests?  Holmes  Math  1  20050513 17:18 