| 
  • If you are citizen of an European Union member nation, you may not use this service unless you are at least 16 years old.

  • You already know Dokkio is an AI-powered assistant to organize & manage your digital files & messages. Very soon, Dokkio will support Outlook as well as One Drive. Check it out today!

View
 

Generating Some Primes

Page history last edited by Bill McEachen 3 weeks, 6 days ago

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.