20160722, 15:46  #1 
(loop (#_fork))
Feb 2006
Cambridge, England
3·19·113 Posts 
Silly Lucaslike sequences of primes
Consider the sequence n[1]=x, n[2]=n[1]^2+K, n[3]=n[2]^2+K ... for arbitrary x and K.
For K=4 you can test that any n[1] will have some n[t] divisible by 13 for t<=6; n[1]=306167 does have n[t] prime for t=1..5 (as does n[1]=48639197) For K=12 the smallest analogous obstruction is that some n[t] will be divisible by 31 for t<=11, so we can potentially have quite long sequences of large primes. n[1]=564103, 3424241, 6780857 ... give five primes. Can you find an n[1] giving six? For K=18 the smallest obstruction appears to be at p=257 and the bound on sequence length at p=257 is 45; for K={54, 88} I cannot find an obstruction. There are some K with only inconvenient obstructions; K=64 is moderately interesting in that there are obstructions [761, 84], [937, 92], [1597, 72] and [2129, 107]; K=58 has [28411, 418]; K=70 has obstruction [3347,100]; K=60 gives [45677,658] K=22, n[1]=1874941 gives six primes. Code:
forprime(p=2,2^30,for(Ki=1,6,K=[4,12,18,22,40,54][Ki];k=1;s=p;while(isprime(s),s=s^2+K;k=1+k);if(k>5,print([K,p,k])))) Any odd K has obstruction [2,1]; 6n+2 has obstruction [3,1]; 5n+1 has obstruction [5,2] Last fiddled with by fivemack on 20160725 at 10:38 
20160722, 17:38  #2 
"Forget I exist"
Jul 2009
Dumbassville
20C0_{16} Posts 

20160722, 18:24  #3 
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
3×1,973 Posts 
I thought so as well sm88.
I have begun a search for K=2. This K has the nice form of factors property as noted in the link above. I have modified Batalovs program to factor these candidates. I suppose it wouldn't be a huge job to replace the nice factor form with the general primes. I have found an example for K=2 where t=3 to 6 are prime. Currently searching t=2 to 6. None for x<1e6. 
20160722, 20:38  #4  
"Forget I exist"
Jul 2009
Dumbassville
20300_{8} Posts 
Quote:
n[1] = 0 mod 13 leads to a loop length of 1 n[1] = 1 or 1 mod 13 leads to a loop of 5,3,0,4,7,1 n[1] = 2 or 2 mod 13 leads to a loop of 8,* 3,0,4,7,1,5*,... like in knitting patterns repeat between * n[1] = 3 or 3 covered above 4 or 4 covered above, 5 or 5 covered above, 6 or 6 start from 7 above, Last fiddled with by science_man_88 on 20160722 at 20:39 

20160724, 06:51  #5  
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
3·1,973 Posts 
Quote:
((((1383068639^22)^22)^22)^22)^22 ((((2524497709^22)^22)^22)^22)^22 I need to improve the program if I am going to search for 7. I am not doing any factoring for t=1 currently. 

20160724, 11:16  #6 
"Forget I exist"
Jul 2009
Dumbassville
8384_{10} Posts 
I'm guessing you are both aware that K=(a^2) can be avoided as then you have n[2]= x^2a^2 = (x+a)*(xa) so all K that are negatives of perfect squares are out for long sequences of primes. Also only factors of the sequence are the ones with K as a modular quadratic residue.edit: in fact there are at least 3 forms of K that can be deleted K=(a^2) K=(2ax+a^2) and K=(2ax+a^2) the latter two allow factoring as (x+a)^2 and (xa)^2 edit2: okay exception of the fact that (x+a) or (xa) may be 1 like in the case x=2 a=1 2^21^2 =41 =3 = (2+1)*(21) = 3*1.
Last fiddled with by science_man_88 on 20160724 at 11:49 
20160724, 14:30  #7  
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
3·1,973 Posts 
Quote:


20160724, 18:54  #8 
"Forget I exist"
Jul 2009
Dumbassville
2^{6}×131 Posts 
and I only continue to post modular arithmetic stuff because so much of what people post relates to it, to each their own. edit: using the logic I used in a post in this thoead I realized that I've cut the work for you by 75% as the symmetry you thought about does exist in that you get the two for one of +/ value mod r. it also cuts the work by 75% or more for checking if a prime divides any values x^2+k in theory. it can only go to r\2 before it runs out of unique quadratic residues to base it on, it can only of up to a value of x=r\2 in theory as x^2 mod prime r will not be unique after that and k may also be able to be cut at times. edit: found the k cut k can be limited to less than 2*x+1 because at that point it has another way of expressing itself as a whole with different x and k values.
Last fiddled with by science_man_88 on 20160724 at 19:48 
20160724, 21:10  #9  
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
3×1,973 Posts 
Quote:
I suppose it may work if you go large enough but currently I am sieving ranges of 1000 and only expect to do a few 10k at best. Sieving would need a huge increase in speed in order to actually help now. Each bit removes very few candidates. 

20160724, 21:50  #10  
"Forget I exist"
Jul 2009
Dumbassville
2^{6}×131 Posts 
Quote:


20170201, 16:00  #11 
"99(4^34019)99 palind"
Nov 2016
(P^81993)SZ base 36
5×13×47 Posts 
Are there any research for primes in Lucas U(P, Q) and V(P, Q) sequences? i.e.
a(0)=0, a(1)=1, a(n+2)=P*a(n+1)Q*a(n) for all n>=0 and a(0)=2, a(1)=P, a(n+2)=P*a(n+1)Q*a(n) for all n>=0 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
LucasLehmer Primes  henryzz  And now for something completely different  42  20190603 14:09 
Lucas and Fibonacci primes  Batalov  And now for something completely different  9  20170628 16:56 
LucasLehmer sequences starting with s0 other than 4  GP2  Math  6  20160521 17:00 
Need help with Lucas Sequences...  WraithX  Programming  11  20100923 23:22 
factors of lucas sequences  jocelynl  Math  2  20100923 21:32 