mersenneforum.org  

Go Back   mersenneforum.org > Prime Search Projects > And now for something completely different

Reply
 
Thread Tools
Old 2018-04-11, 22:45   #1
Citrix
 
Citrix's Avatar
 
Jun 2003

32·52·7 Posts
Default A113767

I am interesting in extending the series A113767
https://oeis.org/A113767

I had done some work on this in the past
http://www.mersenneforum.org/showthread.php?t=18347

1) How do I submit the two terms found 6071, 218431?
2) Is there an efficient sieve for these forms?
3) Would these sequences be finite?

Last fiddled with by Citrix on 2018-04-11 at 23:02
Citrix is offline   Reply With Quote
Old 2018-04-11, 23:43   #2
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

20B116 Posts
Default

Quote:
Originally Posted by Citrix View Post
I am interesting in extending the series A113767
https://oeis.org/A113767

I had done some work on this in the past
http://www.mersenneforum.org/showthread.php?t=18347

1) How do I submit the two terms found 6071, 218431?
2) Is there an efficient sieve for these forms?
3) Would these sequences be finite?
1) get an OEIS account, ( or use somebody who has one) to edit the sequence.
2) modular remainders are inefficient but give that if a(n-1) is 2 mod 3, k is odd, if a(n-1) is 1 mod 3,k is even.( Oops math for the related sequence)
3) no clue.

Last fiddled with by science_man_88 on 2018-04-11 at 23:54
science_man_88 is offline   Reply With Quote
Old 2018-04-12, 00:11   #3
Citrix
 
Citrix's Avatar
 
Jun 2003

32·52·7 Posts
Default

1) I have figured out how to add the terms. Thanks.
2) I am looking for efficient software (not the math). This is basically a fixed k sieve (but the k is very large).

Last fiddled with by Citrix on 2018-04-12 at 00:12
Citrix is offline   Reply With Quote
Old 2018-04-12, 08:45   #4
10metreh
 
10metreh's Avatar
 
Nov 2008

2·33·43 Posts
Default

