- I expect a prime for the + series under 35000

and for the - series under 30000

Harsh Aggarwal

--- In primenumbers@yahoogroups.com, mikeoakes2@a... wrote:

> How many primes N=2*a^a+-1 can we expect for X_0 <= a <= X?

>

> If N was a "typical" integer of that size, the probability of its

being prime

> would be 1/log(N), by the PNT.

>

> But N is clearly not divisible by 2, so we must multiply by 2.

>

> So, ignoring the complicated story of which primes can divide which

of these

> numbers (see another of my posts), which can be expected to add

only an

> overall multiplying factor O(1), a first guess would be:-

> count = integral{X_0 to X}dx/log(N) = integral{X_0 to X}dx/(x*log(x)

+log(2))

> ~ integral{X_0 to X}d(log(x))/log(x) ~ [log(log(X))] as X =>

infinity.

>

> So first of all: this heuristic argument indicates that there are

indeed

> infinitely many primes of each type.

>

> Putting in the numbers gives the following table:-

> X log(X) count=log(log(X))

> 10 2.3026 0.834

> 10^2 4.6052 1.527

> 10^3 6.9078 1.933

> 10^4 9.2103 2.220

> 10^5 11.5129 2.443

> 10^6 13.8155 2.626

> 10^7 16.1181 2.780

> 10^8 18.4207 2.913

> 10^9 20.7233 3.031

> 10^10 23.0259 3.137

>

> The good news: for both the "+" and "-" formulae, the number of

known primes

> (a <= 5*10^3) is actually 4, which gives some confidence that the

heuristics

> are on the right track, given that PNT is only very approximate for

these small

> values of X, etc :-)

>

> The bad news: the probability for finding a new prime increases

_extremely_

> slowly with X :-(

>

> Mike Oakes

>

>

> [Non-text portions of this message have been removed] - In a message dated 04/09/03 02:03:15 GMT Daylight Time, harsh@... writes:

> I expect a prime for the + series under 35000

On what grounds?

> and for the - series under 30000

>

(please enlighten us;-)

Mike

[Non-text portions of this message have been removed] - Mike,

You said a while back that you had a proof regarding the divisiblity of

properties of the primes=1 mod 4 with these numbers. Could you post it here

for us at all? I for one would certainly be interested.

Regards,

Paul.

__________________________________________________

Virus checked by MessageLabs Virus Control Centre. - In a message dated 04/09/03 09:17:45 GMT Daylight Time,

Paul.Jobling@... writes:

> You said a while back that you had a proof regarding the divisiblity of

So there is one reader out there who is interested, after all!

> properties of the primes=1 mod 4 with these numbers. Could you post it here

> for us at all? I for one would certainly be interested.

>

Let p be a prime = +1 mod 4, and N = 2*a^a+1.

Let a = s mod p, 0 <= s <= p-1,

and a = t mod (p-1), 0 <= t <= p-2.

N = 0 mod p iff

2*a^a = -1 mod p,

i.e. a^a = (p-1)/2 mod p,

i.e. s^a = (p-1)/2 mod p,

i.e. s^t = (p-1)/2 mod p, since s^(p-1) = 1 mod p (Fermat).

So, for each t in [0,p-2] we are looking for solutions s in [0,p-1] of

s^t = (p-1)/2 mod p (1)

Repeating the above for the "-" case, we are looking for solutions of

s^t = -(p-1)/2 mod p (2)

If t is odd, each solution of (1) gives a solution of (2) (just change the

sign of s), and vice versa.

If t is even, s^2 = -1 has a solution (-1 is a quadratic residue for primes p

= +1 mod 4), so again, each solution of (1) gives a solution of (2), and vice

versa.

QED

Mike

[Non-text portions of this message have been removed] - As Harsh announced here a while back, there is a small coordinated search

going on for primes of this form - see:

http://groups.yahoo.com/group/primenumbers/files/2%2Aa%5Ea%2B-1%20prime%20sear

ch/index.htm

so it is instructive to see how much more or less likely such numbers are to

be prime than "random" integers of the same size.

Here are the results of removing all prime factors < p_max for both the "-"

and "+" forms, compared with the same exercise for a set of numbers of the form

2*a^a+r, where the "r" values are selected randomly from the range 1<=r<=10^9.

A range of 20000 <= a <= 25000 was used, for all 3 cases, and the columns in

the following table record how many of the 5000 starting numbers remain after

sieving to the depth p_max:-

p_max "-" form "+" form "random" form

2*10 2734 1650 1698

55 2286 1367 1365

2*10^2 1856 1167 1198

2*10^3 1395 861 829

2*10^4 1020 675 642

2*10^5 592 318 479

2*10^6 501 247 420

2*10^7 431 205 ??

2*10^8 381 178 ??

2*10^9 351 156 ??

Phil Carmody's excellent "aagenm.exe" was used to obtain the results in the

2nd and 3rd columns, in about 0.8GHz-days.

For the final column PFGW was used, but its trial division is about 100 times

slower than Phil's program's, and so would have taken months to find all the

?? figures.

It is clear that more primes are to be expected from the "-" form than either

from the "+" form or from a collection of "ordinary" (odd) numbers of the

same size.

The p_max=55 row is included to enable a comparison to be made with the

theoretical prediction from my earlier posts giving the probabilities of the "-"

and "+" forms being divisible by each of the primes <= 53:-

p_max "-" form "+" form "random" form

55 2221.8 1419.8 1360.9

where the last column is of course just 5000*(1-1/3)*(1-1/5)*...*(1-1/53).

Mike

[Non-text portions of this message have been removed]