mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2016-07-22, 15:46   #1
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

3·19·113 Posts
Default Silly Lucas-like 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]))))
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
fivemack is offline   Reply With Quote
Old 2016-07-22, 17:38   #2
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

20C016 Posts
Default

so similar to:

http://mersenneforum.org/showthread.php?t=21397
science_man_88 is offline   Reply With Quote
Old 2016-07-22, 18:24   #3
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

3×1,973 Posts
Default

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.
henryzz is offline   Reply With Quote
Old 2016-07-22, 20:38   #4
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

203008 Posts
Default

Quote:
Originally Posted by fivemack View Post
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,

Last fiddled with by science_man_88 on 2016-07-22 at 20:39
science_man_88 is offline   Reply With Quote
Old 2016-07-24, 06:51   #5
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

3·1,973 Posts
Default

Quote:
Originally Posted by henryzz View Post
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.
henryzz is offline   Reply With Quote
Old 2016-07-24, 11:16   #6
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

838410 Posts
Default

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.

Last fiddled with by science_man_88 on 2016-07-24 at 11:49
science_man_88 is offline   Reply With Quote
Old 2016-07-24, 14:30   #7
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

3·1,973 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
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.
henryzz is offline   Reply With Quote
Old 2016-07-24, 18:54   #8
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by henryzz View Post
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
science_man_88 is offline   Reply With Quote
Old 2016-07-24, 21:10   #9
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

3×1,973 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
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.
henryzz is offline   Reply With Quote
Old 2016-07-24, 21:50   #10
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by henryzz View Post
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.
science_man_88 is offline   Reply With Quote
Old 2017-02-01, 16:00   #11
sweety439
 
sweety439's Avatar
 
"99(4^34019)99 palind"
Nov 2016
(P^81993)SZ base 36

5×13×47 Posts
Default

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
sweety439 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Lucas-Lehmer Primes henryzz And now for something completely different 42 2019-06-03 14:09
Lucas and Fibonacci primes Batalov And now for something completely different 9 2017-06-28 16:56
Lucas-Lehmer sequences starting with s0 other than 4 GP2 Math 6 2016-05-21 17:00
Need help with Lucas Sequences... WraithX Programming 11 2010-09-23 23:22
factors of lucas sequences jocelynl Math 2 2010-09-23 21:32

All times are UTC. The time now is 04:13.


Thu Oct 21 04:13:07 UTC 2021 up 89 days, 22:42, 1 user, load averages: 2.28, 2.40, 2.46

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.