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.

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.

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.

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.

[QUOTE=beyastard;182117]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:
.[/QUOTE]

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.

[quote=R.D. Silverman;182506]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.[/quote]

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?

[quote=beyastard;182589]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.[/quote]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?[/quote]He already gave you a hint. You even quoted it in your own post! Take it!

[quote=beyastard;182139]I've tried finding an option to edit my original post but failed[/quote]There's a 60-minute time limit on editing one's post, except for designated moderators.

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.

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

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

[quote=beyastard;182731]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.[/quote]Dr. Silverman's hint was:

[quote]Try finding a prime that isn't of your form.[/quote][U]But you haven't demonstrated that you've made any effort whatsoever to find a prime that isn't of your form.

[/U]That hint was very simple: Try to find a prime that is [B]not[/B] 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, [I]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[/I].

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?

[quote=Mini-Geek;182733]If I'm understanding Silverman's hint correctly, [/quote]Mini-Geek,

It would have been more instructive and useful for beyastard if you had encouraged beyastard to take Dr. Silverman's hint and do some work on his/her own, rather than just telling beyastard what you think the answer is.

You know -- the old "give a fish" / "teach to fish" distinction.

[quote=Mini-Geek;182733]If you try and fail at that, continue:
[/quote]No, you're still giving an answer ("giving a fish") instead of showing how the effort of taking Silverman's hint is instructive ("how to fish"). The education will be in the effort of finding the prime, not in being told an answer.

beyastard has not yet shown us any evidence (e.g., range of integers searched, unsuccessfully, to find a prime [B]not[/B] of that form) of having tried to use the hint. Once beyastard has done that, we can proceed to teaching what that failure means. OTOH, if beyastard succeeds ...

[QUOTE=beyastard;182589]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[/QUOTE]

I will try to be gentle.

You admit that you are not a mathematician. Therefore you can not
[b]possibly[/b] know what is new and what isn't new. Your claim that your
'research' is new therefore comes across as arrogance.

It is not 'new'. In fact, it is so elementary that it might be presented
as a simple homework problem in a first year number theory course.

I gave the perfect hint as to why what you are doing is pointless.
Follow this hint. Present a prime to this group that is NOT of your
form. Then ask yourself: "what is special about the prime that I just
presented".


May I suggest that you pick up and read any elementary number theory
book. Do the exercizes.

Your attempt at 'research' falls in the same category as someone without
a science education doing research into a cure for cancer.

[quote=R.D. Silverman;182767]Your attempt at 'research' falls in the same category as someone without
a science education doing research into a cure for cancer.[/quote]

It appears that a thread asking for help with a sieve so that searching for
large primes more efficiently has degraded into, basically, a thread of
belittling. Indirectly, it appears I am being told that as someone who does
not hold a Ph.D. in mathematics has no right to search for large primes.
If this is the case then GIMPS, et al, should not be open to the public but
be a private website. I will immediately quit GIMPS and delete Prime95
from all my computers as I am not "authorized" to assist in prime searches.

[QUOTE=beyastard;182872]It appears that a thread asking for help with a sieve so that searching for
large primes more efficiently has degraded into, basically, a thread of
belittling. Indirectly, it appears I am being told that as someone who does
not hold a Ph.D. in mathematics has no right to search for large primes.
If this is the case then GIMPS, et al, should not be open to the public but
be a private website. I will immediately quit GIMPS and delete Prime95
from all my computers as I am not "authorized" to assist in prime searches.[/QUOTE]

I never said that you had no [b]RIGHT[/b] to conduct such a search.
I said that you had no [b]QUALIFICATIONS[/b].

One does not need a math PhD. One [b]does[/b] need a knowledge
of basic number theory.

Finally, using computers to search for large primes, is not "research",
as you claimed to be doing. Your claim of "new research" was just
arrogance based upon ignorance. When I tried to lead you into actually
studying the mathematics of what you were doing, you chose not to
respond.

Don't let the door hit you on the way out.

If you read my first post you will see it's nothing more than a request for
a sieve of a specific form as there are none that I can find. I see nothing
in my request that can even be closely considered showing arrogance.

Also, one does not have to have "qualifications" to use a piece of software
to sieve, test for prp then verify prp's as prime. One only needs to know how
to use the software.

Is it a requirement to have a basic understanding of computer hardware or software
to boot up a computer? Do you need to be "qualified" in networking to start
a browser and surf the internet? You merely need to know how to use the
software.

