Register FAQ Search Today's Posts Mark Forums Read  2018-04-11, 22:45 #1 Citrix   Jun 2003 1,553 Posts 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   2018-04-11, 23:43   #2
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts Quote:
 Originally Posted by Citrix 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   2018-04-12, 00:11 #3 Citrix   Jun 2003 1,553 Posts 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   2018-04-12, 08:45 #4 10metreh   Nov 2008 91216 Posts 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.   2018-04-12, 09:08   #5
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts Quote:
 Originally Posted by 10metreh 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   2018-04-13, 02:59 #6 Citrix   Jun 2003 1,553 Posts 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?   2018-04-13, 06:20   #7
henryzz
Just call me Henry

"David"
Sep 2007
Cambridge (GMT)

52×227 Posts Quote:
 Originally Posted by Citrix 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   2018-04-13, 11:09   #8
10metreh

Nov 2008

2·33·43 Posts Quote:
 Originally Posted by science_man_88 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.   2018-04-13, 15:44 #9 sweety439   Nov 2016 3·677 Posts 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   2018-04-15, 00:03   #10
Citrix

Jun 2003

61116 Posts Quote:
 Originally Posted by henryzz 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
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   2018-04-15, 10:07   #11
henryzz
Just call me Henry

"David"
Sep 2007
Cambridge (GMT)

52·227 Posts Quote:
 Originally Posted by Citrix 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.   Thread Tools Show Printable Version Email this Page

All times are UTC. The time now is 22:18.

Sat Jul 4 22:18:11 UTC 2020 up 101 days, 19:51, 1 user, load averages: 1.10, 1.03, 1.18