20150905, 19:41  #12 
Feb 2004
France
2·461 Posts 
I should read again the documentation of PARI/gp... ;) However, I'm now involved with porting Ruby and Python3, and then Go, on AIX, so I'm fed up reading language documentation. So, I know very basic things about PARI/gp. Some time, when I have time, I'll read more ! ;) Anyway, thanks to help me understand. For now, I do not care about performance of PARI/gp programs.

20150905, 21:58  #13 
Sep 2002
Database er0rr
3934_{10} Posts 
Is there any need to run verification now "mathlove" has proved this composite test?
Does it produce fewer pseudoprimes than basea Fermat PRP tests? Last fiddled with by paulunderwood on 20150905 at 22:15 
20150906, 18:59  #14 
Feb 2004
France
1632_{8} Posts 
About proving the sufficiency, I think that an issue (as I already said) is that s can be equal to sn before i==n1 .
Finding s(n1)==sn only after n1 iterations and not before is important I think. I think that it is important to add a check s!=sn after the computation of s from i=1,n2 . 
20150906, 19:32  #15  
"Forget I exist"
Jul 2009
Dumbassville
20300_{8} Posts 
Quote:


20150907, 17:32  #16  
Feb 2004
France
1110011010_{2} Posts 
Quote:
for(k=1,100,for(c=0,50,CEk2c(k,2*c+1,100))) : produces 34 pseudoprimes. But, if we check that no S(i) is equal to S(sn1) with i=1...n2 , there are less. ... z=0; forstep(i=n,3,1, s=sqr(s)2; if(s==sn, z=1;break)); s=sqr(s)2; if(z==0 && s==sn && ! isprime(N), print("k: ",k," c: ",c," n: ",n))) ? for(k=1,100,for(c=0,50,CEk2c(k,2*c+1,100))) : there are only 13. k: 1 c: 1 n: 3 k: 15 c: 1 n: 3 k: 33 c: 25 n: 79 k: 35 c: 17 n: 83 k: 37 c: 17 n: 92 k: 45 c: 1 n: 3 k: 49 c: 17 n: 80 k: 66 c: 25 n: 78 k: 70 c: 17 n: 82 k: 74 c: 17 n: 91 k: 95 c: 17 n: 77 k: 97 c: 17 n: 48 k: 98 c: 17 n: 79 With c=1, 17, or 25 only, within the limits used for k, c and n. However, there are others, like: 16*2^121+33 . Up to now, for c>0, they all seem to appear when c = 1 mod 8 : 1, 17, 25, 33, 41, 73 . For c<0, it seems to appear only with: c= 5, 29 , like: 8*2^15829 or 11*2^2325 . Last fiddled with by T.Rex on 20150907 at 18:07 Reason: Add note about special values of c and c that create pseudoprimes. 

20150907, 18:42  #17 
Feb 2004
France
2×461 Posts 
for(k=1,100,for(c=0,50,CEk2c(k,2*c+1,100))) : there are only 13 pseudoprimes out of 5588 numbers verifying the test; including 5575 primes: 0.23% of pseudoprimes. Out of a total of 125,000 numbers N tested.
For c<0, there are 1.22% of pseudoprimes (72 out of 5866 numbers verifying the test, including 5794 primes). Out of a total of 125,000 numbers N tested. 
20150907, 21:53  #18 
Feb 2004
France
2×461 Posts 

20150907, 23:26  #19 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
3·5·641 Posts 
A few trivial things about Chebyshev polynomials replace all that "mathlove" wrote in pages of scribbles in a simple way.
One has to admire how he Ponder these: 1. https://en.wikipedia.org/wiki/Lissajous_curve : 2. Lissajous figures where a=1, b=N (with N a natural number) and are Chebyshev polynomials 3. Chebyshev polynomial (one of the definitions) 4. Using renormalized ; in particular {n times}. So, the whole iterated calculation is a calculation of T_{k*2^n}(a) and comparing it to T_c(a) with some a value like . Because of periodicity of cos, the result is obvious. In a way, this is a "Fermat" test z^N = z ("mod" N) in complex plane and with irrational complex with imaginary half of calculations swept under the carpet, projected on real axis only. (A Frobenius PRP test?) primus has been boring people with these trivialities for years now. Search this forum. And always it was "A new conjectured primality test blablabla" . Only in 2015, he finally settled down for them as PRP tests, which they are; but as such, they are trivial! All you need to realize is the property 4, which makes the purpose of iterations painfully obvious: you are calculating the , because Nc = k*b^n, then compare that the. Of course it is! 
20150908, 20:17  #20  
Feb 2004
France
2·461 Posts 
Quote:
Hummm Sometimes, I'm saying myself that I should go back to photography and forget Maths, where I was not so good even before I forgot so many things ! Anyway, thanks for the explanations ! So, you transformed something mysterious into something nearly obvious... I'm sad ! But that's the (Math) rule/law. Anyway, what is surprising me is that, with some modification of his algorithm, I no more can find pseudoprimes (which does NOT mean that there are no more, for sure). In a previous post, I said that, with c>0, pseudoprimes seem to be only N=k*2^n+c where c = 1 mod 8. If you eliminate Ns such that S(i)==S(n1) with i<n1, and then if you eliminate Ns such that N= 0 mod(2*c1) , I no more find pseudoprimes. Last check means that remaining numbers Ns only have 2*c1 as simple factor. The examples I have factored do confirm: they have a unic small factor (never prime) and a very big prime factor. Examples (where N passes the test before my last filter and are pseudoprimes): N=171*2^379+145 = 0 mod 17^2 , and 17^2=2*1451 . factor(171*2^379+145) : 17^2 * 728562182048384077130159586626790436923511614970760313605012778127813410783523249843408253631630684967337087623537 N=307*2^319+105 = 0 mod 11*19 and 11*19 = 2*1051 factor(307*2^319+105) : 11*19 * 1568775167530429175347539865536010763595766240104048804721870271773735540226451313055142011218969 N=471*2^393+73 = 0 mod 5*29 and 5*29 = 2*731 factor(471*2^393+73): 5*29 * 65530155850158078972410448815378156940155788169319195826683219662211477907862726436991538868262118459391723814610133049 N=17*2^399+137 = 0 mod 3*7*13 and 3*7*13 = 2*1371 factor(17*2^399+137): 3*7*13 * 80399721478896421289653161033060809274001828714463003146742141137712471747777106792498115395169126619799183010140489721 The same for a dozen of other similar pseudoprimes. In short, the 2 filters I have added seem to remove all pseudoprimes (which are of a special form and could be used for finding other big primes). That may hide something obvious, for sure. But, the algorithm below no more finds PRPs/pseudoprimes (or I haven't tested with largeenough numbers, for sure. Or my code is wrong.). Would you mind explaining why it seems to work ? 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); z=0; forstep(i=n,3,1,s=sqr(s)2;if(s==sn,z=1;break)); s=sqr(s)2; if(z==0 && s==sn, y=Mod(N,2*c1);if(!isprime(N)&&y!=0, print(k,"*2^",n,"+",c))) ); } for(k=1,100,for(c=0,100,CEk2c(k,2*c+1,200))) for(k=1,100,for(c=101,200,CEk2c(2*k+1,2*c+1,800))) Last fiddled with by T.Rex on 20150908 at 20:19 Reason: orthograph 

