Most Abundant form of Prime Numbers

a1call · 2017-02-21, 07:49

Hi all,
From what I understand Mersenne primes are quite rare but relatively easy to prove deterministically to be prime.
Ease of proof notwithstanding, what would be the most (or more) abundant form of Prime Numbers?
Thank you in advance.

axn · 2017-02-21, 08:34

2n+1

a1call · 2017-02-21, 09:08

Quote:

Originally Posted by axn

2n+1

I would have thought something along the lines of:
m.n#(+-)p, p>n
Don't understand your title.

ETA I think from a probabilistic point of view it can be argued that 2^n+1 is less likely to be prime than 2^n-1, but not by very much.

science_man_88 · 2017-02-21, 12:12

Quote:

Originally Posted by a1call

I would have thought something along the lines of:
m.n#(+-)p, p>n
Don't understand your title.

ETA I think from a probabilistic point of view it can be argued that 2^n+1 is less likely to be prime than 2^n-1, but not by very much.

2n+1 covers all odd numbers so 2n+1 also covers all odd primes.

axn · 2017-02-21, 13:52

Quote:

Originally Posted by a1call

ETA I think from a probabilistic point of view it can be argued that 2^n+1 is less likely to be prime than 2^n-1, but not by very much.

No, no. Not 2^n+1. 2n+1. As in, all odd numbers... You haven't specified what constitutes a "form", hence the title.

Coming to 2^n+1. It isn't just "less" likely than 2^n-1. It is whole lot less likely. We expect infinitely many Mersenne primes, but only finitely many 2^n+1. Because 2^n+1 can be prime only if n is itself a power of 2. These are the Fermat numbers.

As to a good form -- after sieving, all the forms are expected to yield similar number of primes (subject to size and sieve depth). Mersenne primes can be sieved deeper (due to special property of factor), but they grow fast. GFNs (b^2^n+1) can also be similarly sieved deeper, but they grow slowly. So this would be a good form.

If we don't consider sieving, your form is a good candidate, since it gets sieve up to n for free. A better form would be m.X+/-n.Y where X.Y = p# and X and Y are almost same size and gcd(m.X,n.Y)=1.

a1call · 2017-02-21, 18:01

Thank you gentlemen. It was 4:30 in the morning and I misread the post. The odd numbers is the correct answer to my under described question. What I am looking for is an algebraic integer form which has a high likelihood of evaluating to prime numbers for high integer values. Algorithms or forms that produce large PRPs and their probability of being prime would be of interest.

Batalov · 2017-02-21, 18:28

Quote:

Originally Posted by a1call

What I am looking for is an algebraic integer form which has a high likelihood of evaluating to prime numbers for high integer values.

If you wanted to find very large primes at the maximum possible rate, then the answer is clear - cyclotomic polynomials Phi(m,x):

For m prime, only x=2 is useful, and you get Mersenne numbers
For m 2-smooth, you get generalized Fermat series
For m 3-smooth, you get generalized Eisenstein Fermats (which also happen to be generalized unique numbers when prime)
For m not 3-smooth, you get unprovable PRPs. For m=5 or 10, 7 or 14, with a great bit of luck you can find a provable prime, but this luck becomes vanishing as size grows

science_man_88 · 2017-02-21, 22:22

Quote:

Originally Posted by a1call

Thank you gentlemen. It was 4:30 in the morning and I misread the post. The odd numbers is the correct answer to my under described question. What I am looking for is an algebraic integer form which has a high likelihood of evaluating to prime numbers for high integer values. Algorithms or forms that produce large PRPs and their probability of being prime would be of interest.

it could also be argued that 6k+/-1 is a form that covers all primes greater than 3.

if conditionals are counted as part of a form then specifically you can make 2m+1 be exactly the odd primes by saying 2m+1 such that m is not of form 2ij+i+j where there are conditions on i and j. https://en.wikipedia.org/wiki/Sieve_of_Sundaram

a1call · 2017-02-22, 05:59

Thank you very much Batalov,
I have to be careful, what I wish for.
Still studying into it.

