20090721, 18:00  #1 
Jul 2009
11_{16} Posts 
Sieve needed for k*b1^m*b2^n+1
I've been trying to find a type of prime that has not been explored and yet easily factored for p+1 or p1 and came up with the following:
k*b1^m*b2^n+1 where b1 and b2 are prime bases > 2, bases differing and k is even, for example: 6904*7^987*11^654+1 8020*13^731*31^257+1 6460*257^112*523^388+1 7702*5^2386*7^1257+1 This form appears to be prime rich but I have only done > 2k digits so far as trial dividing each and every k is so time consuming. Is there anyone who can modify an existing program that can sieve then k values of this form? Any help will be appreciated. NOTE: I've also tried k*b1^m*b2^n1 but this has proved to be not a very common prime. 
20090721, 20:28  #2 
Jul 2009
17 Posts 
I've tried finding an option to edit my original post but failed so this is to
correct my typo's. Thus far, I've only trial divided values to < 2k digits. And I'd like to sieve the k values. It also appears that composites of this form have at least one relatively small factor so sieving will be fairly fast at removing k's. If I understood what is involved in programming sieve's I'd take this task upon myself but I am still new in primes research and still learning. 
20090724, 02:18  #3 
Mar 2003
New Zealand
13×89 Posts 
Sieving k * b1^n1 * b2^n2 * ... * bm^nm + 1 (Assuming all bi and ni are fixed, and that only k varies) should not take more than m times longer than a normal fixedn sieve would.
For factors > k1, a fixedn sieve for k*b^n+1 over a range k0 <= k <= k1 should not take much longer than twice the time to trial factor a single k. (A fixedn sieve cannot make use of the Legendre symbol for k which can double the speed of trial factoring). It would probably not be too difficult to modify an ordinary fixedn sieve for your purpose, but I don't know of any opensource fixedn sieves to modify. Writing one from scratch will be a bigger job. 
20090724, 06:43  #4 
Jul 2009
17 Posts 
Hi geoff,
I'v been studying primes of this form more ndepth and found that there are some k's that give a higher density of primes when a single n varies. I believe it would be more practical to sieve a single n value instead of k. Of course, I've only tried up to k=24 as I noticed this value gives quite a few primes. To get a visual of the distribution of primes I threw together a simple program to create a bitmap from the exponents used. Attached is a bitmap for 24*7^n1*11^n2+1 for all n <= 1000. I may do this for many more k values to see what the prime distribution is for various k's and try to extrapolate what the best value of k is to find a large (150k+ digit) prime by trial dividing across n instad of k. To date, the largest prime I've found of this form (using bases 7 an 11 in the hopes I get lucky) is 9926*7^11387*11^14771+1 (25010 digits). Though I may be speaking prematurely, I feel that this is a good form to analyze more indepth for discovering large primes a it appears they are fairly common compared to other forms. 
20090724, 09:57  #5  
"Bob Silverman"
Nov 2003
North of Boston
1110101010100_{2} Posts 
Quote:
an exercize. I do offer one hint: Try finding a prime that isn't of your form. 

20090724, 21:36  #6  
Jul 2009
17 Posts 
Quote:
is because you believe that one should not look into new areas of prime number research but should do what everyone else already has. I don't see why exploring new areas would be pointless, isn't that how some discoveries are made? I find it pointless to use my idle cpu cycles on something everyone else is doing or has already done. So my question to you would be, what form do you suggest? Or should I spend the next few years and use all my cpu cycles to factor small composites? 

20090724, 22:33  #7  
"Richard B. Woods"
Aug 2002
Wisconsin USA
1E0C_{16} Posts 
Quote:
Quote:
Last fiddled with by cheesehead on 20090724 at 22:39 

20090724, 22:35  #8 
"Richard B. Woods"
Aug 2002
Wisconsin USA
2^{2}×3×641 Posts 

20090725, 17:22  #9 
Jul 2009
21_{8} Posts 
One thing I'd like to say is I am not a mathematician but I research prime
numbers because I find them facinating. Also, the most I would like to get out of this "hobby" is I hope one day I can contribute something of use. I am clueless about these vague answers that have been posted as I don't look through a "mathematician's eyes." I am still confused about why what I am doing is just a useless waste of time. Maybe because this form has already been investigated? Is it being suggested I only look at Proth or Mersenne numbers? I hope someone will be blunt as just let me know what it is I am wasting my time with so I can start something more constructive. At any rate, I guess I wasted my time with the attached visual representations of primes of this form with k<=20 (minus k values that share the same base as a factor) and n1=n2<=512, since I did state I will do it. 
20090725, 17:32  #10  
Account Deleted
"Tim Sorbera"
Aug 2006
San Antonio, TX USA
11·389 Posts 
Edit: First, try to take Silverman's hint. If you try and fail at that, continue:
Quote:
No, just take the hint when someone's saying that your form is useless. Last fiddled with by TimSorbet on 20090725 at 18:26 

20090725, 18:12  #11  
"Richard B. Woods"
Aug 2002
Wisconsin USA
2^{2}·3·641 Posts 
Quote:
Quote:
That hint was very simple: Try to find a prime that is not of your form. It came from a leading mathematician! Did you assign any value at all to that hint, or did you just ignore it? Did it ever occur to you that taking that hint might allow you to learn something valuable? Did you take that hint? It doesn't seem so; you don't say anything about trying to find a prime that is not of your form. What shall we conclude from that? That you have no interest in any hint we give you? That you need every single detail completely spelled out? That you will not lift a finger to do even so simple a task as trying to find a prime that is not of your form? How about doing just one simple thing: find a prime that is not of your form, then tell us what it is. If you put a reasonable amount of effort into trying to find such a prime, but cannot, then at least describe what efforts you made toward that goal, so as to show us that you're willing to use a simple hint that you were given. Otherwise, why should we give you any more help than we already have given you? If you throw away Dr. Silverman's valuable hint, why should we waste any more hints on you? Last fiddled with by cheesehead on 20090725 at 18:43 

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  20180312 22:43 
Advantage of lattice sieve over line sieve  binu  Factoring  3  20130413 16:32 
Sieve needed for a^(2^b)+(a+1)^(2^b)  robert44444uk  Software  55  20090812 06:39 
Help needed  AntonVrba  Math  3  20070306 10:55 
Volunteer needed for sieve merging  MooooMoo  Twin Prime Search  9  20070101 21:13 