Again, the only thing I was searching for was assistance on a sieve of the
form I posted. If you read through my posts you will see I used the word "new"
in the context of a form that there is no sieves available for. Neither newpgen
nor multisieve handles these forms. I also stated that it appears that
there are many primes of this form. My first post was similar to that made
by robert44444uk. I've read the entire thread and seen nowhere mentioned
to him that searching for primes of the form a^(2^b)+(a+1)^(2^b) is
pointless. If a sieve exists for the form k*b1^n1*b2^n2+1 then it would
have been so much easier pointing me into the right direction. If there is
none my question was "can an existing one be modified to handle this
form?"

[QUOTE=beyastard;182885]If you read my first post you will see it's nothing more than a request for
a sieve of a specific form as there are none that I can find. I see nothing
in my request that can even be closely considered showing arrogance.[/QUOTE]

Have you ever considered that maybe there are no sieves of that form for a reason? And maybe that we've been trying to show you what that reason is for days now? And that maybe it's a little bit arrogant to ignore the advice of established mathematicians when you admit you have no experience in the area?

I am not a mathematician either, so perhaps someone can explain to me why searching for primes of the form k*3^3*5^2+1 say, is pointless but searching for primes of the form k*2^333333+1 is not? (Well, I know that k*2^333333+1 might be a Fermat Divisor, but apart from that?)

Since there are already sieves for k*2^n+1 (n fixed), albeit without source code, and lots of people using them, why would a sieve for k*b1^n*b2^m+1 (b1,b2,m,n fixed) be useless?

It can't be because all primes are of the form k * b1^n * b2^m + 1, because all primes are of the form k*2^n+1 too, and that doesn't make an ordinary fixed-n sieve pointless.

[quote=geoff;182896]I am not a mathematician either, so perhaps someone can explain to me why searching for primes of the form k*3^3*5^2+1 say, is pointless but searching for primes of the form k*2^333333+1 is not? (Well, I know that k*2^333333+1 might be a Fermat Divisor, but apart from that?)

Since there are already sieves for k*2^n+1 (n fixed), albeit without source code, and lots of people using them, why would a sieve for k*b1^n*b2^m+1 (b1,b2,m,n fixed) be useless?[/quote]
Remember Silverman's hint: find a prime that is not of this form. I'm going to try to find it myself, and if the OP posts what efforts he has made, I'll post my efforts as well.
[quote=geoff;182896] It can't be because all primes are of the form k * b1^n * b2^m + 1, because all primes are of the form k*2^n+1 too, and that doesn't make an ordinary fixed-n sieve pointless.[/quote]
The definition of Proth numbers requires that 2^n be greater than k, so not all numbers are of the form k*2^n+1.

Edit: To the OP: can m and/or n equal 0? If so, the problem should be quite easy to spot. Whether they may or may not equal 0, this should have been specified clearly. Maybe that's all that RDS is complaining about, because at a quick glance I don't see anything wrong with it if m,n>0...

[QUOTE=Mini-Geek;182898]Remember Silverman's hint: find a prime that is not of this form. I'm going to try to find it myself, and if the OP posts what efforts he has made, I'll post my efforts as well.

The definition of Proth numbers requires that 2^n be greater than k, so not all numbers are of the form k*2^n+1.[/QUOTE]

23 is a prime not of the form k*3^3*5^2+1. Why shouldn't someone search for those primes which are of this form? The sieve that was requested would allow them to do that efficiently.

[QUOTE=R.D. Silverman;182767]I will try to be gentle.[/QUOTE]
RDS being gentle... That should really be appreciated. :wink:

[quote=geoff;182901]23 is a prime not of the form k*3^3*5^2+1.[/quote]But it is of the form

k*b1^m*b2^n+1 where b1 and b2 are prime bases > 2, bases differing and k is even

k = 2

b1 = 11

m = 1

b2 = any odd prime but 11

n = 0

I do understand EVERY prime with no exception can be represented as
k*b1^n1*b2^n2+1 if b1 = n1 = b2 = n2 = 1 and k = p-1/2. So an exercise
to find a prime NOT of this form is simply futile. If b1 and b2 are prime
bases > 2 and differing and n1 and n2 are > 0, k even, then there are
primes NOT of this form and the smallest you can represent would be
2*3^1*5^1+1 = 31, therefore, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 are NOT
of this form.

But from what I see, a sieve of this form can and will allow people to find
primes currently unknown. Also, I believe sieving across n1 or n2 will be a
more efficient use of time instead of sieving across k in a search for a
large prime. I think both b1 and b2 should be prime bases and k should be
chosen so it does not share a factor with the bases and is even. Having
prime bases allows for easy factoring of p-1 so a BLS can be done.

As I have stated before, the largest prime I've found of this form is
9926*7^11387*11^14771+1 (25010 digits) but I have, since then,
realized 9926 has a factor of 7 so the correct prime would be
1418*7^11388*11^14771+1. Finding this prime was no easy task as I
cannot sieve this form and so have to use an ABC2 file with pfgw and prp
each and every candidate.

