Author |
Topic: 2 questions about primes (Read 3940 times) |
|
Benny
Uberpuzzler
Gender: 
Posts: 1024
|
 |
2 questions about primes
« on: Feb 28th, 2008, 2:31pm » |
 Quote  Modify
|
(1) What is it about Mersenne numbers that causes them to be prime so often?
(2) Are there other kinds of numbers that take on prime values with an even higher frequency than Mersenne number?
..............................................
(1) I think the first question can be answered as follows: It's not that Mersenne numbers tend to be prime, it's just vastly easier to test them. Where for most numbers one needs to do exhaustive factoring to prove a number prime, it is possible to test a Mersenne number for primality through rotation and addition only, using a method called the "Lucas-Lehmer test."
Your thoughts, please.
|
|
 IP Logged |
If we want to understand our world — or how to change it — we must first understand the rational choices that shape it.
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: 2 questions about primes
« Reply #1 on: Feb 28th, 2008, 3:09pm » |
Quote Modify
|
on Feb 28th, 2008, 2:31pm, BenVitale wrote:| (1) What is it about Mersenne numbers that causes them to be prime so often? |
|
Often?
There are so far only 44 known Mersenne primes. The largest known mersenne prime is 232,582,657-1, so you can assume about in the order of 32 million Mersenne prime candidates have been tested.
44 out of 32 million is not a particularly impressive frequency.
|
| « Last Edit: Feb 28th, 2008, 3:11pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: 2 questions about primes
« Reply #2 on: Feb 28th, 2008, 3:30pm » |
Quote Modify
|
on Feb 28th, 2008, 2:31pm, BenVitale wrote:| It's not that Mersenne numbers tend to be prime, it's just vastly easier to test them. |
|
on Feb 28th, 2008, 3:09pm, towr wrote:| 44 out of 32 million is not a particularly impressive frequency. |
|
But it's impressive for numbers of that size:
If you were to pick 32,582,657 numbers uniformly at random between 1 and 232,582,657, you would only expect to find around 1/log(2) ~ 1.44 primes. But if you pick the 32,582,657 Mersenne numbers in the same interval, you'd find at least 44 primes.
It may be even more fair to consider picking only  (32582657) numbers in that range, in which case you'd expect only 1/[log(2) log(32582657)] ~ 0.09 primes.
|
| « Last Edit: Feb 28th, 2008, 5:00pm by Eigenray » |
IP Logged |
|
|
|
Benny
Uberpuzzler
Gender:
Posts: 1024
|
|
Re: 2 questions about primes
« Reply #3 on: Feb 28th, 2008, 10:41pm » |
Quote Modify
|
It may be even more fair to consider picking only pi(32582657) numbers in that range, in which case you'd expect only 1/[log(2) log(32582657)] ~ 0.09 primes.
Why is that ?
|
|
IP Logged |
If we want to understand our world — or how to change it — we must first understand the rational choices that shape it.
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: 2 questions about primes
« Reply #4 on: Feb 28th, 2008, 11:06pm » |
Quote Modify
|
Because you only need to consider the (32582657) = 2007537 Mersenne numbers of the form 2p-1 for p prime, p  32582657.
And if i pick (n) numbers at random between 1 and 2n, the expected number of primes is (n)*(2n)/2n ~ (n/log n) * (2n/log(2n))/2n = 1/[log(2) log(n)].
But on second thought this isn't a fair way to compare them, because the above obviously goes to 0 as n does, whereas the number of Mersenne primes 2p-1 with p<n obviously doesn't, even if there are only finitely many Mersenne primes (in which case they would certainly not be any more likely to be prime than other numbers their size).
|
|
IP Logged |
|
|
|
Benny
Uberpuzzler
Gender:
Posts: 1024
|
|
Re: 2 questions about primes
« Reply #5 on: Feb 28th, 2008, 11:22pm » |
Quote Modify
|
Let's consider the unusual primes.
Define a set of numbers that have a common form as 'Unusual' if those numbers are prime with
a relativilty high frequency, and this frequency cannot be accounted for using the theory mentioned above.
Example: Consider the set of Double Mersenne numbers. That is, a number of the form 2^(Mp) - 1
where Mp denotes a Mersenne prime. These numbers are Mersenne numbers except that this time the prime in the exponent is a Mersenne prime.
What makes Double Mersenne numbers 'Unusual' is the fact that they are prime with very high frequency (as compared to their relative size), and this frequency cannot be accounted for using the ideas presented above for Mersenne numbers.
For example, the first 5 Mersenne double primes are known to be prime.
That is 2^3 -1, 2^7 -1, 2^31 -1, 2^127 -1, and 2^8191 -1 are all prime.
Here's a much harder question:
Why are Double Mersenne numbers prime with such a high frequency?
Can you find other types of numbers that could well be considered 'Unusual'?
|
|
IP Logged |
If we want to understand our world — or how to change it — we must first understand the rational choices that shape it.
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: 2 questions about primes
« Reply #6 on: Feb 29th, 2008, 12:00am » |
Quote Modify
|
on Feb 28th, 2008, 3:30pm, Eigenray wrote:But it's impressive for numbers of that size:
If you were to pick 32,582,657 numbers uniformly at random between 1 and 232,582,657 |
|
How about if you pick them in an exponential distribution, like the Mersenne primes?
After all, half of the known Mersenne primes are smaller than 29,941
3k-2 seems to be prime almost as often as Mersenne numbers (from the small sequence that's given at http://www.research.att.com/~njas/sequences/A014232 )
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
Right, I should be comparing M(x) = #{Mersenne primes 2pn-1 : n x} to
A(x) =  k=1x 1/log(2pk-1) ~ 1/log(2)* 1/pk ~ [ log(log(x log x)) + (Meissel-Mertens) ]/log(2).
Similarly, should compare N(x) = #{primes of the form 3n-2 : n x}, to
B(x) = 1/log(3n-2) ~ (log x + EulerGamma)/log(3).
Attached are plots of y=M(u)/A(u) (upper left), and y=N(u)/B(u) (upper right), where u = ex. In the bottom row is [M(u)-M(u-1)]/[A(u)-A(u-1)] (left), and [N(u)-N(u-1)]/[B(u)-B(u-1)].
Note that 3n-2 is never divisible by 2 or 3, so we should expect it to be prime at least 2*3/2 = 3 times as often as a random number in the same range. From the graph, N/B doesn't look like it will exceed this.
M/A, however, seems happy to go to infinity. This may be because 2p-1 is only divisible by primes q which are 1 mod p (and  1 mod 8). So we'd expect to to be prime an extra fraction of the time, which should be a product of q/(q-1) over some set of disallowed primes q, and this goes to infinity as we take more and more factors.
|
| « Last Edit: Feb 29th, 2008, 4:32pm by Eigenray » |
IP Logged |
|
|
|
Benny
Uberpuzzler
Gender:
Posts: 1024
|
|
Re: 2 questions about primes
« Reply #8 on: Feb 29th, 2008, 4:39pm » |
Quote Modify
|
Can you think of some ways on how we can construct polynomials that produce prime numbers with high frequency?
|
|
IP Logged |
If we want to understand our world — or how to change it — we must first understand the rational choices that shape it.
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: 2 questions about primes
« Reply #9 on: Feb 29th, 2008, 7:10pm » |
Quote Modify
|
on Feb 29th, 2008, 4:39pm, BenVitale wrote:| Can you think of some ways on how we can construct polynomials that produce prime numbers with high frequency? |
|
The Bateman-Horn conjecture predicts that if f is an irreducible integer polynomial of degree d, and there is no prime p such that for all n, p|f(n), then
P(x) = #{n x : f(n) is prime} ~ C/d Li(x)
for some constant C. Note that if f(n) were a random integer which is approximately nd, then we would expect
E(x) = n=1x 1/log(nd) ~ 1/d * Li(x).
So the conjecture says that asymptotically, f(n) is a constant C times more (or less) likely to be prime than a random number its size, as long as it's not trivially composite for all n. We can make C arbitrarily large, e.g., f(n) = (2*3*5*...*p)n + 1, but it will always be finite.
For each prime p, f(n) is divisible by p with probability N(p)/p, where N(p) is the number of mod p solutions to p|f(n). On the other hand, a random number is divisible by p with probability 1/p. So we should expect
C =  p (1-N(p)/p)/(1-1/p),
and this is exactly what Bateman-Horn predicts.
For example, if f(n) = An+B is linear, with (A,B)=1, then N(p)=0 when p|A, and otherwise N(p)=1. So in this case
C = p|A 1/(1-1/p) = A/ (A),
and the number of primes of the form An+B, with n<x should be ~ A/(A) Li(x). Equivalently, the number of primes of the form An+B with An+B < x should be ~ A/(A) Li(x/A) ~ Li(x)/(A).
So for the case of a single linear polynomial, the Bateman-Horn conjecture is equivalent to Dirichlet's theorem on primes in arithmetic progressions. (However, as far as I know, this is the only case which has been proven.)
For a quadratic example, if f(n) = n2 + 1, then N(2) = 1, and for p odd, N(p) = 1 + (-1|p), where (-1|p) is the Legendre symbol, and
C = p odd [ 1 - (-1|p)/(p-1) ] ~ 1.37.
Or if f(n) = n2+n+1, N(3) = 1, and N(p) = 1 + (-3|p), so
C = p  3 [ 1 - (-3|p)/(p-1) ] ~ 2.24.
And of course, there's the famous f(n) = n2 + n + 41. Here N(163)=1, and otherwise N(p) = 1 + (-163|p), and C ~ 6.64. Compared to n2+n+43 (C ~ 1.26) and n2+n+39 (C ~ 1.003), this is pretty remarkable.
The rather deep reason for this is as follows: Say f(n) = n2 + n + (q+1)/4, where q=3 mod 8 is prime. Then N(p) = 1+(-q|p) = 1 + (p|q), and
C = p [ 1 - (p|q)/(p-1) ].
However, there is a similar product
p [ 1 - (p|q)/p ] = 1/L(1) =  q / ( h )
where h is the class number  ({-q}) (a special case of the analytic class number formula). So we should expect C to be large when the second product is also large, which happens when q is large but h is small. The smallest h can be is 1, and the largest q for which this happens is q=163. (This is also the reason e163 is so close to an integer; the integer it's close to is actually 744 minus the j-invariant of the lattice  [(1+{-q})/2].)
|
| « Last Edit: Feb 29th, 2008, 7:20pm by Eigenray » |
IP Logged |
|
|
|
Benny
Uberpuzzler
Gender:
Posts: 1024
|
|
Re: 2 questions about primes
« Reply #10 on: Feb 29th, 2008, 10:28pm » |
Quote Modify
|
I don't understand, the second statement in the beginning, that is "Note that if f(n) were a random integer which is approximately n^d, then we would expect
E(x) = SUM [n=1,x] 1/log(n^d) ~ 1/d * Li(x)."
Could you please clarify?
|
|
IP Logged |
If we want to understand our world — or how to change it — we must first understand the rational choices that shape it.
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: 2 questions about primes
« Reply #11 on: Feb 29th, 2008, 10:41pm » |
Quote Modify
|
Which part? f is a polynomial of degree d, so f(n) ~ nd. The probability that a random number near nd is prime is ~ 1/log(nd) = 1/d * 1/log(n). Approximating the sum 1 n x by the integral, we get
E(x) ~ 1/d 1/log(n) ~ 1/d  dt/log t = 1/d Li(x).
|
| « Last Edit: Feb 29th, 2008, 10:44pm by Eigenray » |
IP Logged |
|
|
|
Benny
Uberpuzzler
Gender:
Posts: 1024
|
|
Re: 2 questions about primes
« Reply #12 on: Mar 1st, 2008, 2:15am » |
Quote Modify
|
Thanks. In my next post, i'll put a heuristic reasoning with quadratic polynomials to higher degrees.
In the meantime, I would like to make the following comments:
the Bateman-Horn conjecture, which is one of the most outstanding open problems in number theory (with little hope of solution anytime soon)
If we restrict ourselves to quadratic polynomials with negative discriminant, then the frequency of prime values is directly related to the class number of the corresponding quadratic extention.
For example, the discriminants -3, -7, -11, -19, -43, -67, -163 all have class number one. If we take a number a from that list and consider the polynomial x^2 + x + (1-a)/4, having discriminant a, these polynomials will produce many prime values.
|
|
IP Logged |
If we want to understand our world — or how to change it — we must first understand the rational choices that shape it.
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: 2 questions about primes
« Reply #13 on: Mar 1st, 2008, 11:47am » |
Quote Modify
|
Earlier I showed how the analytic class number formula and the Bateman-Horn conjecture together predict that n2+n+(q+1)/4 is asymptotically more likely to be prime the larger q is, and the smaller the class number h of (-q) is.
In fact, let p be prime, and q=4p-1. Then the following are equivalent:
(A) f(n) = n2+n+p is prime for 0 n < p-1,
(B) K=(-q) has class number 1.
If p=2, we can check (A) and (B) both holds, so assume now that p>2 is odd.
First suppose (B). If f(n) is not prime for some n < p-1, let r be the smallest prime factor. Since f(n)=0 mod r, 1-4p=-q must be a square mod r. But this means the ideal (r) splits in K, and since h(K)=1, r must be a product of two elements each of norm r. So r = (a2+qb2)/4 for some a,b. But since r is the smallest prime factor of f(n) < f(p-1) = p2, we have
r = (a2+qb2)/4 < p = (1+q)/4.
This forces either r=a2/4 or r=q/4, which are both impossible.
Now suppose (A) holds. In order to show K has class number 1, it suffices to show that each prime r below the Minkowski bound M = (2/)q factors into principal prime ideals.
r=2 is inert in K because p is odd, making -q=5 mod 8. For r odd, if -q is not a square mod r, then r remains prime in K. And if -q is a square mod r, then f(n) = 0 mod r has a solution, with
0 n r-1 < 2/q - 1 < p-1.
So by assumption, f(n) is prime, and we must have r = f(n)  f(0) = p, a contradiction.
|
|
IP Logged |
|
|
|
Benny
Uberpuzzler
Gender:
Posts: 1024
|
|
Re: 2 questions about primes
« Reply #14 on: Mar 1st, 2008, 1:36pm » |
Quote Modify
|
Awesome!
Note that the linear polynomial case, which is indeed the only proven case of the Bateman-Horn conjecture, is due to de-la-Vallee-Poussen and not Dirichlet. Dirichlet only showed there are infinitely many prime values to a suitable linear polynomial.
|
|
IP Logged |
If we want to understand our world — or how to change it — we must first understand the rational choices that shape it.
|
|
|
Benny
Uberpuzzler
Gender:
Posts: 1024
|
|
Re: 2 questions about primes
« Reply #15 on: Mar 1st, 2008, 4:10pm » |
Quote Modify
|
In the begining.
You wrote: "So we should expect C = Pi[p] (1 - N(p)/p)(1 - 1/p),"
- Does Pi(p) represent the number of prime numbers less than n?
- I assume that (1 - N(p)/p) represents the probability that a f(n) is not divisible by p.
From here, I assume that Pi[p] (1 - N(p)/p) represents the product of the terms (1- N(p)/p)
over every prime number from 2 to sqrt(f(n)). ie it represents the probability that f(n) is
not divisible by any of the primes from 2 to sqrt(f(n)), right?
If the above description is correct, then my question is: Why do you multiply this by (1-1/p)?
|
|
IP Logged |
If we want to understand our world — or how to change it — we must first understand the rational choices that shape it.
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: 2 questions about primes
« Reply #16 on: Mar 1st, 2008, 9:14pm » |
Quote Modify
|
The factor C accounts for how much more or less likely f(n) is to be prime than a random number its size. It is the product over all primes p of [probability p doesn't divide f(n)]/[probability p doesn't divide a random number].
For example, if f(n) is never divisible by p, then C contains the factor 1/(1-1/p) > 1, because a random number is not divisible by p only (1-1/p) of the time. If f(n) is divisible by p for a unique value of n mod p, then C contains the factor (1-1/p)/(1-1/p) = 1, since f is just as likely to be divisible by p as a random number. If f(n) has N(p) > 1 roots mod p, then f(n) is more likely to be divisible by p than a random number, and the factor is (1-N(p)/p)/(1-1/p) < 1.
We take the product over all primes because we want the asymptotic behavior as x   . The factor (1-1/p) in the denominator is there for comparison to a random number (the 1/log(nd) ~ 1/d*Li(x) factor already accounts for the probability that a random number is prime). If we were to omit the (1-1/p) factors, the product would be 0.
|
|
IP Logged |
|
|
|
Benny
Uberpuzzler
Gender:
Posts: 1024
|
|
Re: 2 questions about primes
« Reply #17 on: Mar 2nd, 2008, 12:49am » |
Quote Modify
|
Thanks. My next question is:
you wrote:
"For example, if f(n) = An+B is linear, with (A,B)=1,
then N(p)=0 when p|A, and otherwise N(p)=1.
So in this case C = Pi[p|A] 1/(1-1/p) = A/phi(A),"
Wouldn't the answer be C=1/phi(A)? Were does the A come from in A/phi(A)?
|
|
IP Logged |
If we want to understand our world — or how to change it — we must first understand the rational choices that shape it.
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: 2 questions about primes
« Reply #18 on: Mar 2nd, 2008, 10:54am » |
Quote Modify
|
If A = pa, then
(A) = pa-1(p-1) = pa(1-1/p) = A* (1-1/p).
|
|
IP Logged |
|
|
|
Benny
Uberpuzzler
Gender:
Posts: 1024
|
|
Re: 2 questions about primes
« Reply #19 on: Mar 17th, 2008, 7:50pm » |
Quote Modify
|
Given some odd prime number p, can you find a way to contruct or quickly find an integer n such that every prime factor q of n is such that q = 1 (mod p^2), and n is less than 2^p.
PS: Notice that if I remove the condition that n be less than 2^p than this problem becomes trivial.
....
According to Linnik's theorem for every p we have q1,q2 such that q1,q2 < (p^2)^C and q1=q2=1 (mod p^2) and so n = q1*q2 < p^(4C).
The bound in Linnik's theorem is conjectured to be K^2.
The problem doesn't ask us to do a computer search, but it asks a method that would enable us
to construct, generate such integers. For example, a polynomial f(x) that produces these numbers for integer values of x.
Let's do some examples with some of the restrictions lifted in order to get a better idea of the question the problem is asking
Suppose instead we wish to quickly find integers 'n' such that n is less than 2^p, and every prime factor q of n is such that q=1(modp) instead of q=1(modp^2).
ANSWER: Mersenne numbers are an easy solution to this since if n=2^p -1, then n is less than 2^p and we have that every prime factor q of n 2^p -1 is such that q=1(modp).
On the other hand, suppose we just wish to find integers n such that every prime factor q of n such that q=1(modp^2).
ANSWER: If 'a' is a positive integer greater than 1, and if a^(p^2) +1 is squarefree (and p is odd),
then the integer a^(p^2) +1/(a^p+1) can be shown to satisfy the above condition (that is, if a prime q divides a^(p^2) -1/(a^p+1) then q=1(modp^2).
how to find a set of numbers that satisfy all of the original restrictions?
|
|
IP Logged |
If we want to understand our world — or how to change it — we must first understand the rational choices that shape it.
|
|
|
Benny
Uberpuzzler
Gender:
Posts: 1024
|
|
Re: 2 questions about primes
« Reply #20 on: Mar 19th, 2008, 11:01pm » |
Quote Modify
|
Can anyone help?
|
|
IP Logged |
If we want to understand our world — or how to change it — we must first understand the rational choices that shape it.
|
|
|
Benny
Uberpuzzler
Gender:
Posts: 1024
|
|
Re: 2 questions about primes
« Reply #21 on: Mar 24th, 2008, 4:20pm » |
Quote Modify
|
There are numbers of the form (2^(p^i) -1)/(2^(p^(i-1) -1) or (2^(p^i) +1)/(2^(p^(i-1) +1) where p is a prime number, and i is an integer greater than or equal to 2.
Examples:
73 = 2^9 - 1/(2^3 - 1)
126,765,056,244,929,866,443,941,478,4001 = (2^125 +1)/(2^25 +1)
443,267,679,8593 = 2^49 -1/(2^7 -1)
First let's mention one provable property that each of these numbers has. First notice how every prime divisor p of 73 is such that p = 1(mod 9), and every prime divisor p of126,765,056,244,929,866,443,941,478,4001 is such that p = 1 (mod 125), and every prime divisor p of 443,267,679,8593 is such that p = 1 (mod 49).
It is not difficult to show that this property hold in the more general setting. That is, if q is a prime divisor of
(2^(p^i) -1)/(2^(p^(i-1) -1) or
(2^(p^i) +1)/(2^(p^(i-1) +1) then q = 1 (mod p^i).
It is in fact because of this property that integers of this form are prime numbers with high frequency (notice that 73 and 443,267,679,8593 are both prime).
Now for some not so obvious observations whose proofs (or disproof) are challenging.
Let n = (2^(p^i) -1)/(2^(p^(i-1) -1). If we let k=i-1, then
I conjecture (based on observation) that (2^(p^k) +1)/(2^(p^(k-1) +1) divides n-1.
Similarily, if n = (2^(p^i) +1)/(2^(p^(i-1) +1), and again let k = i-1,
then I conjecture that (2^(p^k) -1)/(2^(p^(k) -1) divides n-1.
Example:
Consider n=126,765,056,244,929,866,443,941,478,4001=(2^125 +1)/(2^25 +1).
Now based on my conjecture, we should have that 1082401=2^25 -1/(2^5 -1) divides n-1.
A quick check shows that this is the case.
|
|
IP Logged |
If we want to understand our world — or how to change it — we must first understand the rational choices that shape it.
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: 2 questions about primes
« Reply #22 on: Mar 25th, 2008, 3:40pm » |
Quote Modify
|
Fix p and let A(k) = 2p^k + 1, B(k) = 2p^k-1. Your claim is that B(k)/B(k-1) divides A(k+1)/A(k) - 1 and A(k)/A(k-1) | B(k+1)/B(k) - 1.
Now, mod B(k), we have 2p^k  1. But then A(k+1) - A(k) = (2p^k)p - 2p^k 1 - 1 = 0. So B(k) | A(k+1)-A(k). And since A(k) | A(k+1)-A(k), and gcd(B(k),A(k)) = 1, we have A(k)B(k) | A(k+1)-A(k), or B(k) | A(k+1)/A(k) - 1, which is in fact stronger.
Similarly, mod A(k), we have 2p^k -1, and B(k+1) - B(k) (-1)p - (-1) = 0, when p is odd. So we get A(k) | B(k+1)/B(k) - 1.
|
|
IP Logged |
|
|
|
Benny
Uberpuzzler
Gender:
Posts: 1024
|
|
Re: 2 questions about primes
« Reply #23 on: Apr 26th, 2008, 4:01pm » |
Quote Modify
|
Can one find any value for n other than 1, 2, and 4, such that n^n+1 is a prime?
|
|
IP Logged |
If we want to understand our world — or how to change it — we must first understand the rational choices that shape it.
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
