Sieve needed for k*b1^m*b2^n+1

[R.D. Silverman]

Originally Posted by cheesehead

It's not arrogance (he can 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).

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

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 at hand. 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.

[cheesehead]

Originally Posted by R.D. Silverman

Can't you see the difference?

Of course. I saw no reason to extend my previous remarks to encompass factors such as attitude.

I admit to showing disdain for novices who make ridiculous claims,

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

Most of the good math professors that I have had do not simply hand students the answer; they can not learn that way.

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

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

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.

As for being "below my level", the level matters very much. Which is why courses have PRE_REQUISTITES.

However, public fora don't. :-}

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.

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.

A final prerequisite is an INTEREST IN LEARNING THE SUBJECT.

I think most postings here can be taken as evidence of some interest in learning something, even if not exactly the sort of interest-in-learning you prefer to see.

Asking that others hand you code does not show such interest.

So, let us do the refusing while you interact with more worthy students.

And believing that blindly running code written by others is doing "new research" is just crazy.

An abuse of the language, at least.

[beyastard]

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

[lfm]

Originally Posted by beyastard

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

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.

[R.D. Silverman]

Originally Posted by lfm

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.

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).

[R.D. Silverman]

Originally Posted by cheesehead

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.

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

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

What difference does it make who does it?

[geoff]

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:

6904*7^987*11^654+1

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.

[TimSorbet]

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.

[geoff]

Originally Posted by Mini-Geek

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.

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

[TimSorbet]

Originally Posted by geoff

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

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?

[beyastard]

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.