mersenneforum.org Sieve needed for k*b1^m*b2^n+1
 Register FAQ Search Today's Posts Mark Forums Read

 2009-07-21, 18:00 #1 beyastard   Jul 2009 1710 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 p-1 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^n-1 but this has proved to be not a very common prime.
 2009-07-21, 20:28 #2 beyastard   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.
 2009-07-24, 02:18 #3 geoff     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 fixed-n sieve would. For factors > k1, a fixed-n 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 fixed-n 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 fixed-n sieve for your purpose, but I don't know of any open-source fixed-n sieves to modify. Writing one from scratch will be a bigger job.
2009-07-24, 06:43   #4
beyastard

Jul 2009

17 Posts

Hi geoff,

I'v been studying primes of this form more n-depth 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.
Attached Files
 24.7^m.7^n+1.zip (5.5 KB, 106 views)

2009-07-24, 09:57   #5
R.D. Silverman

Nov 2003

22·5·373 Posts

Quote:
 Originally Posted by beyastard I've been trying to find a type of prime that has not been explored and yet easily factored for p+1 or p-1 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: .
A pointless activity. Think about why I say this...... I will leave it as
an exercize.

I do offer one hint: Try finding a prime that isn't of your form.

2009-07-24, 21:36   #6
beyastard

Jul 2009

17 Posts

Quote:
 Originally Posted by R.D. Silverman A pointless activity. Think about why I say this...... I will leave it as an exercize. I do offer one hint: Try finding a prime that isn't of your form.
The only reason I can think of why you would call this a pointless activity
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?

2009-07-24, 22:33   #7

"Richard B. Woods"
Aug 2002
Wisconsin USA

22×3×641 Posts

Quote:
 Originally Posted by beyastard The only reason I can think of why you would call this a pointless activity is because you believe that one should not look into new areas of prime number research but should do what everyone else already has.
The limits of your imagination in this regard might be stretched if you actually took Dr. Silverman's hint.

Quote:
 So my question to you would be, what form do you suggest?
He already gave you a hint. You even quoted it in your own post! Take it!

Last fiddled with by cheesehead on 2009-07-24 at 22:39

2009-07-24, 22:35   #8

"Richard B. Woods"
Aug 2002
Wisconsin USA

22×3×641 Posts

Quote:
 Originally Posted by beyastard I've tried finding an option to edit my original post but failed
There's a 60-minute time limit on editing one's post, except for designated moderators.

2009-07-25, 17:22   #9
beyastard

Jul 2009

17 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.
Attached Files
 k.7^n1.11^n2+1.zip (19.8 KB, 104 views)

2009-07-25, 17:32   #10
Mini-Geek
Account Deleted

"Tim Sorbera"
Aug 2006
San Antonio, TX USA

17×251 Posts

Edit: First, try to take Silverman's hint. If you try and fail at that, continue:

Quote:
 Originally Posted by beyastard I am still confused about why what I am doing is just a useless waste of time.
If I'm understanding Silverman's hint correctly, all numbers (or at least all primes) are of the form you speak of.
Quote:
 Originally Posted by beyastard Is it being suggested I only look at Proth or Mersenne numbers?
No, just take the hint when someone's saying that your form is useless.

Last fiddled with by Mini-Geek on 2009-07-25 at 18:26

2009-07-25, 18:12   #11

"Richard B. Woods"
Aug 2002
Wisconsin USA

22×3×641 Posts

Quote:
 Originally Posted by beyastard 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.
Dr. Silverman's hint was:

Quote:
 Try finding a prime that isn't of your form.
But you haven't demonstrated that you've made any effort whatsoever to find a prime that isn't of your form.

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 2009-07-25 at 18:43

 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 robert44444uk Software 55 2009-08-12 06:39 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 21:57.

Thu May 6 21:57:13 UTC 2021 up 28 days, 16:38, 0 users, load averages: 2.54, 2.19, 1.92