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

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.

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

[QUOTE=robert44444uk;174161]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[/QUOTE]

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

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

[tex]\sum_{i=1}^{3000} \frac{1}{\log(i^{128}+(i+1)^{128})} \approx 3.46[/tex]

[QUOTE=fivemack;174170]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

[tex]\sum_{i=1}^{3000} \frac{1}{\log(i^{128}+(i+1)^{128}} \approx 3.46[/tex][/QUOTE]


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?

[QUOTE=R.D. Silverman;174173]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?[/QUOTE]


Yes, it converges.

[QUOTE=R.D. Silverman;174166]I am not sure what you mean by "very prime...series", but for any
fixed a, such primes will be quite rare.[/QUOTE]

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.

[QUOTE=R. Gerbicz;174165]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).[/QUOTE]

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.

[QUOTE=fivemack;174170]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

[/QUOTE]

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

[URL="http://factorization.ath.cx/search.php?query=x*2%5E%28b%2B1%29%2B1&v=x&x=1&b=12&EC=1&E=1&Prp=1&P=1&of=H&pp=500&se=Update"][U]this [/U][/URL]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