Again, I will state my case and say I believe a sieve of this form will allow
many more large primes to be discovered. As for those that say I haven't
been doing my "homework," since Dr Silverman's post I have download
vaious PDF's including:

A Computational Introduction to Number Theory and Algebra
by Victor Shoup
The ABC's of Number Theory
by Prof Noam D Elkies
Elementary Number Theory, A Computational Approach
by William Stein
Elementary Number Theory in Nine Chapters
by James J Tattersall
and even
Fast Generation of Random, Strong RSA Primes by R D Silverman

[QUOTE=geoff;182896]I am not a mathematician either, so perhaps someone can explain to me why searching for primes of the form k*3^3*5^2+1 say, is pointless but searching for primes of the form k*2^333333+1 is not? [/QUOTE]

Alright! I give up!

EVERY prime can be put into the form k * p1^n p2^m + 1
where k is even and p1, p2 are primes.

The O.P. placed no restriction on n or m.!!!!!!!

Suppose now we restrict to n,m > 0. Now, almost all primes
have a representation. I say 'almost all' in the measure-theoretic sense.
The exceptions form a set of density 0. Which ones can't? I leave it
as an exercise. Hint: "Think about the Germain primes".

Suppose now we restrict to n,m > 1. The set that has a representation
is no longer 'almost all primes', but it is a set of positive density. That
density is easy to compute. (Hint: "what fraction of even integers are
squarefee; now apply to having two distinct square factors).

Furthermore, a "sieve" in the sense originally requested is computationally
impossible. We want p-1 = k * p1^n, p2^m. The RHS has 5 (FIVE!)
free variables. Over which one shall we sieve? 5-Dimensional sieves
are somewhat difficult from a computational point of view..... :smile:

Finally, note that for ANY pair (p1, p2), there are infinitely many primes
of the requested form. Their density is also positive. (Think about the
PNT for AP).

In short, there are so many primes of this form that looking for them is
EASY. There is no 'research' here. The density of these primes is
well understood.

[QUOTE=geoff;182901]23 is a prime not of the form k*3^3*5^2+1. Why shouldn't someone search for those primes which are of this form? The sieve that was requested would allow them to do that efficiently.[/QUOTE]

23 - 1 = 2 * 11^1 * p^0 where p is any prime. 23 has the
requested form.

See my followup.

[QUOTE=beyastard;182885]If you read my first post you will see it's nothing more than a request for
a sieve of a specific form as there are none that I can find. I see nothing
in my request that can even be closely considered showing arrogance.

Also, one does not have to have "qualifications" to use a piece of software
to sieve, test for prp then verify prp's as prime. One only needs to know how
to use the software.
[/QUOTE]

YOU claimed to be doing 'new research'. Blindly using software written
by others to implement algorithms that you do not understand is not
'research'. Blindly computing primes is not 'research'. Nor is it doing
mathematics.


And you did [b]NOT[/b] request a 'sieve of a specific form'. You
said nothing at all about the 'form' of the sieve you wanted.

Damn it!! There are 5 variables involved! Over which variable(s) did
you want to sieve? Fix any 4 of them and the problem becomes a
simple sieve; trivial to implement.

A good learning exercize would be for you to write such a sieve yourself
instead of asking that it be handed to you. Learn the difficulties involved.
Learn the elementary number theory involved. Learn why such a general
sieve (in the sense you ask for) is computationally impossible.

OTOH, if you are just doing this for fun, that I can understand. But
it is not new, it is not research, and doesn't even add enough knowledge
to mathematics to make a decent undergraduate paper.

[quote=beyastard;182927]Finding this prime was no easy task as I
cannot sieve this form and so have to use an ABC2 file with pfgw and prp
each and every candidate.[/quote]
Run -f file.txt and PFGW will attempt to trial factor every number (to an automated depth) before PRPing it. Read pfgwdoc.txt to learn about the other options and how to tweak how much TF it tries.

[quote=beyastard;182927]I do understand EVERY prime with no exception can be represented as
k*b1^n1*b2^n2+1 if b1 = n1 = b2 = n2 = 1 and k = p-1/2. So an exercise to find a prime NOT of this form is simply futile.[/quote]That's why Silverman was saying that your search, [I]as defined in the OP[/I], was pointless. You'd simply be searching for any prime whatsoever.

[I]That's the lesson[/I] to be learned from trying to find a prime that is NOT of the form [I]defined in the OP[/I]. [U]If you'd simply done that right away as requested, we'd have saved a lot of time.[/U]

[quote]If b1 and b2 are prime bases > 2 and differing and n1 and n2 are > 0, k even, then[/quote]... you have added a restriction (n1 and n2 are > 0) that was missing from the OP (where m and n were used in place of n1 and n2).

