 mersenneforum.org > Math Silly Lucas-like sequences of primes
 Register FAQ Search Today's Posts Mark Forums Read  2016-07-22, 15:46 #1 fivemack (loop (#_fork))   Feb 2006 Cambridge, England 22×1,613 Posts Silly Lucas-like sequences of primes Consider the sequence n=x, n=n^2+K, n=n^2+K ... for arbitrary x and K. For K=4 you can test that any n will have some n[t] divisible by 13 for t<=6; n=306167 does have n[t] prime for t=1..5 (as does n=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=564103, 3424241, 6780857 ... give five primes. Can you find an n 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=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])))) 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] Last fiddled with by fivemack on 2016-07-25 at 10:38   2016-07-22, 17:38 #2 science_man_88   "Forget I exist" Jul 2009 Dumbassville 20C016 Posts so similar to: http://mersenneforum.org/showthread.php?t=21397   2016-07-22, 18:24 #3 henryzz Just call me Henry   "David" Sep 2007 Liverpool (GMT/BST) 135008 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.   2016-07-22, 20:38   #4
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts Quote:
 Originally Posted by fivemack For K=4 you can test that any n will have some n[t] divisible by 13 for t<=6; n=306167 does have n[t] prime for t=1..5 (as does n=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) it has to happen or it can't ever happen because we have the cases:

n = 0 mod 13 leads to a loop length of 1
n = 1 or -1 mod 13 leads to a loop of 5,3,0,4,7,1
n = 2 or -2 mod 13 leads to a loop of 8,* 3,0,4,7,1,5*,... like in knitting patterns repeat between *
n = 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 2016-07-22 at 20:39   2016-07-24, 06:51   #5
henryzz
Just call me Henry

"David"
Sep 2007
Liverpool (GMT/BST)

26×3×31 Posts Quote:
 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.   2016-07-24, 11:16 #6 science_man_88   "Forget I exist" Jul 2009 Dumbassville 26×131 Posts I'm guessing you are both aware that K=-(a^2) can be avoided as then you have n= 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. Last fiddled with by science_man_88 on 2016-07-24 at 11:49   2016-07-24, 14:30   #7
henryzz
Just call me Henry

"David"
Sep 2007
Liverpool (GMT/BST)

595210 Posts Quote:
 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= 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.   2016-07-24, 18:54   #8
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts Quote:
 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.

Last fiddled with by science_man_88 on 2016-07-24 at 19:48   2016-07-24, 21:10   #9
henryzz
Just call me Henry

"David"
Sep 2007
Liverpool (GMT/BST)

26·3·31 Posts Quote:
 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.   2016-07-24, 21:50   #10
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts Quote:
 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.   2017-02-01, 16:00 #11 sweety439   "99(4^34019)99 palind" Nov 2016 (P^81993)SZ base 36 22×17×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 Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post henryzz And now for something completely different 42 2019-06-03 14:09 Batalov And now for something completely different 9 2017-06-28 16:56 GP2 Math 6 2016-05-21 17:00 WraithX Programming 11 2010-09-23 23:22 jocelynl Math 2 2010-09-23 21:32

All times are UTC. The time now is 07:59.

Tue Jan 18 07:59:30 UTC 2022 up 179 days, 2:28, 0 users, load averages: 1.24, 1.21, 1.15