OEIS A071580: Smallest prime of the form k*a(n-1)*a(n-2)*...*a(1)+1

arbooker · 2015-05-19, 12:17

I have been working on extending OEIS sequence A071580, whose nth term is the smallest prime congruent to 1 mod the product of all smaller terms. The sequence enjoys several nice properties in common with the sequence of Mersenne primes:

1) There is a fast algorithm to prove primality: since p-1 has a prime factor of about square root size, the simplest variant of Pocklington's criterion runs about as quickly as a Fermat PRP test.

2) It has rapid growth (doubly exponential), so we get to big primes quickly.

3) It has an intrinsic definition, as opposed to (say) Proth primes, which are a bit quicker to test, but for which the choice of numbers is completely ad hoc.

I have computed the first 23 terms, the last of which is a prime with over a million digits. I used gwnum to find the terms and double-checked the first 22 of them with gmp.

It took a lot of effort to find the 23rd term (it was roughly a factor of 3 larger than expected), and I'm thinking of stopping at this point, but if any of you guys with substantial resources would be interested in helping to find the 24th term or double-check the 23rd, let me know. There is a reasonable chance of finding the 24th term (which will be a prime with over 2 million digits) within a year.

Batalov · 2015-05-19, 19:03

That is a nice sequence. And good thinking about converting it into the k-series (A258081); one needs a compact representation for a simple sieve and whatnot.

Technically, this series is not as fast as Mersenne's (wall clock wise), because for all terms generic mod reduction on a generic FFT size will be used (making the proof at least twice slower than a similar-sized Mp or a GFN or a cyclotomic GenUni number). My bet for a viz-a-viz Mersenne contender for the largest known prime is between the latter two classes; all they need is a GIMPS' size crowd to follow.

I'll double check your terms with PFGW and scripts. I'll start with writing a quick-and-dirty sieve, maybe tonight.

Batalov · 2015-05-19, 19:11

Also, A071580(22) and A071580(23) should be in the UTM prime database (even if they are not minimal, pending a double check, -- they are still great primes)!
Email Chris Caldwell and send him a zip of the whole sequence, because it will be a helper file for proving successive terms.

arbooker · 2015-05-19, 20:54

Quote:

Originally Posted by Batalov

Technically, this series is not as fast as Mersenne's (wall clock wise)