There's a difference between requiring (m, n > 0) and not requiring that.

[quote]But from what I see, a sieve of this form can and will allow people to find primes currently unknown.[/quote]Perhaps so ... because [I]now[/I] you're talking about a different, more-restrictive form than you were originally talking about -- at least in the eyes of your readers.

Maybe you [I]intended[/I] that the restriction (m, n > 0) be in place all along. Your examples in the OP all met that requirement. [I]But you hadn't actually stated that restriction[/I], and that's why your original proposal met with the reception that it did. We can't read your mind -- just the actual text.

[quote]As for those that say I haven't been doing my "homework," since Dr Silverman's post I have download vaious PDF's including:

< snip >[/quote][I]But your homework assignment wasn't to download PDFs[/I]; it was to try to find a prime that was not of the form you stated in your OP.

This was the first post where you've shown us that you made any attempt to do the [I]actual[/I] "homework assignment" by Dr. Silverman. You hadn't shown us that in any post before #24.

[QUOTE=cheesehead;182960]That's why Silverman was saying that your search, [I]as defined in the OP[/I], was pointless. You'd simply be searching for any prime whatsoever.

[/QUOTE]

The next assignment is to show that the restriction m,n > 0, is also
not very restrictive. I gave a hint.

I am still curious as to why the OP thinks that finding new primes
by blindly using someone else's software is 'research'.

As you stated, "5-Dimensional sieves are somewhat difficult from
a computational point of view..." it can be reduced to 3 values.

Let FicSieve be the name of the fictional fixed-k sieve.

Command line can be something like:

>FictSieve --k=6 --b1=7 --n1=150000 --b2=11 --n2=2-150000 --pmin=2 --pmax=10000000 [etc]

The program checks to see if k shares any factors with b1 or b2,
if it does, it terminates with error message such as
"k shares base with b1/b2". If it shares no factors then it uses
k*b1^n1 as k1 so that it becomes k1*b2^n2+1 and sieves across
the n2 variable, all others being fixed. Basically, a k*b^n+1
sieve with a k value > 100k digits and having a large number
of small factors (above example being 2*3*7^150000).

An alternative (and probably better method) would be where you
can input a term for k on the commandline so only 3 terms will
be needed, for example:

>FictSieve --k=2*3*7^150000 --b=11 --n=2-150000 --pmin=2 --pmax=10000000 [etc]

As I am not familiar with sieves and have no well-commented source
of a few different kinds to study and learn about, I am not sure
if such a task is feasible. If it is, I would probably say that
because the above combining of terms into k1 creates such a large
value, a library such as GMP may be required. Also, if I am able to
learn the "mechanics" of sieves, I'd tackle this problem myself.

And yes, Doc, I do see flaws in this form but still trying to work
through them as I see there is potential in forms of this kind, i.e.,
k*b1^n1*b2^n2...bi^ni+1, as p-1 is easily factored into small primes
(since practically all the factors are known beforehand). An easily
factored number really helps in a BLS test for primality. The biggest
hurdle is reducing all the k*b(i-1)^n(i-1) into a single value to
sieve for k1*bi^ni+1 as k1 will be such a large number.

As you have stated, "In short, there are so many primes of this form
that looking for them is EASY." So, in a nutshell, sieving for primes
of this form will help increase the number of large primes discovered.
The biggest hurdle to overcome will be finding an efficient method of
doing so.

[QUOTE=beyastard;182968]So, in a nutshell, sieving for primes
of this form will help increase the number of large primes discovered.

.[/QUOTE]

So? Other than being a stamp collection, please explain the value
of increasing the number of known large primes. What will you do with these
primes? What mathematics will be learned? What problems will they help
solve? What algorithms will be improved by searching for them?

[QUOTE=beyastard;182968]As I am not familiar with sieves and have no well-commented source
of a few different kinds to study and learn about,




[/QUOTE]

Under the assumption that you already know how to write code,
studying existing code is the WORST way to learn about sieves.

Start by learning the basic number theory behind them.

Then implement one yourself. And one does NOT need an MP
library to sieve numbers of the form you suggest as long as k,
and the two primes are themselves only single precision.
And even if they are multi precision, all one needs to sieve through
primes less than 2^31 (on a 32-bit machine) is a simple routine
that returns the remainder when an MP number is divided by a single
precision number. Get a copy of Knuth Vol II. Read the section on
multi-precision arithmetic. He also discusses how to perform a sieve.

[quote=R.D. Silverman;182967]I am still curious as to why the OP thinks that finding new primes by blindly using someone else's software is 'research'.[/quote]

My words were "... new areas of prime number research.." when I meant to
say "... new areas of prime number searches...," simply a mistake of
words on my part.

