wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> general problem-solving / chatting / whatever >> 2 questions about primes
        
(Message started by: BenVitale on Feb 28^th, 2008, 2:31pm)

Title: 2 questions about primes
Post by BenVitale on Feb 28^th, 2008, 2:31pm

(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.

Title: Re: 2 questions about primes
Post by towr on Feb 28^th, 2008, 3:09pm

on 02/28/08 at 14:31:52, 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 2^32,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.

Title: Re: 2 questions about primes
Post by Eigenray on Feb 28^th, 2008, 3:30pm

on 02/28/08 at 14:31:52, BenVitale wrote:

It's not that Mersenne numbers tend to be prime, it's just vastly easier to test them.

on 02/28/08 at 15:09:54, 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 2^32,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 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pi.gif(32582657) numbers in that range, in which case you'd expect only 1/[log(2) log(32582657)] ~ 0.09 primes.

Title: Re: 2 questions about primes
Post by BenVitale on Feb 28^th, 2008, 10:41pm

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 ?

Title: Re: 2 questions about primes
Post by Eigenray on Feb 28^th, 2008, 11:06pm

Because you only need to consider the http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pi.gif(32582657) = 2007537 Mersenne numbers of the form 2^p-1 for p prime, p http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif 32582657.

And if i pick http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pi.gif(n) numbers at random between 1 and 2ⁿ, the expected number of primes is http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pi.gif(n)*http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pi.gif(2ⁿ)/2ⁿ ~ (n/log n) * (2ⁿ/log(2ⁿ))/2ⁿ = 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 2^p-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).

Title: Re: 2 questions about primes
Post by BenVitale on Feb 28^th, 2008, 11:22pm

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'?

Title: Re: 2 questions about primes
Post by towr on Feb 29^th, 2008, 12:00am

on 02/28/08 at 15:30:39, 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 2^32,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 2^9,941

3^k-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 )

Title: Re: 2 questions about primes
Post by Eigenray on Feb 29^th, 2008, 4:22pm

Right, I should be comparing M(x) = #{Mersenne primes 2^p_n-1 : n http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif x} to

A(x) = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif_k=1^x 1/log(2^p_k-1) ~ 1/log(2)*http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif 1/p_k ~ [ log(log(x log x)) + (Meissel-Mertens) ]/log(2).

Similarly, should compare N(x) = #{primes of the form 3ⁿ-2 : n http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif x}, to

