Sieve needed for a^(2^b)+(a+1)^(2^b) - Page 3

robert44444uk · 2009-06-06, 06:35

Quote:

Originally Posted by geoff

Robert, I have uploaded a sieve here. See the README for instructions.

Geoff, sieve works well!

R.D. Silverman · 2009-06-08, 13:32

Quote:

Originally Posted by R.D. Silverman

I told you that some time ago. Such primes will be rare.

A more interesting question is whether there exists values of a for
which there are no primes. If so, what is the density of that set?

Here is the argument.

Let
$ f(a,b) = a^{2^n} + (a+1)^{2^n}. $

The "probability" that f(a,b) is prime is
$1/\log(f(a,b)) $
by the PNT.

The "probability" that for fixed a, f(a, b) is not prime is
$ (1 - \frac{1}{2^b log a}). $

(approximately) Replacing a by (a+1) just above would be slightly more accurate.

The probability that f(a, b) is NOT prime for ALL b is
$ y = \prod_{b=1}^{\infty} (1 - \frac{1}{2^b \log a)})$

(approximately)

Take the log of both sides and expand
$\log(1 - \frac{1}{2^b \log a})$
using Taylor series. One gets

$ \log y = - \sum_{b=1}^{\infty} ( 1/(2^b \log a) + 1/(2* 2^{2b} \log^2(a)) + ...) $

Summing over b yields
$ \log y = -( 1/(\log a) + 1/(3* 2 \log^2(a)) + 1/(7 * 3 \log^3(a)) + ....) $

This is a very rapidly decreasing series. If we just take the first term
we get $y = exp(-1/\log(a))$

Note that taking more terms just reduces the probability. We could
be a little more careful here and use Taylor series with remainder, but it
is not needed. Note that for any a

$y = exp(-1/\log(a))$

goes to one fairly quickly as a gets large.

The "expected" number of a for which there should be a prime is
then given by the following Stieltje's integral.

$ \int_{x=2}^{\infty} exp(-1/\log(x)) d[x] $

This integral is definitely bounded away from 0. One could replace
log(x) with log(x+1) for a little bit more accuracy.

This will give a rough approximation to the density of the set a for
which a prime does exist. I was a bit surprised by this result; My
a priori expectation was that the asymptotic density would be zero.

Getting even a couple of sig.figs. for this estimate would be quite
difficult, since the above analysis used a number of approximations.

Comments please.

R.D. Silverman · 2009-06-08, 13:36

Quote:

Originally Posted by R.D. Silverman

Here is the argument.

Let
$ f(a,b) = a^{2^n} + (a+1)^{2^n}. $

The "probability" that f(a,b) is prime is
$1/\log(f(a,b)) $
by the PNT.

The "probability" that for fixed a, f(a, b) is not prime is
$ (1 - \frac{1}{2^b log a}). $

(approximately) Replacing a by (a+1) just above would be slightly more accurate.

The probability that f(a, b) is NOT prime for ALL b is
$ y = \prod_{b=1}^{\infty} (1 - \frac{1}{2^b \log a)})$

(approximately)

Take the log of both sides and expand
$\log(1 - \frac{1}{2^b \log a})$
using Taylor series. One gets

$ \log y = - \sum_{b=1}^{\infty} ( 1/(2^b \log a) + 1/(2* 2^{2b} \log^2(a)) + ...) $

Summing over b yields
$ \log y = -( 1/(\log a) + 1/(3* 2 \log^2(a)) + 1/(7 * 3 \log^3(a)) + ....) $

This is a very rapidly decreasing series. If we just take the first term
we get $y = exp(-1/\log(a))$

Note that taking more terms just reduces the probability. We could
be a little more careful here and use Taylor series with remainder, but it
is not needed. Note that for any a

$y = exp(-1/\log(a))$

goes to one fairly quickly as a gets large.

The "expected" number of a for which there should be a prime is
then given by the following Stieltje's integral.

$ \int_{x=2}^{\infty} exp(-1/\log(x)) d[x] $

This integral is definitely bounded away from 0. One could replace
log(x) with log(x+1) for a little bit more accuracy.

This will give a rough approximation to the density of the set a for
which a prime does exist. I was a bit surprised by this result; My
a priori expectation was that the asymptotic density would be zero.

Getting even a couple of sig.figs. for this estimate would be quite
difficult, since the above analysis used a number of approximations.

Comments please.

Note that one thing that can be done to improve the approximations
is to observe that f(a,b) is always odd. This immediately improves the
probability of its being prime by a factor of 2.

R.D. Silverman · 2009-06-08, 20:30

Quote:

Originally Posted by R.D. Silverman

Note that one thing that can be done to improve the approximations
is to observe that f(a,b) is always odd. This immediately improves the
probability of its being prime by a factor of 2.

Discussion? Any ideas on how to get an effectively computable answer?

For those of you doing these computations, it might be nice to tally
those a less than (say) 1000 for which no prime could be found for b up to
(say) 12 or 13.

