mersenneforum.org Most Abundant form of Prime Numbers
 Register FAQ Search Today's Posts Mark Forums Read

 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
2017-02-21, 09:08   #3
a1call

"Rashid Naimi"
Oct 2015
Remote to Here/There

2,333 Posts

Quote:
 Originally Posted by axn 2n+1
I would have thought something along the lines of:
m.n#(+-)p, p>n

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.

Last fiddled with by a1call on 2017-02-21 at 09:30

2017-02-21, 12:12   #4
science_man_88

"Forget I exist"
Jul 2009
Dartmouth NS

841810 Posts

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.

2017-02-21, 13:52   #5
axn

Jun 2003

5×1,087 Posts

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.

 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-21, 18:28   #7
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

1005210 Posts

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

2017-02-21, 22:22   #8
science_man_88

"Forget I exist"
Jul 2009
Dartmouth NS

2·3·23·61 Posts

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

Last fiddled with by science_man_88 on 2017-02-21 at 22:33

 2017-02-22, 05:59 #9 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 44358 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 ∂2ω=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 184216 Posts 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post JeppeSN Math 117 2022-08-30 16:41 carpetpool Miscellaneous Math 6 2017-09-01 13:59 PawnProver44 Miscellaneous Math 9 2016-03-19 22:11 MercPrime Information & Answers 5 2013-05-12 22:03 juergen Math 2 2004-04-17 12:19

All times are UTC. The time now is 01:34.

Sat Jan 28 01:34:20 UTC 2023 up 162 days, 23:02, 0 users, load averages: 1.48, 1.23, 1.14