mersenneforum.org OEIS A071580: Smallest prime of the form k*a(n-1)*a(n-2)*...*a(1)+1
 Register FAQ Search Today's Posts Mark Forums Read

 2015-05-19, 12:17 #1 arbooker     "Andrew Booker" Mar 2013 5×17 Posts OEIS A071580: Smallest prime of the form k*a(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·4,591 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·4,591 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.
2015-05-19, 20:54   #4
arbooker

"Andrew Booker"
Mar 2013

5·17 Posts

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

2015-05-19, 21:05   #5
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

918210 Posts

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

2015-05-19, 21:10   #6
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

2×4,591 Posts

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.

2015-05-19, 22:02   #7
arbooker

"Andrew Booker"
Mar 2013

5·17 Posts

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.

 2015-05-21, 05:59 #8 axn     Jun 2003 2×5×479 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 23DE16 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 12B616 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
2015-05-21, 17:54   #11
arbooker

"Andrew Booker"
Mar 2013

5×17 Posts

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

 Similar Threads Thread Thread Starter Forum Replies Last Post JeppeSN Math 114 2018-12-16 01:57 PawnProver44 Miscellaneous Math 9 2016-03-19 22:11 Stargate38 Puzzles 6 2014-09-29 14:18 Citrix Prime Cullen Prime 12 2007-04-26 19:52 Heck Factoring 9 2004-10-28 11:34

All times are UTC. The time now is 14:49.

Wed Dec 2 14:49:55 UTC 2020 up 83 days, 12 hrs, 2 users, load averages: 1.47, 1.77, 1.72