ewmayer · 2017-02-23, 01:17

The odd ones.

Dr Sardonicus · 2017-02-23, 02:41

For degree 1, a refinement of PNT (PNT for arithmetic progressions) says that, for a given n > 1, the phi(n) arithmetic progressions

n*x + b, with 0 < b < n and gcd(b, n) = 1

all contain, asymptotically, 1/phi(n) of the primes up to X as X increases without bound.

AFAIK, the question of whether a given (monic, irreducible) polynomial in Z[x] without any intrinsic prime factors even assumes infinitely many prime values is unanswered for any polynomial of degree greater than 1.

That said, in the case of quadratic polynomials particularly, one can sometimes exclude evaluations divisible by some small prime values, which may apparently increase the frequency of prime evaluations. The perennial champion is x^2 + x + 41, whose evaluations at integer x are always odd, and whose discriminant -163 is a quadratic non-residue modulo every odd prime less than 41, a circumstance which excludes any evaluations divisible by any prime less than 41.

As to expressions involving exponential functions, I offer 4 + (-1)^n. Its evaluations are prime for all positive integers n.

2017-02-21, 07:49	#1
a1call "Rashid Naimi" Oct 2015 Remote to Here/There 2,333 Posts	Most Abundant form of Prime Numbers Hi all, From what I understand Mersenne primes are quite rare but relatively easy to prove deterministically to be prime. Ease of proof notwithstanding, what would be the most (or more) abundant form of Prime Numbers? Thank you in advance.

2017-02-21, 08:34	#2
axn Jun 2003 5×1,087 Posts	Loophole abuse 2n+1

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Smallest prime of the form a^2^m + b^2^m, m>=14	JeppeSN	Math	117	2022-08-30 16:41
Probability that N is prime given each divisor of N has the form 2kp+1	carpetpool	Miscellaneous Math	6	2017-09-01 13:59
Is there a prime of the form......	PawnProver44	Miscellaneous Math	9	2016-03-19 22:11
Code for testing a prime other than form 2^n-1	MercPrime	Information & Answers	5	2013-05-12 22:03
least common multiple of numbers of the form a^x-1	juergen	Math	2	2004-04-17 12:19

2017-02-21, 18:01	#6
a1call "Rashid Naimi" Oct 2015 Remote to Here/There 2,333 Posts	Thank you gentlemen. It was 4:30 in the morning and I misread the post. The odd numbers is the correct answer to my under described question. What I am looking for is an algebraic integer form which has a high likelihood of evaluating to prime numbers for high integer values. Algorithms or forms that produce large PRPs and their probability of being prime would be of interest.

2017-02-22, 05:59	#9
a1call "Rashid Naimi" Oct 2015 Remote to Here/There 4435₈ Posts	Thank you very much Batalov, I have to be careful, what I wish for. Still studying into it.

2017-02-23, 01:17	#10
ewmayer ∂²ω=0 Sep 2002 República de California 5×2,351 Posts	The odd ones.

2017-02-23, 02:41	#11
Dr Sardonicus Feb 2017 Nowhere 1842₁₆ Posts	For degree 1, a refinement of PNT (PNT for arithmetic progressions) says that, for a given n > 1, the phi(n) arithmetic progressions nx + b, with 0 < b < n and gcd(b, n) = 1 all contain, asymptotically, 1/phi(n) of the primes up to X as X increases without bound. AFAIK, the question of whether a given (monic, irreducible) polynomial in Z[x] without any intrinsic prime factors even assumes infinitely many prime values is unanswered for any polynomial of degree greater than 1. That said, in the case of quadratic polynomials particularly, one can sometimes exclude evaluations divisible by some small prime values, which may apparently increase the frequency of prime evaluations. The perennial champion is x^2 + x + 41, whose evaluations at integer x are always odd, and whose discriminant -163 is a quadratic non-residue modulo every odd prime less than 41, a circumstance which excludes any evaluations divisible by any prime less than 41. As to expressions involving exponential functions, I offer 4 + (-1)^n. Its evaluations are prime for all* positive integers n.