B(x) = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif 1/log(3ⁿ-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 = e^x. 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 3ⁿ-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 2^p-1 is only divisible by primes q which are 1 mod p (and http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pm.gif1 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.

Title: Re: 2 questions about primes
Post by BenVitale on Feb 29^th, 2008, 4:39pm

Can you think of some ways on how we can construct polynomials that produce prime numbers with high frequency?

Title: Re: 2 questions about primes
Post by Eigenray on Feb 29^th, 2008, 7:10pm

on 02/29/08 at 16:39:38, BenVitale wrote:

Can you think of some ways on how we can construct polynomials that produce prime numbers with high frequency?

The [link=http://en.wikipedia.org/wiki/Bateman-Horn_conjecture]Bateman-Horn[/link] 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) = #{nhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif 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 n^d, then we would expect

E(x) = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif_n=1^x 1/log(n^d) ~ 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 = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/prod.gif_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 = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/prod.gif_p|A 1/(1-1/p) = A/http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/varphi.gif(A),

and the number of primes of the form An+B, with n<x should be ~ A/http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/varphi.gif(A) Li(x). Equivalently, the number of primes of the form An+B with An+B < x should be ~ A/http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/varphi.gif(A) Li(x/A) ~ Li(x)/http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/varphi.gif(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) = n² + 1, then N(2) = 1, and for p odd, N(p) = 1 + (-1|p), where (-1|p) is the Legendre symbol, and

C = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/prod.gif_{p odd} [ 1 - (-1|p)/(p-1) ] ~ 1.37.

Or if f(n) = n²+n+1, N(3) = 1, and N(p) = 1 + (-3|p), so

C = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/prod.gif_{p http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ne.gif 3} [ 1 - (-3|p)/(p-1) ] ~ 2.24.

And of course, there's the famous f(n) = n² + n + 41. Here N(163)=1, and otherwise N(p) = 1 + (-163|p), and C ~ 6.64. Compared to n²+n+43 (C ~ 1.26) and n²+n+39 (C ~ 1.003), this is pretty remarkable.

The rather deep reason for this is as follows: Say f(n) = n² + n + (q+1)/4, where q=3 mod 8 is prime. Then N(p) = 1+(-q|p) = 1 + (p|q), and

C = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/prod.gif_p [ 1 - (p|q)/(p-1) ].

However, there is a similar product

http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/prod.gif_p [ 1 - (p|q)/p ] = 1/L(1) = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gifq / ( http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pi.gifh )

where h is the class number http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbq.gif(http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif{-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 e^{http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pi.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif163} is so close to an integer; the integer it's close to is actually 744 minus the j-invariant of the lattice http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbz.gif[(1+http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif{-q})/2].)

Title: Re: 2 questions about primes
Post by BenVitale on Feb 29^th, 2008, 10:28pm

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?

Title: Re: 2 questions about primes
Post by Eigenray on Feb 29^th, 2008, 10:41pm

Which part? f is a polynomial of degree d, so f(n) ~ n^d. The probability that a random number near n^d is prime is ~ 1/log(n^d) = 1/d * 1/log(n). Approximating the sum 1 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif n http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif x by the integral, we get

E(x) ~ 1/d http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif1/log(n) ~ 1/d http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/int.gif dt/log t = 1/d Li(x).

Title: Re: 2 questions about primes
Post by BenVitale on Mar 1^st, 2008, 2:15am

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.

Title: Re: 2 questions about primes
Post by Eigenray on Mar 1^st, 2008, 11:47am

Earlier I showed how the analytic class number formula and the Bateman-Horn conjecture together predict that n²+n+(q+1)/4 is asymptotically more likely to be prime the larger q is, and the smaller the class number h of http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbq.gif(http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif-q) is.

In fact, let p be prime, and q=4p-1. Then the following are equivalent:
(A) f(n) = n²+n+p is prime for 0 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif n < p-1,
(B) K=http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbq.gif(http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif-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 = (a²+qb²)/4 for some a,b. But since r is the smallest prime factor of f(n) < f(p-1) = p², we have

r = (a²+qb²)/4 < p = (1+q)/4.

This forces either r=a²/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/http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pi.gif)http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gifq 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 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif n http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif r-1 < 2/http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pi.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gifq - 1 < p-1.

So by assumption, f(n) is prime, and we must have r = f(n) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ge.gif f(0) = p, a contradiction.

Title: Re: 2 questions about primes
Post by BenVitale on Mar 1^st, 2008, 1:36pm

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.

Title: Re: 2 questions about primes
Post by BenVitale on Mar 1^st, 2008, 4:10pm

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)?

Title: Re: 2 questions about primes
Post by Eigenray on Mar 1^st, 2008, 9:14pm

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 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/to.gif http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/infty.gif. The factor (1-1/p) in the denominator is there for comparison to a random number (the http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif 1/log(n^d) ~ 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.

Title: Re: 2 questions about primes
Post by BenVitale on Mar 2^nd, 2008, 12:49am

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)?

Title: Re: 2 questions about primes
Post by Eigenray on Mar 2^nd, 2008, 10:54am

If A = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/prod.gif p^a, then

http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/varphi.gif(A) = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/prod.gif p^a-1(p-1) = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/prod.gif p^a(1-1/p) = A*http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/prod.gif (1-1/p).

Title: Re: 2 questions about primes
Post by BenVitale on Mar 17^th, 2008, 7:50pm

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?

Title: Re: 2 questions about primes
Post by BenVitale on Mar 19^th, 2008, 11:01pm

Can anyone help?

Title: Re: 2 questions about primes
Post by BenVitale on Mar 24^th, 2008, 4:20pm

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.

Title: Re: 2 questions about primes
Post by Eigenray on Mar 25^th, 2008, 3:40pm

Fix p and let A(k) = 2^{p^k} + 1, B(k) = 2^{p^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 2^{p^k} http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif 1. But then A(k+1) - A(k) = (2^{p^k})^p - 2^{p^k} http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif 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 2^{p^k} http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif -1, and B(k+1) - B(k) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif (-1)^p - (-1) = 0, when p is odd. So we get A(k) | B(k+1)/B(k) - 1.

Title: Re: 2 questions about primes
Post by BenVitale on Apr 26^th, 2008, 4:01pm

Can one find any value for n other than 1, 2, and 4, such that n^n+1 is a prime?

Title: Re: 2 questions about primes
Post by Sir Col on Apr 26^th, 2008, 5:03pm

Numbers of the form, nⁿ+1 are called Sierpinski numbers, with 2, 5, and 257 being the only known primes.
http://mathworld.wolfram.com/SierpinskiNumberoftheFirstKind.html

Title: Re: 2 questions about primes
Post by BenVitale on Jun 27^th, 2008, 10:40pm

First I need to define some terms and give some examples (the examples are mostly there to make the problem more interesting).

Let N = p₁*p₂*...*P_k be a positive squarefree integer.

Define s(n) = gcd(p₁ - 1, p₂ - 1,...., p_k - 1).

Now if k is the largest positive integer such that N is less than
2^(s/k) then we shall say that N is a Mersenne-k integer (If no such k exists than we shall say that N is a Mersenne-0 integer).

Examples: If N = 2^p - 1 is a composite Mersenne number, then because any Mersenne number satisfies the property that any prime factor q satisfies q = 1 mod(2p), then we have that s(n) is greater than or equal to 2p.

If s(n) = 2p then we have that N is a Mersenne-2 integer because N is less than 2^(s/2) = 2^p but is not less than 2^(s/3).

Other integers which are Mersenne-2 (at least) numbers are composite Wagstaff integers (integers of the form ((2^p +1)/3)).

Integers which are always (at least) Mersenne-3 are composite Fermat numbers since if N = 2^{(2^p)} + 1 is composite, then for any prime factor q, we have q = 1 mod(2^{(p +2)}).

In fact, composite Fermat numbers are just 1 unit away from being Mersenne-4 integers so they are particular special.

QUESTION: Find an efficient method to generate Mersenne-k numbers for any given integer k.

......................................................

In this post I'm going to describe one (not so efficient) method. Hopefully it might help others to come up with something better.

One method I've used for generating such integers (although I'm not sure this technique will work for very large integers k) is to consider integers which are generalizations of Mersenne and Wagstaff integers.

EXAMPLE: Consider integers of the form (2^n -1)/D or (2^n + 1)/L where n is an odd squarefree integer and
D = lcm(2^(n/p₁) - 1 , 2^(n/p₂) - 1, ...... , 2^(n/p_k) - 1)

and p₁, p₂,...p_k are the prime factors of n.

Similarily L = lcm(2^(n/p₁) + 1 , 2^(n/p₂) + 1, ...... , 2^(n/p_k) + 1).

(Note: notice these integers are just the primitive components of the numbers 2^n -1 and 2^n +1).

It is not particularily difficult to show that any prime factor q of (2ⁿ -1)/D or (2ⁿ + 1)/L is such that q = 1 mod(2n).

Examples: 2¹⁰⁵ -1/D where D = lcm(2³⁵ - 1 , 2²¹ - 1, 2¹⁵ - 1)

Written out fully this integer is 473474689919911 and because every prime factor q of this number is such that q = 1 (mod 210) we have that this number is Mersenne-4 since it is less than 2^(210/4) but not 2^(210/5).

We can of course find integers that are Mersenne-k for larger k than 4, but this requires a much larger n. Also n must be a product of a sufficient number of small prime factors(can you see why). This isn't good since 2ⁿ - 1/D goes up exponentially for larger n. In fact I would guess that something like Mersenne-8 integer may well have something like a billion digits using this method, which is why I'm asking if anything can think up of a more efficient method than this.

.....................

We could just take a set of primes s.t. the GCD of the p_i - 1 is large and multiply them, just take some number D and look for primes of the form p=1 (mod D).

This technique was used to actually find Carmichael numbers.

A really spectacular method would be one that doesn't involve finding prime numbers of the desired form before hand to create the desired integer.