mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Software

Reply
 
Thread Tools
Old 2009-05-19, 12:25   #1
robert44444uk
 
robert44444uk's Avatar
 
Jun 2003
Oxford, UK

1,933 Posts
Default 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
robert44444uk is offline   Reply With Quote
Old 2009-05-19, 13:18   #2
axn
 
axn's Avatar
 
Jun 2003

115428 Posts
Default

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.
axn is offline   Reply With Quote
Old 2009-05-19, 13:27   #3
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

2×733 Posts
Default

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. Gerbicz is offline   Reply With Quote
Old 2009-05-19, 13:44   #4
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by robert44444uk View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2009-05-19, 14:46   #5
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

24×3×7×19 Posts
Default

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
fivemack is offline   Reply With Quote
Old 2009-05-19, 15:10   #6
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
Originally Posted by fivemack View Post
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 is offline   Reply With Quote
Old 2009-05-20, 09:58   #7
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2009-05-20, 17:23   #8
robert44444uk
 
robert44444uk's Avatar
 
Jun 2003
Oxford, UK

1,933 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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 is offline   Reply With Quote
Old 2009-05-20, 17:28   #9
robert44444uk
 
robert44444uk's Avatar
 
Jun 2003
Oxford, UK

78D16 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
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 is offline   Reply With Quote
Old 2009-05-20, 17:32   #10
robert44444uk
 
robert44444uk's Avatar
 
Jun 2003
Oxford, UK

1,933 Posts
Default

Quote:
Originally Posted by fivemack View Post
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.
robert44444uk is offline   Reply With Quote
Old 2009-05-20, 18:54   #11
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

2·5·587 Posts
Default

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
henryzz is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
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
Sieve needed for k*b1^m*b2^n+1 beyastard Software 55 2009-07-29 12:51
Help needed AntonVrba Math 3 2007-03-06 10:55
Volunteer needed for sieve merging MooooMoo Twin Prime Search 9 2007-01-01 21:13

All times are UTC. The time now is 21:06.

Thu May 13 21:06:59 UTC 2021 up 35 days, 15:47, 0 users, load averages: 3.44, 3.43, 3.28

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.