It feels like these sequences ought to be finite. The only long-term modular restriction I can think of for members of the sequence is that they cannot be 1 mod p for any p other than 2 and the previous term (correct me if I've missed something!). Since 78557 has covering set {3, 5, 7, 13, 19, 37, 73}, 78557+3*5*7*13*19*37*73*n is a Sierpinski number for every n, and 78557 is not 1 mod any of the primes in its covering set, so eventually the sequence ought to hit a number of this form, if it does not hit another Sierpinski number first.
10metreh is offline   Reply With Quote
Old 2018-04-12, 09:08   #5
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts
Default

Quote:
Originally Posted by 10metreh View Post
It feels like these sequences ought to be finite. The only long-term modular restriction I can think of for members of the sequence is that they cannot be 1 mod p for any p other than 2 and the previous term (correct me if I've missed something!). Since 78557 has covering set {3, 5, 7, 13, 19, 37, 73}, 78557+3*5*7*13*19*37*73*n is a Sierpinski number for every n, and 78557 is not 1 mod any of the primes in its covering set, so eventually the sequence ought to hit a number of this form, if it does not hit another Sierpinski number first.
It can also hit a cunningham chain of first or second kind respectively though.

Last fiddled with by science_man_88 on 2018-04-12 at 09:08
science_man_88 is offline   Reply With Quote
Old 2018-04-13, 02:59   #6
Citrix
 
Citrix's Avatar
 
Jun 2003

30478 Posts
Default

Is someone able to modify srsieve to sieve for (((((((((((((((((1*2^1+1)*2^1+1)*2^2+1)*2^1+1)*2^5+1)*2^1+1)*2^1+1)*2^29+1)*2^3+1)*2^37+1)*2^31+1)*2^227+1)*2^835+1)*2^115+1)*2^7615+1)*2^6071+1)*2^218431+1)*2^n+1?
Citrix is offline   Reply With Quote
Old 2018-04-13, 06:20   #7
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

22×1,433 Posts
Default

Quote:
Originally Posted by Citrix View Post
Is someone able to modify srsieve to sieve for (((((((((((((((((1*2^1+1)*2^1+1)*2^2+1)*2^1+1)*2^5+1)*2^1+1)*2^1+1)*2^29+1)*2^3+1)*2^37+1)*2^31+1)*2^227+1)*2^835+1)*2^115+1)*2^7615+1)*2^6071+1)*2^218431+1)*2^n+1?
I think your best bet might be to modify mtsieve adding a fixed k sieve with k being a gmp number.
Your runtime might be dominated though by calculating k % p as that is a very large k. Whatever you do I don't think it is going to be overly fast.
http://www.mersenneforum.org/rogue/mtsieve.html

Last fiddled with by henryzz on 2018-04-13 at 06:20
henryzz is offline   Reply With Quote
Old 2018-04-13, 11:09   #8
10metreh
 
10metreh's Avatar
 
Nov 2008

1001000100102 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
It can also hit a cunningham chain of first or second kind respectively though.
But this doesn't affect the finiteness or otherwise of the sequence, as Cunningham chains are finite. Also, as the terms get larger, the probability of hitting a Cunningham chain
should tend to 0 (by the prime number theorem), whereas the probability of hitting a Sierpinski number does not.
10metreh is offline   Reply With Quote
Old 2018-04-13, 15:44   #9
sweety439
 
sweety439's Avatar
 
Nov 2016

22·19·31 Posts
Default

We can make the list of all primes:

a(m,n+1) is the smallest prime of the form a(m,n)*2^k+1 (k>=0)

a(m+1,1) is the smallest prime not in the first m rows

Code:
 2     3      7       29           59   1889   3779   7559
 5    11     23       47   47*2^583+1
13    53    107      857         6857
17   137   1097   140417
The first row of this table is indeed A084435.

For the Riesel analog:

a(m,n+1) is the smallest prime of the form a(m,n)*2^k-1 (k>=1)

a(m+1,1) is the smallest prime not in the first m rows

Code:
 2    3      5    19        37   73   9343
 7   13    103   823   1685503
11   43   5503
17   67   2143

Last fiddled with by sweety439 on 2018-04-13 at 15:54
sweety439 is offline   Reply With Quote
Old 2018-04-15, 00:03   #10
Citrix
 
Citrix's Avatar
 
Jun 2003

157510 Posts
Default

Quote:
Originally Posted by henryzz View Post
I think your best bet might be to modify mtsieve adding a fixed k sieve with k being a gmp number.
Your runtime might be dominated though by calculating k % p as that is a very large k. Whatever you do I don't think it is going to be overly fast.
http://www.mersenneforum.org/rogue/mtsieve.html
Thank you for pointing out mtsieve. (I did not know about this before :( )
There is something called modular exponentiation which will calculate k%p very fast.
Calculating k%p will take very little time per prime.

Addendum: Looks like srsieve is not implemented yet. So this will not help.

Last fiddled with by Citrix on 2018-04-15 at 00:13
Citrix is offline   Reply With Quote
Old 2018-04-15, 10:07   #11
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

10110011001002 Posts
Default

Quote:
Originally Posted by Citrix View Post
Thank you for pointing out mtsieve. (I did not know about this before :( )
There is something called modular exponentiation which will calculate k%p very fast.
Calculating k%p will take very little time per prime.

Addendum: Looks like srsieve is not implemented yet. So this will not help.
There will be a fair bit of manual work although it should be doable in a day or 2.
henryzz is offline   Reply With Quote
Reply

Thread Tools


All times are UTC. The time now is 06:33.

Sat Oct 24 06:33:15 UTC 2020 up 44 days, 3:44, 1 user, load averages: 1.17, 1.37, 1.36

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.