Also I stated, "... but I research prime numbers..." which I do when I have
time but have found nothing that is already known, so nothing to post
about that.

As for "blindly using someone else's software," lead me to sources I can study
to learn to write my own sieve's and I'll do it all myself. Further, I've never
called prime searching as research.

As for cheeseheads comment, "[I]But your homework assignment wasn't to[/I]
[I]download PDFs[/I]; it was to try to find a prime that was not of the form you
stated in your OP." Doc said, "May I suggest that you pick up and read
any elementary number theory book. Do the exercizes." And so I followed
his suggestion and did so and am reading them as time permits.

And finally, for the remainder of the "assignments," I am currently working
on them, again, as time permits.

[quote=R.D. Silverman;182969]So? Other than being a stamp collection, please explain the value
of increasing the number of known large primes. What will you do with these
primes? What mathematics will be learned? What problems will they help
solve? What algorithms will be improved by searching for them?[/quote]

Then projects such as GIMPS, et al, are a waste of time and many people
are doing useless searches for such primes.

[quote=Mini-Geek;182946]Run -f file.txt and PFGW will attempt to trial factor every number (to an automated depth) before PRPing it. Read pfgwdoc.txt to learn about the other options and how to tweak how much TF it tries.[/quote]

Yes, that is what I have been doing, thought it is still quite slow.

[QUOTE=beyastard;182973]My words were "... new areas of prime number research.." when I meant to
say "... new areas of prime number searches...," simply a mistake of
words on my part.

[/QUOTE]

Bull.

Congratulations. You just made my "willfully ignorant" ignore list.

[QUOTE=beyastard;182975]Then projects such as GIMPS, et al, are a waste of time and many people
are doing useless searches for such primes.[/QUOTE]

On the contrary. GIMPS has spurred much research into algorithms
and has led to the irrational-base DWT that is now used. The
effort to develop code also taught us many things.

The primes themselves are not very useful at all. Finding them is certainly
FUN, but finding a new one or even several new ones will not advance
our understanding of the underlying mathematics. OTOH, the continued
search for better algorithms has great value.

You on the other hand have made it clear that you are not interested in
the algorithms. It is also clear that you lack the background to make
a contribution towards improved algorithms. You simply want someone else's
code handed to you.

<plonk>

[quote=beyastard;182975]Then projects such as GIMPS, et al, are a waste of time and many people
are doing useless searches for such primes.[/quote]

GIMPS are searching for a prime of the form 2^p-1. There are very few of these, and they can be tested much higher than other numbers using the Lucas-Lehmer test. This means that most of the time the largest known prime number is of the form 2^p-1. Same with the other projects. They are not searching for virtually "random" primes, since this would be [I]very[/I] easy and [I]very[/I] boring. There would be no thrill, as you would find so many primes.

P.S. Dr Silverman's ignore list is very long. I'm one of the hundreds on it. If you join this forum and ask lots of questions, you will end up on it. He is on my ignore list for insulting me.

[quote=R.D. Silverman;182988]On the contrary. GIMPS has spurred much research into algorithms
and has led to the irrational-base DWT that is now used. The
effort to develop code also taught us many things.

The primes themselves are not very useful at all. Finding them is certainly
FUN, but finding a new one or even several new ones will not advance
our understanding of the underlying mathematics. OTOH, the continued
search for better algorithms has great value.

You on the other hand have made it clear that you are not interested in
the algorithms. It is also clear that you lack the background to make
a contribution towards improved algorithms. You simply want someone else's
code handed to you.

<plonk>[/quote]

You're arrogance knows no bounds, does it? I have taken your suggestions
and have been studying as well as working on your "assignments" at every
opportunity. You should try not to be so opinionated and make assumptions
that contradict other peoples statements. Did I not say I'd do it myself once
I know the basic algorithms involved? Do you recall in one of my posts I
stated "also, if I am able to learn the 'mechanics' of sieves, I'd tackle this
problem myself" and did I not say that I took your suggestions and am
studying elementary number theory? Already, I am in the planning stages
of writing this sieve myself.

Also, I have found a copy of Knuth vol II as you suggested (as well as vols
I and III). I really don't know how much more clear I can make it to you
when you won't even listen to what I'm saying. Maybe I should just be
blunt and say it in simple language so that you may understand.

[I][B]I am studying elementary number theory and am writing my own sieve[/B][/I]
[I][B]for this form.[/B][/I]

I hope that statement is clear enough for you to understand. It is not my
intention to be rude, I am simply trying to get this across to you. I am,
also, trying to get it across to you that I have been taking your suggestions
and working out solutions for myself. If you wish to ignore me from this point
on, well, I'd like to thank you for your input as it has led me to a better
understanding and helped me to initiate more in-depth study into
number theory.