20150908, 21:08  #21  
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
3·5·641 Posts 
Quote:
Compare it with the way this thread went, and on to http://www.mersenneforum.org/showthr...943#post380943 This is long ago and well described by A.A. Milne as the character of Tigger. Tigger first claims: 'Tiggers eat evertyhing'. After being presented with honey, he "improves" his theory to 'Tiggers eat evertyhing except honey'. After being presented with acorns, he further "improves" his theory to 'Tiggers eat evertyhing except honey and acorns'. Can you blame anyone for not taking him all too seriously after that? 

20150909, 13:23  #22  
Feb 2004
France
2·461 Posts 
Quote:
However, don't you think that there are other ways for finding new stuff than using pure Math proof ? Is there a place for experimenting ? Years ago, before computers were there, many mathematicians used pen, paper, and figures, for exploring something that looked weird for them at first, before they search for a math proof. Now, we have computers. Remember S. Ramanujan: he never used more than a slate since he was unable to pay for notebooks and paper at first and because he had a wrong idea about what "good" maths are: find a property and PROVE it ; however his findings were remarkable and mathematicians are still studying his findings. However, there was only 1 Srinivasa... Now, back to what I did:  primus published 4 conjectures about a property of primes  I generalized the conjectures into one  someone proved the conjecture and, as you explained, it was not so difficult to prove and it is simply another way to present something already known  however, what about pseudoprimes ?  I found a limited number of pseudoprimes  I used the idea: not only S(n1) must have a special value Sn, but S(i) must not be equal to S(n) when i<n1, because some Sn values are a deadend, like 2 : 2^22=2 , and because we must not enter a cycle with length smaller than n1, with the idea that a minimum of n1 different steps are required for showing a prime, as for Mersenne/Fermat LLT. The other idea is that, for very simple numbers like Mersenne and Fermat, so close to 2^n, about n iterations of X^22 mod N is enough, though for numbers moving away from pure 2^n more steps should be required, which are the P_k and P(c) functions that add more steps before and after the (s^22 mod N) part. The idea is that there must be a minimum of steps to run in order to have something that can be a prime test. A number N being a prime creates a symmetric structure ; running a minimum number of steps in the structure of a number is required in order to discover if the symmetry is broken due to a factor of N. What is magic with LLT for Mersenne/Fermat is this: you run n1 steps in the digraph, from a starting point to a ending point, and bingo! it is a prime. This should work, under more complex conditions, for other numbers, where starting and ending points are more difficult to define since they depend on other characteristics of the number than the power of n : k and c in addition, like primus did.  then, I found that ALL the remaining pseudoprimes I can find (c>0) share the same characteristics: c= 1 mod 8 , and N=0 mod (2*c1) .  and then I shown that ALL these remaining pseudoprimes look strange: only 1 small factor (2c1) and a big prime. They do NOT look like random factors as expected for random exceptions in the theory. They share a property, probably showing something deep and interesting to look at.  and, at the end, filtering this unique class of pseudoprimes, I cannot find more pseudoprimes (up to the limits of my computer). For sure, that does NOT provides a proof. That is only showing "strange" properties that seem to exist with very big numbers and with a very big number of numbers tried. And, as you say, after honey and acorns, there could be ants and mushrooms. Or not. I remember an example from a book of JP Delahaye, where 2 sequences A(n) and B(n) generate coprime numbers ... up to n being very very big where an exception occured. But, in our case, we are using methods that are well known and have already provided good results, like LLT for Mersenne numbers and LLT for Fermat numbers, which are true prime tests. So, we have the expectation to find something that works, under strict conditions. So, I have only used 2 filters. Remind also that, for c<0, I found that all pseudoprimes I've found have the same structure. For sure, there could be another kind of pseudoprimes with much higher values for: k, n, or c . And, in that case, the conjecture will be the Tiger you are talking about. Last fiddled with by T.Rex on 20150909 at 14:02 Reason: english 

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 