mersenneforum.org  

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

Reply
 
Thread Tools
Old 2009-07-21, 18:00   #1
beyastard
 
Jul 2009

17 Posts
Default 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.
beyastard is offline   Reply With Quote
Old 2009-07-21, 20:28   #2
beyastard
 
Jul 2009

100012 Posts
Default

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.
beyastard is offline   Reply With Quote
Old 2009-07-24, 02:18   #3
geoff
 
geoff's Avatar
 
Mar 2003
New Zealand

13×89 Posts
Default

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.
geoff is offline   Reply With Quote
Old 2009-07-24, 06:43   #4
beyastard
 
Jul 2009

17 Posts
Default

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
File Type: zip 24.7^m.7^n+1.zip (5.5 KB, 89 views)
beyastard is offline   Reply With Quote
Old 2009-07-24, 09:57   #5
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
Originally Posted by beyastard View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2009-07-24, 21:36   #6
beyastard
 
Jul 2009

1116 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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?
beyastard is offline   Reply With Quote
Old 2009-07-24, 22:33   #7
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

1E0C16 Posts
Default

Quote:
Originally Posted by beyastard View Post
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
cheesehead is offline   Reply With Quote
Old 2009-07-24, 22:35   #8
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

22·3·641 Posts
Default

Quote:
Originally Posted by beyastard View Post
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.
cheesehead is offline   Reply With Quote
Old 2009-07-25, 17:22   #9
beyastard
 
Jul 2009

17 Posts
Default

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
File Type: zip k.7^n1.11^n2+1.zip (19.8 KB, 86 views)
beyastard is offline   Reply With Quote
Old 2009-07-25, 17:32   #10
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

10000101010112 Posts
Default

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

Quote:
Originally Posted by beyastard View Post
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 View Post
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
Mini-Geek is offline   Reply With Quote
Old 2009-07-25, 18:12   #11
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

22×3×641 Posts
Default

Quote:
Originally Posted by beyastard View Post
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
cheesehead 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 a^(2^b)+(a+1)^(2^b) robert44444uk Software 55 2009-08-12 06:39
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:56.

Sun Jan 17 21:56:32 UTC 2021 up 45 days, 18:07, 0 users, load averages: 1.99, 1.81, 1.83

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.