>As far as I understand, sieve methods
>generally are used (computationally) to sieve for useful candidates
>in a long list to generate a list of better candidates which are
>then laborously checked.
>For instance, if you were looking for a long
>list of primes, then you could take a long list of integers and
>trial divide against a list of small primes
This is the difference between a "sieve" and an iterative process
like you list above (in the original post Jack was using an iterative
process and not a sieve).
In this trivial example, a list of numbers from 10000001 to 11000001
will be searched for primes.
Note, 10000001 to 11000001 are frequently MUCH larger, and may be
certain forms of expressions, patterns, or other groupings which
have certain arithmetic properties.
Take 10000001 and see if 2, 3, 5, 7, 11, ... divides it. If not,
then keep it for a longer test.
Take 10000002 and see if 2, 3, 5, 7, 11, ... divides it. If not,
then keep it for a longer test.
Take 10000003 and see if 2, 3, 5, 7, 11, ... divides it. If not,
then keep it for a longer test.
When done, test whatever survived.
Determine that 2 divides 10000001+1.
Cross out that number, and every other number from that point on.
Determine that 3 divides 10000001+1.
Cross out that number and every third number from that point on.
Determine that 5 divides 10000001+4.
Cross out that number and every fifth number from that point on.
Any value not "crossed-out" is tested.
The difference between the 2 processes, is that the iterative process
requires O(X*Y) time, while the sieve requires O(X) time [where X is
the count of small prime factors, and Y is the number of candidate
In the sieve, we are assuming that division is a costly step (it
is), and that "crossing out" candidates can be done much faster.
We try to avoid division, by using the fact that if we know that
N%p is 0, then (N+k*p)%p is also 0. We have thus removed 1/p of
our candidates, without having to perform Y divisions. If we had
10 candiates, we would only have to find the "starting" point for
each factor prime once. If we have 10 million candidates, we still
only have to find that starting point once. If using iterative
division, then for 10 candidates, we perform division by a prime 10
times, and for 10 million candidates, we perform 10 million
The down side to a sieve, is that finding the starting point, is
frequently very costly (more costly than divisision usually). Also,
it is highly likely that there will be NO candidates (left) that have
a factor of the prime we are searching for. Take for instance, if
we had 10 canidates to start with. Using a sieve to factor them is
not very useful. The simple iterative trial division is probably
much faster in this case. However, if there were 10 million
starting candidates, then using a sieve (even if the step of finding
the starting point is 10 times more CPU intensive than a single
division), is much faster, due to the number of candidates.
Another "down side", is that not all expression forms "fit" into a
sieve model. Searches such as the Mersenne prime search,
unfortunately do not allow for a sieve to be used. Each candidate
must stand on it's own, due to the types of numbers that divide each
candidate, and an iterative process must be used. However there are
many forms where a sieving process can be used.
Not all "sieves" try to simply eliminate composites.
In the search Jack listed, you might write a sieve to:
have X number of "buckets".
Each bucket capable of holding factors.
Then perform a sieve where you place a 2 in the bucket #2 #4 #6 ...
place a 3 in bucket #3 #6 #9 ....
place a 5 in bucket #5 #10 #15 ...
(in each step above, you would have to place as many 2's, 3's, or
other factor as would "fit" into the bucket, i.e. the bucket #24
would get 3 2's and 1 3)
When done, throw out any bucket with too few, or too many factors.
Then search for consecutive buckets.
Then see if these consecutive bucket have factors of equal size.
This would be considered a sieve (verses iterative process), due to
not "trying" to fully work with each candidate number, but
performing the work on the whole 'set' and then later observing the
results. Note the above method, while it would work, is far from
optimal, as it is testing values which could NEVER be a solution
(note that the first integer of the six must be congruent to either
3770 or 84425 (mod 88200).) Any sieve would have to work within
those bounds, or end up being much slower than Jack's "crude" method.
--- In firstname.lastname@example.org, "Adam" <a_math_guy@y...> wrote:
> "Sieve methods" is something that confuses me about many posts to
> this group. It seems to be thrown around a lot, and sometimes I
> don't quite "get it." As far as I understand, sieve methods
> generally are used (computationally) to sieve for useful
> in a long list to generate a list of better candidates which are
> laborously checked. For instance, if you were looking for a long
> list of primes, then you could take a long list of integers and
> divide against a list of small primes (e.g., make sure none of the
> numbers are even, divisible by 3, etc.), then PrP them to get a
> smaller list, then finally test for primality.
> What confuses me about this post, and previous ones that refer to
> sieveing, is how do you generate the "sieve concept"? Is there an
> automated process, or do you have figure out specific concepts re:
> sieveing first relevant to the particular problem?
> --- In email@example.com, "jbrennen" <jack@b...> wrote:
> > After over three days of CPU time, I found the first group of six
> > consecutive integers whose prime factorizations have the same
> > pattern of digit lengths (in base 10, of course).
> > That may be a little confusing, so let me give the result, which
> > should clear things up a bit:
> > 853173502025 == 5 * 5 * 13 * 2625149237
> > 853173502026 == 2 * 3 * 37 * 3843123883
> > 853173502027 == 7 * 7 * 11 * 1582882193
> > 853173502028 == 2 * 2 * 29 * 7354943983
> > 853173502029 == 3 * 3 * 59 * 1606729759
> > 853173502030 == 2 * 5 * 17 * 5018667659
> > Each number is a one-digit-prime times a one-digit-prime times a
> > two-digit prime times a ten-digit-prime. The actual pattern is
> > not important, just the fact that six consecutive integers all
> > share the same pattern.
> > Smaller records include:
> > (two consecutive numbers)
> > 2 == 2
> > 3 == 3
> > (three consecutive numbers)
> > 85 == 5 * 17
> > 86 == 2 * 43
> > 87 == 3 * 29
> > (four consecutive numbers)
> > 34172 == 2 * 2 * 8543
> > 34173 == 3 * 3 * 3797
> > 34174 == 2 * 7 * 2441
> > 34175 == 5 * 5 * 1367
> > (five consecutive numbers)
> > 779930 == 2 * 5 * 23 * 3391
> > 779931 == 3 * 3 * 19 * 4561
> > 779932 == 2 * 2 * 73 * 2671
> > 779933 == 7 * 7 * 11 * 1447
> > 779934 == 2 * 3 * 43 * 3023
> > Before somebody attempts to "best" this result by finding a group
> > of seven consecutive integers with the same pattern, let me warn
> > you... No such group exists. The proof is left to the
> > If anybody would like to find some more examples of six, perhaps
> > to justify inclusion in the OEIS, note that the first integer of
> > the six must be congruent to either 3770 or 84425 (mod 88200).
> > My crude method of factoring every such group of six completely
> > and then testing for compatibility could be greatly improved upon
> > by using sieve methods.