mersenneforum.org  

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

Reply
 
Thread Tools
Old 2020-09-12, 05:47   #1
bur
 
Aug 2020

2×3×5 Posts
Default 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
bur is offline   Reply With Quote
Old 2020-09-12, 07:49   #2
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

887310 Posts
Default

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
LaurV is offline   Reply With Quote
Old 2020-09-12, 08:22   #3
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

33·163 Posts
Default

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).
VBCurtis is online now   Reply With Quote
Old 2020-09-13, 16:32   #4
bur
 
Aug 2020

2·3·5 Posts
Default

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.

Last fiddled with by bur on 2020-09-13 at 16:36
bur is offline   Reply With Quote
Old 2020-09-14, 06:40   #5
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

104618 Posts
Default

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.
VBCurtis is online now   Reply With Quote
Old 2020-09-14, 08:13   #6
bur
 
Aug 2020

2·3·5 Posts
Default

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
bur is offline   Reply With Quote
Old 2020-09-29, 17:10   #7
bur
 
Aug 2020

111102 Posts
Default

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
bur is offline   Reply With Quote
Old 2020-09-30, 03:32   #8
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

887310 Posts
Default

Quote:
Originally Posted by bur View Post
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.
LaurV is offline   Reply With Quote
Old 2020-10-03, 06:01   #9
bur
 
Aug 2020

1E16 Posts
Default

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.
bur is offline   Reply With Quote
Old 2020-10-03, 13:35   #10
Happy5214
 
Happy5214's Avatar
 
"Alexander"
Nov 2008
The Alamo City

39010 Posts
Default

Quote:
Originally Posted by LaurV View Post
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 View Post
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.
Happy5214 is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 02:51.

Thu Oct 29 02:51:28 UTC 2020 up 49 days, 2 mins, 1 user, load averages: 1.34, 1.55, 1.59

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.