[quote=beyastard;182973]As for cheeseheads comment, "[I]But your homework assignment wasn't to [/I][I]download PDFs[/I]; it was to try to find a prime that was not of the form you stated in your OP." Doc said, "May I suggest that you pick up and read any elementary number theory book. Do the exercizes." And so I followed his suggestion and did so and am reading them as time permits.[/quote]Yes, I overlooked the need to specify [i]first[/i] assignment. :-)

[quote=beyastard;182995]You're arrogance knows no bounds, does it?

< snip >

I'd like to thank you for your input as it has led me to a better understanding and helped me to initiate more in-depth study into number theory.[/quote]Having supported Dr. Silverman's mathematical hint, let me balance that by saying that Dr. Silverman has nowhere near the ability to educate novices appropriately in a public forum as he does to do the math itself.

It's not arrogance (he [I]can[/I] walk the walk); it's inability to modulate his message to communicate with students much below his level, in my opinion. He's actually mellowed a bit recently (though I don't necessarily expect you to believe that without having scanned the archives).

[quote=cheesehead;183029]Having supported Dr. Silverman's mathematical hint, let me balance that by saying that Dr. Silverman has nowhere near the ability to educate novices appropriately in a public forum as he does to do the math itself.

It's not arrogance (he [I]can[/I] walk the walk); it's inability to modulate his message to communicate with students much below his level, in my opinion. He's actually mellowed a bit recently (though I don't necessarily expect you to believe that without having scanned the archives).[/quote]

Thanks for your input cheesehead. I hold absolutely no animosity toward
the Doc but continue to respect him thought I, at times, get frustrated
trying to get my point acrossed. Also, to validate my last post I am showing
how far I have got in a siev of this form. It appears more simple than I have
originally anticipated. The basic algorithm is as follows in pseudocode:

[code]// sieve algorithm for k*b1^n1*b2^n2+1
// where k, b1, n1, b2 are fixed and n2 is variable
//
// ...simplified PSEUDOCODE...
//
// get input from user/file for terms
BEGIN
GetInput();
if(k%b1 OR k%b2)
print("Error: k shares factor with b1 or b2")
exit
// initialize bitmap
// for this example, we will simplify it by using a bytemap
for(i=0; i<maxn; i++)
bitmap[i] = 0 // clear all bits
// initialize values
k1 = k*b1^n1
p = minp // set p to minimum p
n = minn // set n to minimum n we are sieving
// begin sieve
do
if(k1*b2^n2+1 % p)
setbit(bitmap[i]) // composite
// remove all remaining candidates that share factor
while(i <= maxn)
i += p-1
setbit(bitmap[i])
NextPrime(p)
i = 0
while(p != maxp OR UserInterrupt)
END
[/code]

As this is a rough first draft at an algorithm for this sieve there may be
parts I've left out. As I continue to develop this code I will be sure to
keep anyone who's interested posted on my progress.

And again, I'd like to give my thanks to the Doc :smile::tu:

I noticed an error in my pseudocode.
If k = 2 then p-1 becomes (p-1)/2

[code]// begin sieve
do
if(k1*b2^n2+1 % p)
setbit(bitmap[i]) // composite
// remove all remaining candidates that share factor
while(i <= maxn)
if(k == 2)
i += (p-1)/2
else
i += p-1
setbit(bitmap[i])
NextPrime(p)
i = 0
while(p != maxp OR UserInterrupt)[/code]

Instead of checking whether or not the bit is set or not, I just set it to
speed it up by getting rid of cmp and jxx instructions as all are composite.

[QUOTE=cheesehead;183029]
It's not arrogance (he [I]can[/I] walk the walk); it's inability to modulate his message to communicate with students much below his level, in my opinion. He's actually mellowed a bit recently (though I don't necessarily expect you to believe that without having scanned the archives).[/QUOTE]

It isn't the [b]level[/b] of the student; it is his or her [b]attitude[/b].

If, instead of saying "I am interested in primes of the form
p = m p1^n p2^m+1; can someone TEACH me to implement a sieve to
eliminate many of the composite candidates"

rather than

"I am doing new research on primes of the form p = ...., can someone
GIVE me the software I need"

I would have responded with a great deal of help.

Can't you see the difference? The latter boldly makes a ridiculous
assertion and is combined with an apparent DISINTEREST in learning.
(he wanted it handed to him)

Indeed; my very first response was designed to elicit some thinking
about the mathematics of the problem. IT WAS IGNORED.

I later wrote up what happens when the exponents are first restricted
to > 0, then > 1. The mathematics of what I wrote was ALSO ignored.

