General question about sieving software

bur · 2020-09-12, 05:47

I'm not sure if this is the proper section, but anyway.

Sieve of Eratosthenes takes a prime, marks all multiples of it, then moves to the next unmarked number and so on. But when I view the output of sieving software such as sr2sieve it appears like each prime has at max one number it factors. In factors.txt no prime turns up more than once. It seems like sieving stops as soon as one multiple of that prime is found.

So what if that particular prime is a factor of more than one candidate in the sieve file? Especially for small primes such as 2 or 3 this will happen a lot and I'm sure it's taken care of, but how?

LaurV · 2020-09-12, 07:49

If you sieve for n to 1 million, you have one million candidates, but you sieve with primes much larger. Take a range of 1 million consecutive numbers. Small primes (below 1 million) are sieved out so fast that you can't see them

(not really, but you got the idea, see below). For the larger primes, most of them will divide no candidate from the million consecutive numbers, as their "step" (say, in Eratosthenes' sieve) is larger then a million, they will completely "jump over" your interval. Few primes will "step" into your interval, but only once, as their "step" is larger than a million, next step is outside. Does this makes sense?

Showing all "small primes" stuff is not wanted, because it is bloody time consuming (printing on screen or saving in a file). But you can do it, if you want.

For srsieve and relatives, there is a parameter (maybe -m ?? you have to check, my memory is weaker and weaker) which says "do not show factored candidates for primes lower than this value", which is by default (if not specified), set to 1 million (again, please double check this). You can use "-m 2" or "-m 11" to see all candidates eliminated when sieving with primes larger than 2, respectively larger than 11 (for example). In the first case, you will see an endless stream of candidates eliminated by the prime 3 (all numbers in your range which are divisible by 3).

VBCurtis · 2020-09-12, 08:22

newpgen also does not print the candidates factored out by small primes, but when one fires it up on a new sieve it'll give a status line for each prime. So, you'll be able to see just how many candidates are divisible by 5.

srsieve is faster than newpgen, so one would run the older software only for this curiosity (or for other forms for which newpgen works but sr[x]sieve doesn't).

bur · 2020-09-13, 16:32

Quote:

For the larger primes, most of them will divide no candidate from the million consecutive numbers, as their "step" (say, in Eratosthenes' sieve) is larger then a million, they will completely "jump over" your interval. Few primes will "step" into your interval, but only once, as their "step" is larger than a million, next step is outside.

I don't really get it. The candidates aren't a million consecutive numbers. Only the n is consecutive.

Say my primes are of magnitude 1E12 and candidates are k * 2^1E6 + 1. Then any of the primes can easily factor various candidates. For example 1E12 * 1E100 is 1E125 which is still much smaller than my candidates which are on the magnitude of 1E1000000. But since I will probably not sieve up to 1E125 I will not find that composite number.

That all those composites are not printed to screen, I get that. But the factors.txt also doesn't contain more than one composite per prime. And that also applies to relatively small primes around 1E5.

VBCurtis · 2020-09-14, 06:40

I don't think it applies to even-smaller primes than 1e5- small primes should divide many candidates.

By the time you're sieving out a prime near 100,000, I think there are fewer than 100k candidates left in your sieve, and it's merely unlikely for one to divide more than one candidate; however, if it was a random occurence, it *should* happen once in a while. Can you set a sieve to record factors from 10,000 to 100,000 and see if you find instances of one prime factoring multiple candidates? or 1,000 to 2,000?

Maybe it's just so rare at large values that you haven't seen it yet.

bur · 2020-09-14, 08:13

The thing is, what does happen is that a single candidate is factored by more than one prime in a relatively small range.

The sieve file contains 65000 candidates and I was sieving in four seperate instances in ranges like 20E11-25E11, 25E11 to 30E11 and so on. Almost always the sr2sieve.exe with higher range reported, e.g. 400 found factors and only 375 got removed by srfile because the remaining 25 were already removed in the 20E11-25E11 factors.txt.

Of course having one candidate being factored by several primes if different from one prime factoring several candidates.

Still, I'd like to know how this is handled. Is certain that a prime is only considered until one factoring candidate was found? Especially for primes around 100,000 this seems inefficient as I would think one prime factors more than one candidate in the sieve. Maybe it's not worth the effort though.

bur · 2020-09-29, 17:10

For the record, common sieving software DOES check all candidates in the sieve against a prime factor. The reason why you almost never see a prime dividing more than one candidate is simply that the chances are so low.

For example, my current sieving with P ~ 1E12 yields one factor in about 1E10 primes. So the probability that one prime divides two candidates is around 1E20.

What I still don't understand is, why it apparently happens often that a candidate is divided by more than one prime in a relatively small range of say 10E12 to 11E12. I think that's strange, because the fact that the candidate is still in the sieve means it didn't have any prime factor for 2 < p < 10E12. But it has two in that aforementioned range. Could be conincidence, but it happened frequently for a sieve with about 75000 candidates.

At least I assume that happens since when I run four sr2sieve instances simultaneously on the same abcd file and afterwards remove the factors srfile frequently removes 1 less candidate then the respective sr2sieve reported factors. So I assumed the candidate was already removed by another factor.

LaurV · 2020-09-30, 03:32

Quote:

Originally Posted by bur

I don't really get it. The candidates aren't a million consecutive numbers. Only the n is consecutive.

So what? Take a million odd numbers. Or a million numbers of the form n^2+1. They are not consecutive, but from sieving point of view, they are. When you sieve them with the prime 3, you still count (by some algorithm, in case of consecutive n, once you figure out how/where to start), one, two, three, cut it out, one, two, three, cut it out, one, two, three, cut it out, one, two, three, cut it out. Think about it.

bur · 2020-10-03, 06:01

Sorry, but I still don't get it. Using 2^n + 1 for the first 10 values we get:

3 5 9 17 33 65 129 257 513 1025

5 divides the 2nd, 6th and 10th candidate. So it divides not at most every 5th number, but more. The same should apply to much larger prime factors.

Happy5214 · 2020-10-03, 13:35

Quote:

Originally Posted by LaurV

So what? Take a million odd numbers. Or a million numbers of the form n^2+1. They are not consecutive, but from sieving point of view, they are. When you sieve them with the prime 3, you still count (by some algorithm, in case of consecutive n, once you figure out how/where to start), one, two, three, cut it out, one, two, three, cut it out, one, two, three, cut it out, one, two, three, cut it out. Think about it.

Quote:

Originally Posted by bur

Sorry, but I still don't get it. Using 2^n + 1 for the first 10 values we get:

3 5 9 17 33 65 129 257 513 1025

5 divides the 2nd, 6th and 10th candidate. So it divides not at most every 5th number, but more. The same should apply to much larger prime factors.

Note the bolded parts (you're working with different sequences). But even with 2^n + 1, notice that (assuming the first term listed above is index 1) 3 divides every term of index form 2n+1 (i.e. odd) (3, 9, 33, 129, 513, 2049, ...), 5 divides every term of index form 4n+2 (5, 65, 1025, 16385, ...), 17 divides every term of index form 8n+4 (17, 4097, ...), and so on. There's a sieve right there.

2020-09-12, 05:47	#1
bur Aug 2020 2×19 Posts	General question about sieving software I'm not sure if this is the proper section, but anyway. Sieve of Eratosthenes takes a prime, marks all multiples of it, then moves to the next unmarked number and so on. But when I view the output of sieving software such as sr2sieve it appears like each prime has at max one number it factors. In factors.txt no prime turns up more than once. It seems like sieving stops as soon as one multiple of that prime is found. So what if that particular prime is a factor of more than one candidate in the sieve file? Especially for small primes such as 2 or 3 this will happen a lot and I'm sure it's taken care of, but how? Last fiddled with by bur on 2020-09-12 at 05:48

2020-09-12, 07:49	#2
LaurV Romulan Interpreter Jun 2011 Thailand 3⁴×113 Posts	If you sieve for n to 1 million, you have one million candidates, but you sieve with primes much larger. Take a range of 1 million consecutive numbers. Small primes (below 1 million) are sieved out so fast that you can't see them (not really, but you got the idea, see below). For the larger primes, most of them will divide no candidate from the million consecutive numbers, as their "step" (say, in Eratosthenes' sieve) is larger then a million, they will completely "jump over" your interval. Few primes will "step" into your interval, but only once, as their "step" is larger than a million, next step is outside. Does this makes sense? Showing all "small primes" stuff is not wanted, because it is bloody time consuming (printing on screen or saving in a file). But you can do it, if you want. For srsieve and relatives, there is a parameter (maybe -m ?? you have to check, my memory is weaker and weaker) which says "do not show factored candidates for primes lower than this value", which is by default (if not specified), set to 1 million (again, please double check this). You can use "-m 2" or "-m 11" to see all candidates eliminated when sieving with primes larger than 2, respectively larger than 11 (for example). In the first case, you will see an endless stream of candidates eliminated by the prime 3 (all numbers in your range which are divisible by 3). Last fiddled with by LaurV on 2020-09-12 at 07:50

2020-09-14, 08:13	#6
bur Aug 2020 2×19 Posts	The thing is, what does happen is that a single candidate is factored by more than one prime in a relatively small range. The sieve file contains 65000 candidates and I was sieving in four seperate instances in ranges like 20E11-25E11, 25E11 to 30E11 and so on. Almost always the sr2sieve.exe with higher range reported, e.g. 400 found factors and only 375 got removed by srfile because the remaining 25 were already removed in the 20E11-25E11 factors.txt. Of course having one candidate being factored by several primes if different from one prime factoring several candidates. Still, I'd like to know how this is handled. Is certain that a prime is only considered until one factoring candidate was found? Especially for primes around 100,000 this seems inefficient as I would think one prime factors more than one candidate in the sieve. Maybe it's not worth the effort though. Last fiddled with by bur on 2020-09-14 at 08:13

2020-09-29, 17:10	#7
bur Aug 2020 2·19 Posts	For the record, common sieving software DOES check all candidates in the sieve against a prime factor. The reason why you almost never see a prime dividing more than one candidate is simply that the chances are so low. For example, my current sieving with P ~ 1E12 yields one factor in about 1E10 primes. So the probability that one prime divides two candidates is around 1E20. What I still don't understand is, why it apparently happens often that a candidate is divided by more than one prime in a relatively small range of say 10E12 to 11E12. I think that's strange, because the fact that the candidate is still in the sieve means it didn't have any prime factor for 2 < p < 10E12. But it has two in that aforementioned range. Could be conincidence, but it happened frequently for a sieve with about 75000 candidates. At least I assume that happens since when I run four sr2sieve instances simultaneously on the same abcd file and afterwards remove the factors srfile frequently removes 1 less candidate then the respective sr2sieve reported factors. So I assumed the candidate was already removed by another factor. Last fiddled with by bur on 2020-09-29 at 17:10

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
General factoring algorithms not using sieving	mickfrancis	Factoring	21	2016-02-22 19:38
S9 and general sieving discussion	Lennart	Conjectures 'R Us	31	2014-09-14 15:14
What about general purpose sieving of k*b^n+/-1?	jasong	GPU Computing	1	2012-04-03 10:52
new sieving software	Thomas11	Riesel Prime Search	81	2011-11-05 19:16
Sieving Software	lavalamp	Software	10	2007-10-20 23:07

2020-09-12, 08:22	#3
VBCurtis "Curtis" Feb 2005 Riverside, CA 3⁵·19 Posts	newpgen also does not print the candidates factored out by small primes, but when one fires it up on a new sieve it'll give a status line for each prime. So, you'll be able to see just how many candidates are divisible by 5. srsieve is faster than newpgen, so one would run the older software only for this curiosity (or for other forms for which newpgen works but sr[x]sieve doesn't).

2020-09-14, 06:40	#5
VBCurtis "Curtis" Feb 2005 Riverside, CA 3⁵·19 Posts	I don't think it applies to even-smaller primes than 1e5- small primes should divide many candidates. By the time you're sieving out a prime near 100,000, I think there are fewer than 100k candidates left in your sieve, and it's merely unlikely for one to divide more than one candidate; however, if it was a random occurence, it should happen once in a while. Can you set a sieve to record factors from 10,000 to 100,000 and see if you find instances of one prime factoring multiple candidates? or 1,000 to 2,000? Maybe it's just so rare at large values that you haven't seen it yet.

2020-10-03, 06:01	#9
bur Aug 2020 46₈ Posts	Sorry, but I still don't get it. Using 2^n + 1 for the first 10 values we get: 3 5 9 17 33 65 129 257 513 1025 5 divides the 2nd, 6th and 10th candidate. So it divides not at most every 5th number, but more. The same should apply to much larger prime factors.