b^(k*2^n)-2 primes

lukerichards · 2019-04-30, 06:21

With reference to a previous thread:

Primes of the form $b^{k \cdot 2^n}-2$ where k and b are both odd, give a head start to factorisation of N+1 due to the fact that:

$b^{k \cdot 2^n}-1 = (b^k-1)(b^k+1)(b^{2k}+1)[...](b^{k \cdot 2^{n-2}}+1)(b^{k \cdot 2^{n-1}}+1)$

The extent of the utility of this factorisation aside, I'm interested in exploring primes of this form and have decided to assign some cores to it.

Have done some elementary sieving to eliminate a lot of candidates and I am planning to do some more.

If anyone is interested in picking up a worktodo.txt file to PRP some candidates, let me know. My thanks to bearnol who is already working on one which I have rudimentally estimated to be worth 80-120 core-days.

I'm focussing on b = 3 initially.

axn · 2019-04-30, 06:42

Quote:

Originally Posted by lukerichards

Have done some elementary sieving to eliminate a lot of candidates and I am planning to do some more.

How are you parameterizing your search space? What are the values that you're currently testing?

How are you doing the sieving?

lukerichards · 2019-04-30, 06:54

Quote:

Originally Posted by axn

How are you parameterizing your search space? What are the values that you're currently testing?

1) Fix b
2) Fix k
3) Increasing n until a certain bit size limit is reached
4) Increase k, return to 3) until the Cunningham table limit for b is reached
5) Increase b, return to 2)

Quote:

Originally Posted by axn

How are you doing the sieving?

I wrote a program to do what I referring to as Stage 1 sieving...

Take each prime, p, up to a limit and find the first m for which 3^m = 2 mod p. Then find the multiplicative order of 3 mod p (or is it p mod 3?) which gives the linear sequence of all m's for which 3^m = 2 mod p.

Stage 2 sieving... run some small amount of ECM and P-1 on candidates to a) find factors and b) then find the multiplicative orders of these, to find further linear sequences of ms for which 3^m = 2 mod p.

From stage 1 alone I now only have ~500 candidates to test for b = 3 within my size limit. (I'm not being cagey about what my limit it, I decided it two weeks ago and the details are at home, while I'm presently at work - I can check back this evening if you want the details.).

axn · 2019-04-30, 07:49

Depending on how large a range you want to sieve, you might get better sieving efficiency using NewPGen or sr1sieve. Using either of them, you can sieve 3^n-2 form for a given n range, and then later winnow out the survivors further using your additional smoothness criteria.

lukerichards · 2019-04-30, 11:25

Thanks, I'll look into this.

The reason I wrote my own program is because a) I didn't know which software would be appropriate and b) I wanted to be able to get out the data that I was interested in.

In particular for any composite b^m-2 I'm interested to know that prime that divides it - before I investigate the software you mention in more detail, do you know if this data can be extracted from its results?

axn · 2019-04-30, 12:57

Quote:

Originally Posted by lukerichards

In particular for any composite b^m-2 I'm interested to know that prime that divides it - before I investigate the software you mention in more detail, do you know if this data can be extracted from its results?

NewPGen can be made to log the factors found / candidates removed, but is limited to factors > 10^9. sr1sieve also can log the factors -- you can control how big the factors should be.

lukerichards · 2019-04-30, 16:55

Unsurprisingly, the specialist software written by experts is a lot more efficient at sieving than my paltry efforts in Python.

I'm now at a point where NewPGen is eliminating exponents for b=3, n < 10^7 at a rate of 2 per second and there are ~730k exponents left in its list.

Of the 730k, only 140 meet my smoothness criteria and this number hasn't changed in the past hour.

My computer will take 9 hours to run a PRP test on the largest of these 140, so I'm going to leave NewPGen running overnight and see how many of the 140 are eliminated by the morning, at which point I'll batch up the remaining exponents into worktodo files and get to work on PRP tests.

Thanks axn for the advice on sieving software.

lukerichards · 2019-05-01, 06:23

Quote:

Originally Posted by lukerichards

Of the 730k, only 140 meet my smoothness criteria and this number hasn't changed in the past hour.

My computer will take 9 hours to run a PRP test on the largest of these 140, so I'm going to leave NewPGen running overnight and see how many of the 140 are eliminated by the morning

9 in the 13 hours since I left my desk at work, so the sieve continues.

For the benefit of anyone reading this who is not familiar with this process, sieving is a process of eliminating prime number candidates by identifying smallish factors using an efficient algorithm which can often do many at once.

It makes sense to sieve because, as above - in the early stages doing so eliminates candidates at a faster rate than running PRP tests can do.

