Silly Lucas-like sequences of primes

[fivemack]

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.

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]))))

This is rather like the other generalisation of the Fermat problem: finding n such that n+1, n^2+1, n^4+1, n^8+1, n^16+1, n^32+1 ... are all prime.

Any odd K has obstruction [2,1]; 6n+2 has obstruction [3,1]; 5n+1 has obstruction [5,2]

[science_man_88]

so similar to:

http://mersenneforum.org/showthread.php?t=21397

[henryzz]

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.

[science_man_88]

Originally Posted by fivemack

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)

well yeah you are basically guaranteed except cases where the whole of the plane of values doesn't allow it but that would make it rare for exceptions; this comes about in the fact that there are 7 unique squares mod 13 one of which is 0 so by the sixth step ( n[6]) it has to happen or it can't ever happen because we have the cases:

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,

[henryzz]

Originally Posted by henryzz

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.

I have found a couple of sequences of t=1 to 6:
((((1383068639^2-2)^2-2)^2-2)^2-2)^2-2
((((2524497709^2-2)^2-2)^2-2)^2-2)^2-2
I need to improve the program if I am going to search for 7. I am not doing any factoring for t=1 currently.

[science_man_88]

I'm guessing you are both aware that K=-(a^2) can be avoided as then you have n[2]= x^2-a^2 = (x+a)*(x-a) 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 (x-a)^2 edit2: okay exception of the fact that (x+a) or (x-a) may be 1 like in the case x=2 a=1 2^2-1^2 =4-1 =3 = (2+1)*(2-1) = 3*1.

[henryzz]

Originally Posted by science_man_88

I'm guessing you are both aware that K=-(a^2) can be avoided as then you have n[2]= x^2-a^2 = (x+a)*(x-a) 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 (x-a)^2 edit2: okay exception of the fact that (x+a) or (x-a) may be 1 like in the case x=2 a=1 2^2-1^2 =4-1 =3 = (2+1)*(2-1) = 3*1.

I am only doing K=-2 because of the special factor forms. I will allow others to do further.

[science_man_88]

Originally Posted by henryzz

I am only doing K=-2 because of the special factor forms. I will allow others to do further.

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.

[henryzz]

Originally Posted by science_man_88

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.

You mean you can calculate 1/4 of the residues and get all of them. I doubt this makes it any more practical as you still get a stupid number of residues.
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.

[science_man_88]

Originally Posted by henryzz

You mean you can calculate 1/4 of the residues and get all of them. I doubt this makes it any more practical as you still get a stupid number of residues.
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.

technically if you can calculate the loop needed you might be able to use one line to figure out most if not all the rest so r\2 total may be possible.

[sweety439]

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