mersenneforum.org Sieve needed for a^(2^b)+(a+1)^(2^b)
 Register FAQ Search Today's Posts Mark Forums Read

 2009-05-19, 12:25 #1 robert44444uk     Jun 2003 Suva, Fiji 23·3·5·17 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, 13:18 #2 axn     Jun 2003 34×67 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 7×229 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).
2009-05-19, 13:44   #4
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

749610 Posts

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.

 2009-05-19, 14:46 #5 fivemack (loop (#_fork))     Feb 2006 Cambridge, England 645410 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-19, 15:10   #6
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

23×937 Posts

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?

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

"Bob Silverman"
Nov 2003
North of Boston

23×937 Posts

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.

2009-05-20, 17:23   #8
robert44444uk

Jun 2003
Suva, Fiji

23·3·5·17 Posts

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.

2009-05-20, 17:28   #9
robert44444uk

Jun 2003
Suva, Fiji

23·3·5·17 Posts

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.

2009-05-20, 17:32   #10
robert44444uk

Jun 2003
Suva, Fiji

23×3×5×17 Posts

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.

 2009-05-20, 18:54 #11 henryzz Just call me Henry     "David" Sep 2007 Liverpool (GMT/BST) 135778 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 pinhodecarlos NFS@Home 46 2018-03-12 22:43 binu Factoring 3 2013-04-13 16:32 beyastard Software 55 2009-07-29 12:51 AntonVrba Math 3 2007-03-06 10:55 MooooMoo Twin Prime Search 9 2007-01-01 21:13

All times are UTC. The time now is 05:05.

Tue Dec 6 05:05:46 UTC 2022 up 110 days, 2:34, 0 users, load averages: 1.78, 1.53, 1.19