Primeinator · 2009-06-08, 20:49

Well... I decided to post since no one else replied. I followed pretty much most of the math but the reasoning is beyond me as I do not have enough mathematical background. In my spare time I am reading a book on Advanced Calculus. I also want to find some good books on number theory. I do have one question though on your last integral. Does the integral of e^(-1/log x) even have a closed form solution or does it have to be evaluated numerically?

R.D. Silverman · 2009-06-08, 21:57

Quote:

Originally Posted by Primeinator

Well... I decided to post since no one else replied. I followed pretty much most of the math but the reasoning is beyond me as I do not have enough mathematical background. In my spare time I am reading a book on Advanced Calculus. I also want to find some good books on number theory. I do have one question though on your last integral. Does the integral of e^(-1/log x) even have a closed form solution or does it have to be evaluated numerically?

It is not an elementary function.

The derivation that I gave does not require "advanced" Calculus.
It does require knowledge of the Prime Number Theorem, elementary
probability theory, and 1st yr calculus with Taylor series.

Primeinator · 2009-06-08, 23:07

Very well. Since you are about the most knowledgeable person on this forum, mathematically speaking, what books would you recommend I read to learn about number theory/prime number theory and the books required to build up to those? I have had all three levels of basic Calculus and I have also taken ordinary differential equations. I do not have time for "a lot" of reading, but math is something of a hobby of mine when I have the spare time. Because prime numbers are something I am so interested in, I am willing to take as long as is needed to learn the curriculum. Thanks.

R.D. Silverman · 2009-06-08, 23:23

Quote:

Originally Posted by Primeinator

Very well. Since you are about the most knowledgeable person on this forum, mathematically speaking, what books would you recommend I read to learn about number theory/prime number theory and the books required to build up to those? I have had all three levels of basic Calculus and I have also taken ordinary differential equations. I do not have time for "a lot" of reading, but math is something of a hobby of mine when I have the spare time. Because prime numbers are something I am so interested in, I am willing to take as long as is needed to learn the curriculum. Thanks.

Hardy & Wright. Intro to Number Theory
D. Shanks Solved & Unsolved Problems in No. Theory

will do for starters.

Primeinator · 2009-06-08, 23:45

Thanks!

ATH · 2009-06-08, 23:57

Quote:

Originally Posted by geoff

Robert, I have uploaded a sieve here. See the README for instructions.

Be careful when sieving for small b and large k, if the factor is actually equal to the number, that number is removed as well even if possible prime.

robert44444uk · 2009-06-09, 10:30

Quote:

Originally Posted by R.D. Silverman

Discussion? Any ideas on how to get an effectively computable answer?

For those of you doing these computations, it might be nice to tally
those a less than (say) 1000 for which no prime could be found for b up to
(say) 12 or 13.

This looks quite easy to do, so I might give this a go.

I have sieved b=14 for the first 100,000 values of a for all possible prime factors up to 2^31 (=2^16*2^15+1 in fact) and 31652 candidates remain. Although the sieve instructions mention that you need to do two sieves int(odd)*2^15+1 and then int(odd)*2^16+1, this misses out some important possible factors where int is even. So I had to construct multiple layers of sieve int(odd)*2^(15+x), x integer, to ensure that all int(even) were considered by the sieve.

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Sieve needed for kb1^mb2^n+1	beyastard	Software	58	2023-05-27 19:11
More NFS@Home 16e Lattice Sieve V5 wu's needed	pinhodecarlos	NFS@Home	46	2018-03-12 22:43
Advantage of lattice sieve over line sieve	binu	Factoring	3	2013-04-13 16:32
Help needed	AntonVrba	Math	3	2007-03-06 10:55
Volunteer needed for sieve merging	MooMoo2	Twin Prime Search	9	2007-01-01 21:13

2009-06-08, 20:49	#27
Primeinator "Kyle" Feb 2005 Somewhere near M52.. 2×3³×17 Posts	Well... I decided to post since no one else replied. I followed pretty much most of the math but the reasoning is beyond me as I do not have enough mathematical background. In my spare time I am reading a book on Advanced Calculus. I also want to find some good books on number theory. I do have one question though on your last integral. Does the integral of e^(-1/log x) even have a closed form solution or does it have to be evaluated numerically?

2009-06-08, 23:07	#29
Primeinator "Kyle" Feb 2005 Somewhere near M52.. 2×3³×17 Posts	Very well. Since you are about the most knowledgeable person on this forum, mathematically speaking, what books would you recommend I read to learn about number theory/prime number theory and the books required to build up to those? I have had all three levels of basic Calculus and I have also taken ordinary differential equations. I do not have time for "a lot" of reading, but math is something of a hobby of mine when I have the spare time. Because prime numbers are something I am so interested in, I am willing to take as long as is needed to learn the curriculum. Thanks.

2009-06-08, 23:45	#31
Primeinator "Kyle" Feb 2005 Somewhere near M52.. 2×3³×17 Posts	Thanks!