The OEIS has several sequences with mechanisms that generate only 1's and primes. Some can generate purely primes.
They include:
A088198 https://oeis.org/A088198
A135506 https://oeis.org/A135506
A135508 https://oeis.org/A13550
A186253 http://oeis.org/A186253 thru A186263
Rowland has his, though the primes are quite sparse: A132199 https://oeis.org/A132199 Rowland is mentioned at https://en.wikipedia.org/wiki/Formula_for_primes but it well may not be as good as some of the others discussed here (see lower table).
There are others one can create ( I made one from A129912). Here is a basic script: A129912_1orP.gp
A039726 http://oeis.org/A039726 illustrates the result of another sequence of only primes ( w/ omissions)
I must mention A271116 https://oeis.org/A271116 . This sequence includes all primes>3 as well as very few composites (0.03% in the first 10 million terms). It has a nice "predictable" graph. The sequence name is "Integers n such that round(3^n/12) is divisible by n". So the definition is quite straightfwd, and the secondary verification is for pseudoprimes to base 3. The Pari script there is: is(n) = lift(Mod(3, 4*n)^(n-1))==1 It is not fast for generating a range of primes (8min for ~ 10million) but is fine for eval of specific candidates. Note that powers of 3 end in the same digits as potential primes, 1,3,7,9. Seeing as multiples of 12 end in even digits, this doesn't provide obvious shortcut for the rounding calc. An example is n=10007, where 3^n/12= xxx182.25.
See A351336 for the odd pseudoprimes to base 3. I have variant code that eliminates some as well as some actual that is fairly fast.
Another prime-rich sequence is A158034 https://oeis.org/A158034 . Thru the first 30K terms it is 99.91 %prime (0.09% composite). However, it does NOT generate every prime and is slow. It has a nice "predictable" graph. Its composites are found in A235540 https://oeis.org/A235540
A135508 yields the first occurrence of any prime at n+1. This can be used to run the mechanism above any threshold desired, looping until value=n+1. That value will be a prime.
adding that condition yields a sequence with terms purely distinct primes: 2,3,7,11,17,23,29,37,41,47,53,59,67,79,83,89,.... This script has a subroutine that will report the earliest term > user's size target that will be guaranteed to be prime: A135508.gp It is recursive, so jumping ahead of all prior terms is not possible.
Cloitre's sequences below are purported to effectively only generate primes.
A186253 begins 2, 5, 11, 23, 47, 79, 157, 313, 619, 1237, 2473, 4909, 9817, 19603,....It appears to contain only distinct prime terms. The terms appear to double approx and Cloitre notes the higher of the twin prime pairs are absent besides 5.
A186254 begins 5, 17, 53, 149, 449, 1289, 3761, 11261, 33773, 101117, 302681,...
A186255 begins 17, 71, 269, 1013, 4007, 15923, 63521, 253949, 1014317, 4056893,...
A186256 begins 11, 59, 251, 1259, 6299, 31387, 152083, 758971, 3790651,...
A186257 begins 89, 479, 2879, 17099, 99839, 599009, 3592859, 21557099,...
A186258 begins 17, 101, 461, 2801, 19553, 136649, 955841, 6684749, 46777229,...
A186259 begins 167, 797, 6299, 48817, 389437, 3114313, 24910031, 199280101,...
A186260 begins 23, 167, 1511, 13463, 120167, 1076039, 9684359, 87158999,...
A186261 begins 269, 2699, 26423, 259829, 2595473, 25954289, 259491059,...
A186262 SKIP
A186263 begins 29, 269, 2969, 32609, 357169, 3928669, 43213789, 475113649,...
Bouras ( https://easychair.org/publications/preprint/k83H) provides an 8/2022 recursive method as well.
See A356247, A356360, A357127, Can see https://zenodo.org/record/7212512 See my ncpn_Bouras.gp for A356360 I think (new maxs)
Of course there are ways to do limited iterations to locate a prime of a desired size.
Here is a table $$PEND of the various sequences showing relative speeds&term digits (all via the same laptop):
Seq
|
Time (1st 1000 distinct prime terms)
|
k, digits~k*n
|
Note 1
|
basis |
Note 2 |
time to prime target>1E7 |
same to targ>1E20 |
My usefulness rank (1=best) |
A088198
|
n/a
|
n/a
|
Adorjan
|
|
10 distinct primes in first 10K terms (lousy)
|
|
|
|
A221869
|
(no Pari script)
|
n/a
|
Rowland
|
GCD |
3074 distinct primes in first 10^100 terms (poor)
|
|
|
|
A135508
|
125ms (very fast)
|
0.000793 |
Cloitre
|
LCM |
1025 distinct primes in first 10K terms |
~20hrs (10000019) |
|
2 |
A186253
|
xxx hrs (very slow)
|
yyyyyyyyyy
|
Cloitre
|
GCD |
xxxx distinct primes in first ** terms |
|
|
|
(preprint) NOT A356247 ordered w/o 1's
|
234ms (very fast) Bouras_paper2.gpA129912 |
0.000571
|
Bouras
|
GCD |
7537 distinct primes in first 10K terms
|
~15ms (10020389), fast |
|
1 |
A135506 |
very fast per A135508 |
|
Cloitre |
LCM |
every prime except 3; bfile 65537 terms
|
|
|
2 |
A271116 |
instant (very fast)
100 mill terms in 4.5 min
|
0.00400
|
Alkan |
mul/div
|
every prime except 2&3, very few composites;M34 in 17hrs
|
|
|
1 |
A125958 |
**
|
|
Adamchuk |
mul/div
|
only primes, slow; many duplicates
|
|
|
|
A10051 |
875ms (fast, but slows signif.
|
|
Gauthier&Urban |
fact/mod |
ref: arxiv 2202.11908; every prime |
|
|
3 |
A081257 |
instant (very fast)
1 mill terms in 3 min
|
|
Fricke |
GPF |
relates to A002383; ~ 7300 distinct primes in the first 1mill terms; A081256 as well
|
|
|
1 |
combo_BourasCloitre2.gp |
lower memory use
|
|
McEachen |
LCM/GCD |
no pseudo,97% of primes
will miss some upr TwinPrimes and others
|
instant.
|
|
2 |
Here are some of the pertinent scripts: A186253.gp Bouras_paper2.gp. Here is an interesting plot of A271116 vs A135506:
Sequence A125958 only has prime terms. https://oeis.org/A213901 also, though it is quite slow to generate them. A272480 purportedly can generate a lot of primes.
Sequence A081257 - <73% distinct thru 1mill terms, fast (same applies to A081256 )
Related to A271116, there's a derivative script that generates only primes with ending digits 3&9 and is more sparse, though it is extremely prime-dense.
That is a custom script and screens out many of the pseudos of A271116. Running thru n=50mill the sequence is 99.95%prime with 19 pseudoprimes to base-3. The max term has value=49998919.
The script screened out 1551 such pseudos. The script is on this site as A271116G.gp. It returns a 200 million PRP in ~ **
Now for the combo Cloitre-Bouras method, stats for as high as I've taken it follow.
6hrs thru (225K) 240821 96.80% via 240821./primepi(3479057), missed 7968
** (450K) **
Here is a July 2023 Quantas article that relates: https://www.quantamagazine.org/how-to-build-a-big-prime-number-20230713/
Contrarian, A005230 contains very few primes (0.014% ie 7 out of the 1st 50K).
Bouras A370026 has about 24% of terms prime (rest=1) thru 70K terms (Feb 28 2024).
Bouras A369797 is similar (terms all 1 or primes).
*****************************************************************************************
For just large prime generation, see:
Lopez.pdf (Lopez&Thacker)
John Cook's blog post: https://www.johndcook.com/blog/2018/08/15/find-large-primes/
Here's my shot at the subject: largest.gp
***************************************************************************
12/22/2023 I looked over a draft OEIS sequence submittal and noted a connection from it to A000295 (Eulerian numbers)
It indicates a strong correlation such that it implies a prime number can usually be found near (n^2-n-1).
The corresponding primes seen : 7, 13, 29, 59, 127, 251, 1013,1021,8191,16363,65519,65521,131063,524287,1048559, 2097143, 4194301,....
For example, 4194301 stems from 1+bitxor( 14680063, 14680067 ). Of course, in this example requires knowing 2 consecutive primes >> the resulting prime identified.
Intersection of A014657 and A337803 excluding squares yields ~ 90% primes thru n=270000
Another interesting sequence is A105551, which produces a lot of primes and semiprimes. Its basic equation is n^3 + n^2 + 71.
So as example, let n=10000. We get 4 pf's, so we move to 10001. Here we get 3 pfs, 17,23 and the large 2558567903. The first prime is seen by n=10006 ( 1001901200323 ).
Yet another mechanism stems from A307833. one can generate primes easily (minimal iterations).
From A038510 one sees the check for many pseudoprimes ( if (n^4)%30==1 eg 77,119 etc BUT it also screens out true primes, so is not useful.
Comments (0)
You don't have permission to comment on this page.