A113767

Citrix · 2018-04-11, 22:45

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?

science_man_88 · 2018-04-11, 23:43

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.

Citrix · 2018-04-12, 00:11

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

10metreh · 2018-04-12, 08:45

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.

science_man_88 · 2018-04-12, 09:08

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.

Citrix · 2018-04-13, 02:59

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?

henryzz · 2018-04-13, 06:20

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

10metreh · 2018-04-13, 11:09

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.

sweety439 · 2018-04-13, 15:44

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

Citrix · 2018-04-15, 00:03

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

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.

henryzz · 2018-04-15, 10:07

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.

2018-04-11, 22:45	#1
Citrix Jun 2003 1,579 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-12, 00:11	#3
Citrix Jun 2003 1579₁₀ 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-13, 15:44	#9
sweety439 Nov 2016 2²·691 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 472^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-12, 08:45	#4
10metreh Nov 2008 912₁₆ 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+35713193773*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-13, 02:59	#6
Citrix Jun 2003 1,579 Posts	Is someone able to modify srsieve to sieve for (((((((((((((((((12^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?