Sieve needed for a^(2^b)+(a+1)^(2^b)

robert44444uk · 2009-05-19, 12:25

Integers of the form i=[a^(2^b)]+[(a+1)^(2^b)], with a,b integers; provide very prime (or prp-3) series with increasing a, as the possible prime factors of composite i are highly restricted in this series.

As far as I can make out, this series has not been explored before. I would think that an assault on the Lifchitz prp list could be made by a team from this site, but to do so would require a windows executable that quickly eliminates a's that give composite i at a given b.

This should be relatively easy given the quality of sieve programmers here. What is needed is an understanding of the primes that appear as factors. I lack this understanding at present.

Regards

Robert Smith

axn · 2009-05-19, 13:18

So, you're proposing a Generalized Fermat Number with fixed b? AFAIK, Geoff had written a sieve for this, but (I think) it is limited to a^(2^b)+1 form. But pretty sure, he can hack it to fit your need.

R. Gerbicz · 2009-05-19, 13:27

It's easy to prove that if p=(prime)divisor of a^(2^b)+(a+1)^(2^b) then p-1 is divisible by 2^(b+1).

R.D. Silverman · 2009-05-19, 13:44

Quote:

Originally Posted by robert44444uk

Integers of the form i=[a^(2^b)]+[(a+1)^(2^b)], with a,b integers; provide very prime (or prp-3) series with increasing a, as the possible prime factors of composite i are highly restricted in this series.

As far as I can make out, this series has not been explored before. I would think that an assault on the Lifchitz prp list could be made by a team from this site, but to do so would require a windows executable that quickly eliminates a's that give composite i at a given b.

This should be relatively easy given the quality of sieve programmers here. What is needed is an understanding of the primes that appear as factors. I lack this understanding at present.

Regards

Robert Smith

I am not sure what you mean by "very prime...series", but for any
fixed a, such primes will be quite rare.

fivemack · 2009-05-19, 14:46

The primes are rare for fixed A for the same reason that Fermat primes are rare, but the hope is that they will be relatively more common for fixed B than among a set of random numbers of the same size; for instance, n^128 + (n+1)^128 is prime for the twenty values <3000

31 37 65 191 255 287 359 786 836 1178 1229 1503 1601 1609 2093 2103 2254 2307 2471 2934

whilst

$\sum_{i=1}^{3000} \frac{1}{\log(i^{128}+(i+1)^{128})} \approx 3.46$

R.D. Silverman · 2009-05-19, 15:10

Quote:

Originally Posted by fivemack

The primes are rare for fixed A for the same reason that Fermat primes are rare, but the hope is that they will be relatively more common for fixed B than among a set of random numbers of the same size; for instance, n^128 + (n+1)^128 is prime for the twenty values <3000

31 37 65 191 255 287 359 786 836 1178 1229 1503 1601 1609 2093 2103 2254 2307 2471 2934

whilst

$\sum_{i=1}^{3000} \frac{1}{\log(i^{128}+(i+1)^{128}} \approx 3.46$

An interesting question that I am going to look into is:

Does the sum (over all a,b) of the reciprocals of these primes converge?

R.D. Silverman · 2009-05-20, 09:58

Quote:

Originally Posted by R.D. Silverman

An interesting question that I am going to look into is:

Does the sum (over all a,b) of the reciprocals of these primes converge?

Yes, it converges.

robert44444uk · 2009-05-20, 17:23

Quote:

Originally Posted by R.D. Silverman

I am not sure what you mean by "very prime...series", but for any
fixed a, such primes will be quite rare.

I meant variable a, fixed b. It will be a very prime series because there are so few allowable prime factors. However, in some cases, these rare prime factors are factors of 50% of a. A case in question is b=3, then 17 is a factor of 50% of a. These prime factors are of the form [2^(b+1)]+1 so b=3 and 7 do not give very prime series.

If a sieve is constructed using a formula to generate the possible factors of i, this would allow some very deep factoring indeed, lessening the need for prp-3 tests, which is why I think the series interesting.

The prp-3 top 10000 allows us to look first at b=12 and produce prp-3's quickly that qualify for the lower part of the 10000. But higher b should make the top of the list quake in their boots.

robert44444uk · 2009-05-20, 17:28

Quote:

Originally Posted by R. Gerbicz

It's easy to prove that if p=(prime)divisor of a^(2^b)+(a+1)^(2^b) then p-1 is divisible by 2^(b+1).

This looks the key. Shame I did not spot this by observation. So the sieve only has to calculate all the primes in x*2^(b+1)+1, x integer and increasing.

robert44444uk · 2009-05-20, 17:32

Quote:

Originally Posted by fivemack

The primes are rare for fixed A for the same reason that Fermat primes are rare, but the hope is that they will be relatively more common for fixed B than among a set of random numbers of the same size; for instance, n^128 + (n+1)^128 is prime for the twenty values <3000

See notes above relating to b=7 - this is not a very prime series as 2^(7+1)+1 is prime.

henryzz · 2009-05-20, 18:54

this is a link to a list of the possible factors for b=12
it should be easily adjustable to other values of b
if i have got it right then there is an amazingly small number of possible factors

2009-05-19, 12:25	#1
robert44444uk Jun 2003 Suva, Fiji 2×1,021 Posts	Sieve needed for a^(2^b)+(a+1)^(2^b) Integers of the form i=[a^(2^b)]+[(a+1)^(2^b)], with a,b integers; provide very prime (or prp-3) series with increasing a, as the possible prime factors of composite i are highly restricted in this series. As far as I can make out, this series has not been explored before. I would think that an assault on the Lifchitz prp list could be made by a team from this site, but to do so would require a windows executable that quickly eliminates a's that give composite i at a given b. This should be relatively easy given the quality of sieve programmers here. What is needed is an understanding of the primes that appear as factors. I lack this understanding at present. Regards Robert Smith

2009-05-19, 14:46	#5
fivemack (loop (#_fork)) Feb 2006 Cambridge, England 1936₁₆ Posts	The primes are rare for fixed A for the same reason that Fermat primes are rare, but the hope is that they will be relatively more common for fixed B than among a set of random numbers of the same size; for instance, n^128 + (n+1)^128 is prime for the twenty values <3000 31 37 65 191 255 287 359 786 836 1178 1229 1503 1601 1609 2093 2103 2254 2307 2471 2934 whilst $\sum_{i=1}^{3000} \frac{1}{\log(i^{128}+(i+1)^{128})} \approx 3.46$ Last fiddled with by fivemack on 2009-05-19 at 15:46

2009-05-20, 18:54	#11
henryzz Just call me Henry "David" Sep 2007 Liverpool (GMT/BST) 17FD₁₆ Posts	this is a link to a list of the possible factors for b=12 it should be easily adjustable to other values of b if i have got it right then there is an amazingly small number of possible factors Last fiddled with by henryzz on 2009-05-20 at 18:56

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-05-19, 13:18	#2
axn Jun 2003 2³·683 Posts	So, you're proposing a Generalized Fermat Number with fixed b? AFAIK, Geoff had written a sieve for this, but (I think) it is limited to a^(2^b)+1 form. But pretty sure, he can hack it to fit your need.

2009-05-19, 13:27	#3
R. Gerbicz "Robert Gerbicz" Oct 2005 Hungary 3×547 Posts	It's easy to prove that if p=(prime)divisor of a^(2^b)+(a+1)^(2^b) then p-1 is divisible by 2^(b+1).