mersenneforum.org  

Go Back   mersenneforum.org > New To GIMPS? Start Here! > Information & Answers

Reply
 
Thread Tools
Old 2017-02-21, 07:49   #1
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

23×3×79 Posts
Default 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.
a1call is offline   Reply With Quote
Old 2017-02-21, 08:34   #2
axn
 
axn's Avatar
 
Jun 2003

7·11·61 Posts
Default Loophole abuse

2n+1
axn is offline   Reply With Quote
Old 2017-02-21, 09:08   #3
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

23·3·79 Posts
Default

Quote:
Originally Posted by axn View Post
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.

Last fiddled with by a1call on 2017-02-21 at 09:30
a1call is offline   Reply With Quote
Old 2017-02-21, 12:12   #4
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

838410 Posts
Default

Quote:
Originally Posted by a1call View Post
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.
science_man_88 is offline   Reply With Quote
Old 2017-02-21, 13:52   #5
axn
 
axn's Avatar
 
Jun 2003

7·11·61 Posts
Default

Quote:
Originally Posted by a1call View Post
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.
axn is offline   Reply With Quote
Old 2017-02-21, 18:01   #6
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

23·3·79 Posts
Default

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.
a1call is offline   Reply With Quote
Old 2017-02-21, 18:28   #7
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

216468 Posts
Default

Quote:
Originally Posted by a1call View Post
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
Batalov is offline   Reply With Quote
Old 2017-02-21, 22:22   #8
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

100000110000002 Posts
Default

Quote:
Originally Posted by a1call View Post
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
science_man_88 is offline   Reply With Quote
Old 2017-02-22, 05:59   #9
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

111011010002 Posts
Default

Thank you very much Batalov,
I have to be careful, what I wish for.
Still studying into it.
a1call is offline   Reply With Quote
Old 2017-02-23, 01:17   #10
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
Rep├║blica de California

2·13·443 Posts
Default

The odd ones.
ewmayer is offline   Reply With Quote
Old 2017-02-23, 02:41   #11
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

22·3·172 Posts
Default

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.
Dr Sardonicus is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Smallest prime of the form a^2^m + b^2^m, m>=14 JeppeSN Math 114 2018-12-16 01:57
Probability that N is prime given each divisor of N has the form 2*k*p+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

All times are UTC. The time now is 19:23.

Thu Sep 24 19:23:54 UTC 2020 up 14 days, 16:34, 0 users, load averages: 1.57, 1.72, 1.87

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.