mersenneforum.org (https://www.mersenneforum.org/index.php)
-   And now for something completely different (https://www.mersenneforum.org/forumdisplay.php?f=119)
-   -   OEIS A071580: Smallest prime of the form k*a(n-1)*a(n-2)*...*a(1)+1 (https://www.mersenneforum.org/showthread.php?t=20260)

 arbooker 2015-05-19 12:17

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.

 Batalov 2015-05-19 19:03

That is a nice sequence. And good thinking about converting it into the k-series ([URL="https://oeis.org/A258081"]A258081[/URL]); one needs a compact representation for a simple sieve and whatnot.

Technically, this series is not [I]as fast[/I] 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. :rolleyes:

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 [URL="http://primes.utm.edu/primes/includes/mail.php"]Chris Caldwell[/URL] 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=Batalov;402643]Technically, this series is not [I]as fast[/I] as Mersenne's (wall clock wise)[/QUOTE]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.[/QUOTE]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.
[B]Credit[/B] Andrew R. Booker + openPFGW[/QUOTE]

 Batalov 2015-05-19 21:10

[QUOTE=arbooker;402653]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)...[/QUOTE]
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=Batalov;402655]I sent Chris the zip file with the (re-generated by me) sequence.[/QUOTE]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 ([url]http://primes.utm.edu/primes/page.php?id=119934[/url]). 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 ([url]https://oeis.org/A258081[/url]) 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[/code]
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 [/CODE]At UTM, rank #117 slot in fact was empty in the middle of the day (use: [URL]http://primes.utm.edu/primes/page.php[/URL] 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 [url]http://oeis.org/A090475[/url]. 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=axn;402747]Also found the "-" side [url]http://oeis.org/A090475[/url]. How far has this one been extended?[/QUOTE]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 [URL="http://oeis.org/A061092"]A061092[/URL], but we'll never get to top 5000 primes with that (current size is ~41k digits).

All times are UTC. The time now is 15:50.