mersenneforum.org  

Go Back   mersenneforum.org > Prime Search Projects > And now for something completely different

Reply
 
Thread Tools
Old 2015-05-19, 12:17   #1
arbooker
 
arbooker's Avatar
 
"Andrew Booker"
Mar 2013

5·17 Posts
Default 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.
arbooker is offline   Reply With Quote
Old 2015-05-19, 19:03   #2
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

22×3×7×109 Posts
Thumbs up

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 is offline   Reply With Quote
Old 2015-05-19, 19:11   #3
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

22×3×7×109 Posts
Default

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.
Batalov is offline   Reply With Quote
Old 2015-05-19, 20:54   #4
arbooker
 
arbooker's Avatar
 
"Andrew Booker"
Mar 2013

5×17 Posts
Default

Quote:
Originally Posted by Batalov View Post
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)...
arbooker is offline   Reply With Quote
Old 2015-05-19, 21:05   #5
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

22×3×7×109 Posts
Cool

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 is offline   Reply With Quote
Old 2015-05-19, 21:10   #6
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

100011110001002 Posts
Default

Quote:
Originally Posted by arbooker View Post
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.
Batalov is offline   Reply With Quote
Old 2015-05-19, 22:02   #7
arbooker
 
arbooker's Avatar
 
"Andrew Booker"
Mar 2013

5·17 Posts
Default

Quote:
Originally Posted by Batalov View Post
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.
arbooker is offline   Reply With Quote
Old 2015-05-21, 05:59   #8
axn
 
axn's Avatar
 
Jun 2003

17·281 Posts
Default

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
axn is offline   Reply With Quote
Old 2015-05-21, 06:13   #9
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

915610 Posts
Lightbulb

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
Batalov is offline   Reply With Quote
Old 2015-05-21, 11:49   #10
axn
 
axn's Avatar
 
Jun 2003

10010101010012 Posts
Default

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
axn is offline   Reply With Quote
Old 2015-05-21, 17:54   #11
arbooker
 
arbooker's Avatar
 
"Andrew Booker"
Mar 2013

5·17 Posts
Default

Quote:
Originally Posted by axn View Post
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).
arbooker is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Smallest prime of the form a^2^m + b^2^m, m>=14 JeppeSN Math 114 2018-12-16 01:57
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

All times are UTC. The time now is 20:33.

Wed Nov 25 20:33:48 UTC 2020 up 76 days, 17:44, 3 users, load averages: 1.50, 1.59, 1.60

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.