I admit to showing disdain for novices who make ridiculous claims,
and then either ignore or argue with my purely mathematical reply.
This is what happened here. I also dislike the "I am not a mathematician,
but I am doing NEW RESEARCH" type of claim.

Most of the good math professors that I have had do not simply hand
students the answer; they can not learn that way. Instead, one
discusses techniques and approaches to a problem and leads the student
to find the answer himself. i.e. the Socratic Method.

Unfortunately, too many students simply want the answer HANDED to
them (or in this case a piece of software), and only want to learn the
very minimum needed to solve the problem [b]at hand[/b]. This, of course,
leaves them unable to deal with the next problem that comes along.

I have NO patience (and see no reason why I should have any) for
students of this type.

As for being "below my level", the level matters very much. Which
is why courses have PRE_REQUISTITES. The pre-req for number theory
is a mastery of basic algebra, combined with some mathematical maturity
(aka "reasoning ability"). One should already know about proof methods,
induction, polynomial arithmetic, some elementary linear algebra,
arithmetic/geometric series, etc. About the equivalent of a strong honors
level 2nd year high school algebra course. A final prerequisite is an
INTEREST IN LEARNING THE SUBJECT.

Asking that others hand you code does not show such interest.
And believing that blindly running code written by others is doing
"new research" is just crazy.

[quote=R.D. Silverman;183064]Can't you see the difference?[/quote]Of course. I saw no reason to extend my previous remarks to encompass factors such as attitude.

[quote]I admit to showing disdain for novices who make ridiculous claims,[/quote]... and you could choose to let others do the responding to such irritants, but too often you don't IMO.

[quote]Most of the good math professors that I have had do not simply hand students the answer; they can not learn that way.[/quote]So, why not let non-professors do the handslapping on those wanting a handout?

[quote]I have NO patience (and see no reason why I should have any) for students of this type.[/quote]So, why spend any of your time at all, even to deliver a rebuke, on such folks?

Your mind is a terrible thing to waste.

[quote]As for being "below my level", the level matters very much. Which is why courses have PRE_REQUISTITES.[/quote]However, public fora don't. :-}

[quote]The pre-req for number theory is a mastery of basic algebra, combined with some mathematical maturity (aka "reasoning ability"). One should already know about proof methods, induction, polynomial arithmetic, some elementary linear algebra,
arithmetic/geometric series, etc. About the equivalent of a strong honors level 2nd year high school algebra course.[/quote]I suppose that if you were to set up a special teaching forum and require registrants to describe their math educational backgrounds before being allowed to post, you might be less vexed.

[quote]A final prerequisite is an INTEREST IN LEARNING THE SUBJECT.[/quote]I think most postings here can be taken as evidence of [I]some[/I] interest in learning [I]some[/I]thing, even if not exactly the sort of interest-in-learning you prefer to see.

[quote]Asking that others hand you code does not show such interest.[/quote]So, let us do the refusing while you interact with more worthy students.

[quote]And believing that blindly running code written by others is doing "new research" is just crazy.[/quote]An abuse of the language, at least.

Apparently, it is [I]still[/I] not obvious I am working on this sieve myself...

[QUOTE=beyastard;183084]Apparently, it is [I]still[/I] not obvious I am working on this sieve myself...[/QUOTE]

Have you considered instead of a`sieve to try P-1 factoring on these numbers? After all you have a head start on the factors of P-1.

[QUOTE=lfm;183094]Have you considered instead of a`sieve to try P-1 factoring on these numbers? After all you have a head start on the factors of P-1.[/QUOTE]

Huh? This makes no sense! These numbers don't NEED factoring;
their factorization is known.........

And a primality PROOF is easy via Brillhart-Lehmer-Selfridge (and Kraitchik
etc).

[QUOTE=cheesehead;183082]Of course. I saw no reason to extend my previous remarks to encompass factors such as attitude.

... and you could choose to let others do the responding to such irritants, but too often you don't IMO.

[/QUOTE]

Why [b]should[/b] I? Often, others do not realize that the claims are ridiculous.


[QUOTE]
So, why not let non-professors do the handslapping on those wanting a handout?
[/QUOTE]

What difference does it make who does it?

Some people seem to have missed the part of the original message where it was stated that k is the sieving variable. In k*b1^m*b2^n, b1, b2, m, n are all fixed.

Anyway beyastard, if the response in this thread hasn't put you off prime searching altogether, there is a way you can use NewPGen to sieve for primes in some of the forms k*b1^m*b2^n+1, provided you choose the coefficients carefully:

By choosing a particular form k*b1^m*b2^n+1 that can be re-written as k*(b1^r*b2^s)*(b1^t*b2^u)^v+1 where b1^r*b2^s is very small and b1^t*b2^u < 2^31, you could sieve with the NewPGen k*b^n+1 fixed-n (type 0) sieve, plus some manual filtering of the output sieve file.

