20160624, 17:18  #1 
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
5,857 Posts 
LucasLehmer Primes
I have been thinking for a while that a nice form to test for primes might be the numbers encountered during a lucaslehmer test.
Let LL(x,n) = LL(x,n1)^22 with LL(x,0)=x. It will be possible to primality test some of these numbers. For example: LL(x,4) + 1= (x1) (x+1) (x^23) (x^44 x^2+1) (x^88 x^6+20 x^416 x^2+1) which should provide enough prime factors for some to be proven prime. This doesn't work perfectly for example LL(425,10) only has ~8.7% factored. It would be possible to extend that another 152 digits with snfs(and another 320 if someone is feeling adventurous) The thing that makes these numbers nice is that there are strict restrictions on the form that their factors can take. The factors of LL(x,10) seem to take the form k*2^12+1 for example(proof would be useful). This would imply that it should be possible to sieve them deeper and once sieved they should more likely to be prime than general numbers. Also P1 and P+1 should be strong factoring tools for these numbers. I would appreciate it if anyone has any further information on these numbers. There are things like LL(3,n)=Lucas(2^(n+1)). It would be nice to prove the form of the factors and estimate the likelihood of one of these candidates being prime. 
20160624, 17:47  #2  
"Forget I exist"
Jul 2009
Dumbassville
2^{6}×131 Posts 
Quote:
if x is divisible by 3 we get 0,1,2,2,2,2,2,2,2,2 ... mod 3 and none can divide by 3. and in general if an odd prime p divides one of them it can no longer divide any of the others as it will enter the loop 0,P2,2,2,2,2,..... in this form of the test or 0,P1,1,1,1,1,1,... in the versions where the common factor of 2 is taken out. edit: we can also show that any polynomials we need to factor that have an even number odd coefficients must always divide by 2 if the constant term is even and can only not divide by 2 if the constant term is odd in which case it is odd for all even values of a variable in all terms.( because then the parity arguments can come into play). Last fiddled with by science_man_88 on 20160624 at 18:00 

20160624, 18:19  #3  
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
5857_{10} Posts 
Quote:


20160624, 18:26  #4  
"Forget I exist"
Jul 2009
Dumbassville
2^{6}·131 Posts 
Quote:
LL(x,1) = x LL(x,2) = x^22 in this form where LL(x,n+1)=LL(x,n)^22 there will only be one odd coefficient therefore it's only odd if x is odd. all x values that are the same mod a prime p can be done all at once as they will give the same modular remainder mod p so like in factoring mersennes you only have to test the first p1 x values to test for division by p before p can't divide any of them. edit2: and of course any x values that are 2 less than a square are already in a lower sequence so the can be skipped. Last fiddled with by science_man_88 on 20160624 at 18:46 

20160627, 14:20  #5 
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
13341_{8} Posts 
I am currently using pfgw's modular factoring to find the first prime for each n.
n=1012: Code:
(((((((((425^22)^22)^22)^22)^22)^22)^22)^22)^22)^22 ((((((((((1685^22)^22)^22)^22)^22)^22)^22)^22)^22)^22)^22 (((((((((((1417^22)^22)^22)^22)^22)^22)^22)^22)^22)^22)^22)^22 There would be a large speedup with a proper sieve. 
20160627, 14:23  #6  
"Forget I exist"
Jul 2009
Dumbassville
2^{6}·131 Posts 
Quote:


20160628, 08:49  #7  
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
5,857 Posts 
Quote:
4, 9, 10, 11, 20, 21, 22, 27 It appears that there is a mirror image as I expected. Not sure how I would go about finding those without trial division. The problem with sieving these numbers like that is that the numbers will often be larger than the range we are sieving. This means that we are basically trial dividing. Another approach is needed. After an overnight search ((((((((((((9003^22)^22)^22)^22)^22)^22)^22)^22)^22)^22)^22)^22)^22 was found for n=13. I am afraid your maths escapes me science_man_88. 