Once it takes longer on average to eliminate a candidate than it takes to run a PRP test, PRP tests are run instead in order to maximise efficiency.

By example, the rate shown above of eliminating 9 candidates in 13 hours is good going. The candidates we're talking about will take 1-10 hours each to test with PRP, so a rate of elimination of 1.5 hours each is still quicker on average than running tests.

Sieving is, however, a bit of a depressing task. It is encouraging that you can see the 'number of candidates left' decreasing steadily, but ultimately the only thing sieving does is find composites. Unless you sieve up to the square root of the value of a candidate, which is impractical, you know all the while you're running it that you're not actually going to find any primes. You have to have faith that, in the long run, if there are primes to be found in your search field, what you're doing is going help you find them quicker.

Citrix · 2019-05-06, 01:52

An interesting side project would be searching for k=1
Choosing b such that b^(2^(n-1))+1 is also prime
Then b^(2^n)-2 could easily be proven prime as more than 50% of the N+1 can be factorized.

Of note: for large 2^n values we already have a list of b values from PrimeGrid GFN search.

2019-04-30, 06:21	#1
lukerichards "Luke Richards" Jan 2018 Birmingham, UK 288₁₀ Posts	*b^(k2^n)-2 primes** With reference to a previous thread: Primes of the form $b^{k \cdot 2^n}-2$ where k and b are both odd, give a head start to factorisation of N+1 due to the fact that: $b^{k \cdot 2^n}-1 = (b^k-1)(b^k+1)(b^{2k}+1)[...](b^{k \cdot 2^{n-2}}+1)(b^{k \cdot 2^{n-1}}+1)$ The extent of the utility of this factorisation aside, I'm interested in exploring primes of this form and have decided to assign some cores to it. Have done some elementary sieving to eliminate a lot of candidates and I am planning to do some more. If anyone is interested in picking up a worktodo.txt file to PRP some candidates, let me know. My thanks to bearnol who is already working on one which I have rudimentally estimated to be worth 80-120 core-days. I'm focussing on b = 3 initially. Last fiddled with by lukerichards on 2019-04-30 at 06:33 Reason: Tidying and correcting a typo.

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Mersenne Primes p which are in a set of twin primes is finite?	carpetpool	Miscellaneous Math	3	2017-08-10 13:47
Distribution of Mersenne primes before and after couples of primes found	emily	Math	34	2017-07-16 18:44
Conjecture about Mersenne primes and non-primes v2	Mickey1	Miscellaneous Math	1	2013-05-30 12:32
A conjecture about Mersenne primes and non-primes	Unregistered	Information & Answers	0	2011-01-31 15:41
possible primes (real primes & poss.prime products)	troels munkner	Miscellaneous Math	4	2006-06-02 08:35

2019-04-30, 07:49	#4
axn Jun 2003 5,051 Posts	Depending on how large a range you want to sieve, you might get better sieving efficiency using NewPGen or sr1sieve. Using either of them, you can sieve 3^n-2 form for a given n range, and then later winnow out the survivors further using your additional smoothness criteria.

2019-04-30, 11:25	#5
lukerichards "Luke Richards" Jan 2018 Birmingham, UK 2⁵·3² Posts	Thanks, I'll look into this. The reason I wrote my own program is because a) I didn't know which software would be appropriate and b) I wanted to be able to get out the data that I was interested in. In particular for any composite b^m-2 I'm interested to know that prime that divides it - before I investigate the software you mention in more detail, do you know if this data can be extracted from its results?

2019-04-30, 16:55	#7
lukerichards "Luke Richards" Jan 2018 Birmingham, UK 440₈ Posts	Unsurprisingly, the specialist software written by experts is a lot more efficient at sieving than my paltry efforts in Python. I'm now at a point where NewPGen is eliminating exponents for b=3, n < 10^7 at a rate of 2 per second and there are ~730k exponents left in its list. Of the 730k, only 140 meet my smoothness criteria and this number hasn't changed in the past hour. My computer will take 9 hours to run a PRP test on the largest of these 140, so I'm going to leave NewPGen running overnight and see how many of the 140 are eliminated by the morning, at which point I'll batch up the remaining exponents into worktodo files and get to work on PRP tests. Thanks axn for the advice on sieving software.

2019-05-06, 01:52	#9
Citrix Jun 2003 2·7·113 Posts	An interesting side project would be searching for k=1 Choosing b such that b^(2^(n-1))+1 is also prime Then b^(2^n)-2 could easily be proven prime as more than 50% of the N+1 can be factorized. Of note: for large 2^n values we already have a list of b values from PrimeGrid GFN search.