For example: k*3^1001*11^500+1 can be written as k*3*99^500+1, and so you could use a NewPGen type 0 sieve for k*b^n+1 with b=99, n=500, and multiply kmin and kmax by 3 (i.e. sieve the range kmin*3 <= k <= kmax*3 instead of kmin <= k <= kmax).

Then once the sieve has run for a while and removed all the very small factors, stop it and delete all k that are not multiples of 3, before resuming sieving with the modified file.

Another example:
[quote]6904*7^987*11^654+1[/quote]

The form for this example can be written k*(7^6*11^0)*(7^3*11^2)^327+1, or simplified k*117649*41503^327+1, so you could use NewPGen type 0 sieve with b=41503, n=327, and multiply kmin and kmax by 117649. Then manually remove the k that are not multiples of 117649 from the resulting sieve file.


In practice this method will be quite limited because the multiplier for k (3 in the first example is OK, but 117649 in the second is probably too large) reduces both the efficiency of the sieve as well as the range of k that can be sieved. But it should beat trial factoring each candidate separately.

You can probably do something similar with a NewPGen fixed-k (type 16) sieve.

I'm not sure it was clear that k was the variable one, but if so, you could use a k*b^n+1 sieve with k=k, b=(b1^m*b2^n), and n=1. I don't know if you'd lose efficiency by having such a large b.

[QUOTE=Mini-Geek;183222]I'm not sure it was clear that k was the variable one, but if so, you could use a k*b^n+1 sieve with k=k, b=(b1^m*b2^n), and n=1. I don't know if you'd lose efficiency by having such a large b.[/QUOTE]

k*b^n+1 is limited to b < 2^31 in NewPGen.

[quote=geoff;183226]k*b^n+1 is limited to b < 2^31 in NewPGen.[/quote]
Oh, that throws a wrench into it all...what about the srxsieve series? Would one of them work, and be remotely efficient, for a large base, fixed n=1, and variable k?

Through the course of this thread I came to the conclusion that sieving
across a single n would be more practical. The core of this sieve I have
already completed and just working out a few small details of it. An alpha
version of it will be completed in a day or two. The way the sieve works
is for k*b1^n1*b2^n2+1 I reduce it to k1=k*b1^n1 and use k1*b2^n2+1.
As this makes k1 such a large number I am using GMP.

While writing this sieve I found a few things that will speed up sieving. Most
likely these are already known but, as I have said, I don't know all the various
algorithms for sieves as this is the first one I'm writing. Once I get the basics
done, I'll then worry about optimizing it.

[QUOTE=geoff;183217]Some people seem to have missed the part of the original message where it was stated that k is the sieving variable. In k*b1^m*b2^n, b1, b2, m, n are all fixed.

.[/QUOTE]

But now the sieve becomes TRIVIAL; you are sieving over an
arithmetic progression 1 + k * r, with r fixed for k = 0,1,2,3,.......

And even if k and r are multi-precision, the only MP code one
needs is to compute r mod p_i for each p_i in your sieve. This
is to initialize the sieve. One can even speed this sieve by using some
variant of Brent's sub-linear sieve. (but this takes a bit more MP code
to implement).

Rude Treatment of 'beyastard'
 

[QUOTE=R.D. Silverman;183272]But now the sieve becomes TRIVIAL; you are sieving over an
arithmetic progression 1 + k * r, with r fixed for k = 0,1,2,3,.......

And even if k and r are multi-precision, the only MP code one
needs is to compute r mod p_i for each p_i in your sieve. This
is to initialize the sieve. One can even speed this sieve by using some
variant of Brent's sub-linear sieve. (but this takes a bit more MP code
to implement).[/QUOTE]

Have you ever once considered that someone might live with disabilities and still have talent so they may know bits and pieces of high level knowledge of abstract mathematical concepts without knowing the full picture? Have you ever once considered sympathy or empathy?... Or is that not a commonly used process in high mathematics?

You have patiently waited for [SIZE="5"]13 years[/SIZE] to post this?
And you didn't notice that [COLOR="Navy"][B]R.D. Silverman[/B][/COLOR] answered [COLOR="navy"][B]geoff[/B][/COLOR]'s message, not 'beyastard's?
:tenyears:

[QUOTE=Batalov;631333]You have patiently waited for [SIZE="5"]13 years[/SIZE] to post this?
And you didn't notice that [COLOR="Navy"][B]R.D. Silverman[/B][/COLOR] answered [COLOR="navy"][B]geoff[/B][/COLOR]'s message, not 'beyastard's?
:tenyears:[/QUOTE]

sorry my bad i wasn't seeing clearly