20160628, 12:17  #8  
"Forget I exist"
Jul 2009
Dumbassville
10000011000000_{2} Posts 
Quote:
examples from the LL test: 4,14,194, for odd prime r =3 we get the modular remainders 1,2,2 since we've tested the first 3 values and have not got 0 we know that none of the LL test numbers will divide by 3. furthermore we have learned that LLP({x:x%3==1},n) for n={1,2,3} all give the pattern 1,2,2 when mod 3. we know that for p=13 2^p1 divides into LLP(4,11) that means it can not divide into any LLP(4,k) where k>11. this is just using basic math of course. or to show it with true data: Code:
%10 = [1 1 1 1 1] [2 2 2 2 2] [3 7 47 2207 4870847] [4 14 194 37634 1416317954] [5 23 527 277727 77132286527] okay so lets test for division by 3 in this data 1= 1 mod 3 so what I'm saying is based on modular arithmetic we can prove that 4= 1 mod 3 as well, going forward we have 1 = 2 mod 3 so from that same thing we can prove 14 = 2 mod 3, and the same thing happens with 1 and 194 2 is always 2 mod 3 and so we can use modular arithmetic to show 5=2 mod 3, 23 = 2 mod 3, 527 =2 mod 3, and in fact that whole last row will be 2 mod 2. then we test the row starting with 3 well 3 divides by 3 so that's a 0 mod 3 answer and 0^22 is 2 ( aka 1) mod 3 so 7 is 1 mod 3 and 1^22 = 1 ( aka 2) mod 3 and 2^22 = 2 mod 3 as well so that residue will happen again and again through the whole row. if we were to look at the large scale data we would get these three row repeating going down: 1,2,2,2,2,... 2,2,2,2,2,... 0,1,2,2,2,... so only values with x that divides by 3 will be 0 mod 3 (and only for n=1) the rest are safe from elimination as we know 3 doesn't divide them. and we can do this with any prime p all we have to do is check the first p rows and first p columns, if one in that area of the table doesn't divide by p then none of the values will for the whole extent of the table. Last fiddled with by science_man_88 on 20160628 at 13:08 

20160628, 16:54  #9  
"Forget I exist"
Jul 2009
Dumbassville
20300_{8} Posts 
Quote:
Code:
my(r=11,a=[1..r1],b=vector(#a,i,[]),c=[%36,%37,%38,%39,%40,%41,%42,%43,%44,%45,%46,%47]);for(y=1,#a,if(a[y]==0,,for(z=1,#c,if(subst(c[z],x,y)%r,,b[z]=concat(b[z],y);a[y]=0))));b Code:
LLP(x,n) = if(n==1,x,my(s=self());s(x,n1)^22) Last fiddled with by science_man_88 on 20160628 at 17:54 

20160629, 09:17  #10 
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
13341_{8} Posts 
Just thought I would point out that we don't need to test the small primes normally as we know the form of the factors is k*2^(n+2)+1 or 2. This means that the factors start at over 1e4 and will finish at over 1e8 and if we get it faster maybe 1e10.
As we are only looking at a range of around 10100k values of x this means that we can't really sieve. Quickly identifying which candidates can divide LL(x,n) is the best we can hope for. Note n will remain fixed. All methods need to be extendable to very large factors and efficient for a small range(I suppose range will increase as n increases but so will the size of the factors). Nothing for n=14 yet. I suspect a major speed improvement over the pfgw trial division may be code that uses the form of the factor when doing the trial division. I suspect that pfgw uses the k*2^(n+2)+1 form to generate the factors but divides using generic methods. It may be worth looking at how people factor fermat numbers as that is a similar form of factor. 
20160629, 10:50  #11  
"Forget I exist"
Jul 2009
Dumbassville
2^{6}×131 Posts 
Quote:
Last fiddled with by science_man_88 on 20160629 at 11:02 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
LucasLehmer test  Mathsgirl  Information & Answers  23  20141210 16:25 
lucaslehmer theorem  Robot2357  Math  6  20130615 03:10 
lucas lehmer outstretch  science_man_88  Miscellaneous Math  7  20100714 12:35 
LucasLehmer Test  storm5510  Math  22  20090924 22:32 
LucasLehmer  Dougal  Information & Answers  9  20090206 10:25 