True, and Mersenne numbers also benefit a lot from algebraic factorizations that are not available here. I wasn't really thinking of this is as a contender for largest known prime, though there is an outside chance of breaking 17orbust's long-standing record for the largest non-Mersenne prime (we'd need two more terms).

Quote:

I'll double check your terms with PFGW and scripts. I'll start with writing a quick-and-dirty sieve, maybe tonight.

Thanks. I can also send the certificate file if you like. I've recorded the factors found by sieving, so you don't have to repeat every step from scratch (unless you want to, of course)...

Batalov · 2015-05-19, 21:05

I sent Chris the zip file with the (re-generated by me) sequence.
That's all he needs. Here's what I wrote:

Quote:

Before A.R.Booker writes to you (if he didn't yet),
I can make a submission on his behalf. Attached is the zip file <<seq.zip>>.
Use the last line alone as a blob (that's the 23rd member of the sequence) and prove it using the whole file as a helper.
Then, also, use the penultimate line as a blob (that's 22nd member of the sequence) and prove it using the whole file as a helper.

And there, you will have two primes, 518309 and 1036620 decimal digits.
Credit Andrew R. Booker + openPFGW

Batalov · 2015-05-19, 21:10

Quote:

Originally Posted by arbooker

I can also send the certificate file if you like. I've recorded the factors found by sieving, so you don't have to repeat every step from scratch (unless you want to, of course)...

That's the right way to do it!

I've warmed up by brute force double-checking up to a(18) and a couple more are pending, but if you send me the blueprints, that would save even more time for DC. I'll PM you.

arbooker · 2015-05-19, 22:02

Quote:

Originally Posted by Batalov

I sent Chris the zip file with the (re-generated by me) sequence.

Thanks--I don't have a prover account there and wasn't looking forward to making one for just two numbers.

axn · 2015-05-21, 05:59

The smaller of the two has now appeared in Top5000 (http://primes.utm.edu/primes/page.php?id=119934). Interesting things to note:
It has an current rank higher than entry rank (as of this writing)!
It took PFGW 4 passes to prove this (where the N+1 pass should take about 2x N-1 pass)!

BTW, the sister sequence (https://oeis.org/A258081) is empty? Can someone post all the k values here as a handy reference?

EDIT:- Reconstructed k values from the Top 5000 submission data

Code:

1, 1, 1, 1, 2, 10, 12, 10, 21, 25, 70, 670, 239, 2115, 586, 1619, 26800, 2505, 99019, 40903, 285641, 67166

Has an extra "1" at the beginning to correspond to "2".

Batalov · 2015-05-21, 06:13

It is actually not empty -- and if you log in (at top right), then you can see any draft of any sequence (inc. this). Handy!
Even if you are not entering sequences you can create a Wiki account.But in any case the sequence is this ATM:

Code:

1, 1, 1, 1, 2, 10, 12, 10, 21, 25, 70, 670, 239, 2115, 586, 1619, 26800, 2505, 99019, 40903, 285641, 67166, 1852765

At UTM, rank #117 slot in fact was empty in the middle of the day (use: http://primes.utm.edu/primes/page.php and request rank = 117), but then at some point it collapsed back; maybe something broke in Chris' scripts. I am sure that it will be there sooner or later. In my hands, pfgw N-1 proof took only 11 hours. Chris uses -tc for some reason in his automatic server routines.

P.S. What may be the case is that C.C. is running all ladder proofs, first. (And that is the right way to do it. I ran them all, too.) He is rigorous, and even if he wasn't, David Broadhurst is even more rigorous.

axn · 2015-05-21, 11:49

Thanks Serge. I missed your reply as I was editing mine to include the k values. I will register at OEIS (not sure... I may already have an account there).

Also found the "-" side http://oeis.org/A090475. How far has this one been extended?

EDIT:- Now the Top5000 entry has its entrance rank adjusted, so everything is fine.

arbooker · 2015-05-21, 17:54

Quote:

Originally Posted by axn

Also found the "-" side http://oeis.org/A090475. How far has this one been extended?

Good idea. I've done nothing on that sequence, but it wouldn't be hard to adapt my existing sieving code for it.

I do have just under 10k terms of A061092, but we'll never get to top 5000 primes with that (current size is ~41k digits).

2015-05-21, 05:59	#8
axn Jun 2003 5·1,087 Posts	The smaller of the two has now appeared in Top5000 (http://primes.utm.edu/primes/page.php?id=119934). Interesting things to note: It has an current rank higher than entry rank (as of this writing)! It took PFGW 4 passes to prove this (where the N+1 pass should take about 2x N-1 pass)! BTW, the sister sequence (https://oeis.org/A258081) is empty? Can someone post all the k values here as a handy reference? EDIT:- Reconstructed k values from the Top 5000 submission data Code: 1, 1, 1, 1, 2, 10, 12, 10, 21, 25, 70, 670, 239, 2115, 586, 1619, 26800, 2505, 99019, 40903, 285641, 67166 Has an extra "1" at the beginning to correspond to "2". Last fiddled with by axn on 2015-05-21 at 06:28

2015-05-21, 06:13	#9
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 2²·7·359 Posts	It is actually not empty -- and if you log in (at top right), then you can see any draft of any sequence (inc. this). Handy! Even if you are not entering sequences you can create a Wiki account.But in any case the sequence is this ATM: Code: 1, 1, 1, 1, 2, 10, 12, 10, 21, 25, 70, 670, 239, 2115, 586, 1619, 26800, 2505, 99019, 40903, 285641, 67166, 1852765 At UTM, rank #117 slot in fact was empty in the middle of the day (use: http://primes.utm.edu/primes/page.php and request rank = 117), but then at some point it collapsed back; maybe something broke in Chris' scripts. I am sure that it will be there sooner or later. In my hands, pfgw N-1 proof took only 11 hours. Chris uses -tc for some reason in his automatic server routines. P.S. What may be the case is that C.C. is running all ladder proofs, first. (And that is the right way to do it. I ran them all, too.) He is rigorous, and even if he wasn't, David Broadhurst is even more rigorous. Last fiddled with by Batalov on 2015-05-21 at 06:26 Reason: tpyos

2015-05-21, 11:49	#10
axn Jun 2003 5·1,087 Posts	Thanks Serge. I missed your reply as I was editing mine to include the k values. I will register at OEIS (not sure... I may already have an account there). Also found the "-" side http://oeis.org/A090475. How far has this one been extended? EDIT:- Now the Top5000 entry has its entrance rank adjusted, so everything is fine. Last fiddled with by axn on 2015-05-21 at 11:51

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Smallest prime of the form a^2^m + b^2^m, m>=14	JeppeSN	Math	117	2022-08-30 16:41
Is there a prime of the form......	PawnProver44	Miscellaneous Math	9	2016-03-19 22:11
Smallest prime with a digit sum of 911	Stargate38	Puzzles	6	2014-09-29 14:18
Smallest floor of k for cullen prime	Citrix	Prime Cullen Prime	12	2007-04-26 19:52
Smallest ten-million-digit prime	Heck	Factoring	9	2004-10-28 11:34

2015-05-19, 12:17	#1
arbooker "Andrew Booker" Mar 2013 92₁₀ Posts	*OEIS A071580: Smallest prime of the form ka(n-1)a(n-2)...a(1)+1* I have been working on extending OEIS sequence A071580, whose nth term is the smallest prime congruent to 1 mod the product of all smaller terms. The sequence enjoys several nice properties in common with the sequence of Mersenne primes: 1) There is a fast algorithm to prove primality: since p-1 has a prime factor of about square root size, the simplest variant of Pocklington's criterion runs about as quickly as a Fermat PRP test. 2) It has rapid growth (doubly exponential), so we get to big primes quickly. 3) It has an intrinsic definition, as opposed to (say) Proth primes, which are a bit quicker to test, but for which the choice of numbers is completely ad hoc. I have computed the first 23 terms, the last of which is a prime with over a million digits. I used gwnum to find the terms and double-checked the first 22 of them with gmp. It took a lot of effort to find the 23rd term (it was roughly a factor of 3 larger than expected), and I'm thinking of stopping at this point, but if any of you guys with substantial resources would be interested in helping to find the 24th term or double-check the 23rd, let me know. There is a reasonable chance of finding the 24th term (which will be a prime with over 2 million digits) within a year.

2015-05-19, 19:03	#2
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 2²·7·359 Posts	That is a nice sequence. And good thinking about converting it into the k-series (A258081); one needs a compact representation for a simple sieve and whatnot. Technically, this series is not as fast as Mersenne's (wall clock wise), because for all terms generic mod reduction on a generic FFT size will be used (making the proof at least twice slower than a similar-sized Mp or a GFN or a cyclotomic GenUni number). My bet for a viz-a-viz Mersenne contender for the largest known prime is between the latter two classes; all they need is a GIMPS' size crowd to follow. I'll double check your terms with PFGW and scripts. I'll start with writing a quick-and-dirty sieve, maybe tonight.

2015-05-19, 19:11	#3
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 2²×7×359 Posts	Also, A071580(22) and A071580(23) should be in the UTM prime database (even if they are not minimal, pending a double check, -- they are still great primes)! Email Chris Caldwell and send him a zip of the whole sequence, because it will be a helper file for proving successive terms.