 mersenneforum.org (https://www.mersenneforum.org/index.php)
-   And now for something completely different (https://www.mersenneforum.org/forumdisplay.php?f=119)

 Citrix 2018-04-11 22:45

A113767

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

I had done some work on this in the past

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=Citrix;485085]I am interesting in extending the series A113767
[url]https://oeis.org/A113767[/url]

I had done some work on this in the past

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?[/QUOTE]

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=10metreh;485138]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.[/QUOTE]

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=Citrix;485204]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?[/QUOTE]

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.
[url]http://www.mersenneforum.org/rogue/mtsieve.html[/url]

 10metreh 2018-04-13 11:09

[QUOTE=science_man_88;485140]It can also hit a cunningham chain of first or second kind respectively though.[/QUOTE]

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
[/CODE]

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
[/CODE]

 Citrix 2018-04-15 00:03

[QUOTE=henryzz;485211]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.
[url]http://www.mersenneforum.org/rogue/mtsieve.html[/url][/QUOTE]

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