## Other

drummers-lowrise

Message boards : Extended Sierpinski Problem : Can I see my factors? How?

 Subscribe SortOldest firstNewest firstHighest rated posts first
Author Message
River~~

Joined: 17 Mar 07
Posts: 342
ID: 6533
Credit: 15,792,075
RAC: 0

Message 93437 - Posted: 25 Mar 2016 | 20:25:48 UTC

hi everyone,

So far I've been awarded a quarter of a million BOINC points and found no primes. I am told by my "your account" page that I have found 2 factors in the Sierpinski project work. Clearly this is a bit difficult as there for each task that found a factor there were 441 that didn't. So its kind of nice to know I have achieved that.

So my next question is, can I find out what these factors are? And what the numbers are that were being factorised?

I am not sure if the info already exists on the website, in which case my request it for a pointer to it; or if I am actually asking for you to add some new feedback - and if so how hard that would be to do.

And, of course, if I find a prime before I read your answer, I will likely lose interest in the factors, but in the meantime it would be nice to be able to find out. So I'm not asking you to put much work into it. Just, if it is relatively easy, it would be nice.

R~~

JimB
Honorary cruncher

Joined: 4 Aug 11
Posts: 916
ID: 107307
Credit: 974,532,191
RAC: 0

Message 93446 - Posted: 26 Mar 2016 | 0:22:03 UTC - in response to Message 93437.

So far I've been awarded a quarter of a million BOINC points and found no primes. I am told by my "your account" page that I have found 2 factors in the Sierpinski project work. Clearly this is a bit difficult as there for each task that found a factor there were 441 that didn't. So its kind of nice to know I have achieved that.

So my next question is, can I find out what these factors are? And what the numbers are that were being factorised?

You're doing sieving. You've found factors for candidates with n values around 26M and 47M. What this means is that you've proven they're composite - they'll be removed from the sieve and never looked at again. They will never be tested by LLR.

I am not sure if the info already exists on the website, in which case my request it for a pointer to it; or if I am actually asking for you to add some new feedback - and if so how hard that would be to do.

We don't make those factors available. While I can see them with some effort, the only reason we do sieving is to reduce the number of candidates we have to do primality-testing on. There were for example huge numbers of candidates removed by the factors 3, 5, and 7. So many that we don't bother keeping them at all. It's easier and far faster (under 10 minutes to sieve to 100M) to redo that sieving if required than to store tens of gigabytes of factors forever. The important part is that those candidates are removed from the sieve as we've proved beyond the shadow of a doubt that they're composite (non-prime).

And, of course, if I find a prime before I read your answer, I will likely lose interest in the factors, but in the meantime it would be nice to be able to find out. So I'm not asking you to put much work into it. Just, if it is relatively easy, it would be nice.

You're not going to find any primes. Sieving is done to prove that candidates are composite (that's the definition of composite - that they have a factor other than themselves or 1) and so remove them from consideration. In any case, what we're sieving now is ESP candidates for n=10M-50M. The ESP LLR subproject is testing candidates around n=9.1M. When n reaches 10M we'll need new candidates and that's when we'll start using the sieve file generated from the current ESP/PSP/SoB sieving. By then sieving will have reached the same p=90P level that SoB and PSP are sieved to for the same n range. At that point either the sieving subproject will be suspended or I'll add the PSP and SoB candidates back into the sieve. I haven't yet done any calculations on whether we'll have reached an optimal sieving level at that point, but past administrators thought we had.

What is the optimal sieving level? When it takes longer to remove a candidate by sieving than it takes to test it with LLR, it no longer makes sense to do further sieving. This is complicated a bit by the fact that we're sieving n=10M-50M and removing a candidate near the top of that range saves a lot more time than removing one near the beginning. One also has to take into account that every candidate is LLR tested at least twice, so in fact we'll sieve until removals take twice the LLR testing time.

Because all this talk about k, n and p used to confuse me when I was new here:

We check candidates (for ESP) of the form k*2^n+1 where k is a small list of values for which there are no known primes and n is an ever-increasing number currently around 9,100,000. The sieving is testing for factors (p). On our sieving p is currently between 80P and 81P - the exact value of p for the leading edge is 80,896,535,000,000,000. And that's already out of date before I finish typing this next sentence. So we're trying to divide candidates by numbers in that range. Actually we're figuring out the remainder from any such division - a remainder of zero says it divides evenly and means you've found a factor. The factor is reported back and if another user gets the same result the factor is verified and then added into our factor table. Once in a while I take all those factors and use them to make a new sieve file that always has fewer candidates than the previous version. When we need candidates to LLR test, that sieve file is the list of candidates we use.

While it's certainly possible to be sieving and LLR testing the same n range, it's more efficient to finish the sieving first. That yields the fewest candidates that will need to be tested by LLR. And that's the situation with this sieving.

River~~

Joined: 17 Mar 07
Posts: 342
ID: 6533
Credit: 15,792,075
RAC: 0

Message 93456 - Posted: 26 Mar 2016 | 11:30:21 UTC - in response to Message 93446.

You're doing sieving. You've found factors for candidates with n values around 26M and 47M. What this means is that you've proven they're composite - they'll be removed from the sieve and never looked at again. They will never be tested by LLR.

sure, I understand that

We don't make those factors available. ... The important part is that those candidates are removed from the sieve as we've proved beyond the shadow of a doubt that they're composite (non-prime).

sure, those factors are no use to the project. And I do take your point that if you are finding zillions of them you do not want to store them all.

But as a user I'd still be interested in knowing at least some of them. I am wondering if there is any summary info that you could keep, with only a small number of bytes per account?

When you do find one, at present you already bump a counter somewhere in your database that is specific to my account. I am wondering if, sometime in the future and not for past results, it would be easy for you to add another column to the relevant table to show the most recent factor found? or the largest factor so far? or both?

Or maybe even the cumulative total of numbers below a specified limit that have been sieved out by the factor? (obviously if you don't give an upper bound the number of composites excluded is trivial to code in as "infinity")

Or can you think of some other useful summary data that would be interesting to users, beyond the simple count?

By the way, I want to thank you for providing the count - it encourages me to paerticipate further when I see some documentarty evidence of my contribution to the project.

You're not going to find any primes. ..

not from these tasks, no. But the other projects I am running do have blank spaces for prime counts. And what I intended to say was that when any of those blanks turns into a "1" then I will immediately be less interested in detail about factors.

I am suggesting, though, that as anyone crunching a mix of tasks is incredibly likely to find factors before the find a prime, it would be a useful encouragement to people new to the project to see a little more info. And encourage people who are affected by such things (including me) to lift some of the sieving weight as well as helping with the glory seeking prime hunting.

You will, of course, want to weigh up the positive effects of that effect against the effort needed to add the info. I don't presume to know how much work that would be for you so if you say it's not worth the effort that is OK. And all the more so if the current round of sieving is coming to an end soon. I hope you will still bear these thoughts in mind at any future time when there is new sieving software being written.

Because all this talk about k, n and p used to confuse me when I was new here:

We check candidates (for ESP) of the form k*2^n+1 where k is a small list of values for which there are no known primes and n is an ever-increasing number currently around 9,100,000. The sieving is testing for factors (p). On our sieving p is currently between 80P and 81P - the exact value of p for the leading edge is 80,896,535,000,000,000. And that's already out of date before I finish typing this next sentence. So we're trying to divide candidates by numbers in that range. Actually we're figuring out the remainder from any such division - a remainder of zero says it divides evenly and means you've found a factor. The factor is reported back and if another user gets the same result the factor is verified and then added into our factor table. Once in a while I take all those factors and use them to make a new sieve file that always has fewer candidates than the previous version. When we need candidates to LLR test, that sieve file is the list of candidates we use.

thanks, yes that clarifies a lot. And I am thinking that the p is prime? (the choice of letter is a bit of a clue!) Like you don't test for divisibility by 6 when testing a number for primality, you don't need to filter the sixes out with your sieve as the twos have already got them (or the threes if you happened to check in the "wrong" order).

While it's certainly possible to be sieving and LLR testing the same n range, it's more efficient to finish the sieving first. That yields the fewest candidates that will need to be tested by LLR. And that's the situation with this sieving.

So, any sieving you do could *eventually* be useful, when we or our grandchildren get around to LLR work in the area we reached -- except that the cost of holding such a long sieved number line exceeds the eventual value.

Threrfore you are sieving with an upper bound in mind for the coming LLR work, and restart from scratch when the LLR upper bound moves significantly.

R~~

JimB
Honorary cruncher

Joined: 4 Aug 11
Posts: 916
ID: 107307
Credit: 974,532,191
RAC: 0

Message 93460 - Posted: 26 Mar 2016 | 13:02:06 UTC - in response to Message 93456.

sure, those factors are no use to the project. And I do take your point that if you are finding zillions of them you do not want to store them all.

But as a user I'd still be interested in knowing at least some of them. I am wondering if there is any summary info that you could keep, with only a small number of bytes per account?

We're not going to be showing factors. I would have to rewrite how they're stored, among other things. I have a huge list of things I want to get done at this site and this is not one of them.

And I am thinking that the p is prime? (the choice of letter is a bit of a clue!) Like you don't test for divisibility by 6 when testing a number for primality, you don't need to filter the sixes out with your sieve as the twos have already got them (or the threes if you happened to check in the "wrong" order).

Yes, the sieve program is only checking prime factors. The operation to test if it's a divisor (we're not actually dividing) is computationally expensive and we want to do it as few times as possible. So it's worth calculating primes to use there. There may be the occasional pseudo-prime in there, but they don't occur often enough to matter.

So, any sieving you do could *eventually* be useful, when we or our grandchildren get around to LLR work in the area we reached -- except that the cost of holding such a long sieved number line exceeds the eventual value.

Threrfore you are sieving with an upper bound in mind for the coming LLR work, and restart from scratch when the LLR upper bound moves significantly.

Some sieving, like PPR12M manual sieving, will be used years from now. This ESP sieving we're currently running will start being used next year at the latest. Exactly when depends on how fast current ESP candidates are used up. The supply of ESP candidates will then last for years, since candidates get so much larger. n is always increasing and n is an exponent: 2^n. So the candidate roughly doubles in size every time n increases by 1. I say roughly because we're testing k*2^n+1 and there are 11 different k values at the moment: 91549, 99739, 131179, 163187, 193997, 200749, 202705, 209611, 227723, 229673, 238411. See here for a more complete explanation.

Edit: We're talking about ESP sieving (those are the only k values in the sieve right this moment), so I'm going to move this thread into the ESP forum.

Michael Goetz
Volunteer moderator

Joined: 21 Jan 10
Posts: 13633
ID: 53948
Credit: 279,494,797
RAC: 112,655

Message 93461 - Posted: 26 Mar 2016 | 14:18:14 UTC

Folks (not you specifically) need to understand the concept of low hanging fruit.

When someone asks for something "nice to have", if it's low hanging fruit (meaning "easy to do"), we're likely to do it. If I can reach the fruit while standing on the ground, it's no big deal. Even if I need a step-stool or a small ladder it might get done if the idea has sufficient merit.

But if I need a Saturn V to get to the fruit, it's not going to happen.

This one needs at least a Falcon 9 to get to. :)

(Even if Jim wanted to do this for some reason, I might try to talk him out of it because the risk of breaking something that wouldn't be discovered until long after the damage is done far outweighs any potential benefits. We measure cost not only in the amount of time and effort, but also in terms of risk.)

____________
My lucky number is 75898524288+1

River~~

Joined: 17 Mar 07
Posts: 342
ID: 6533
Credit: 15,792,075
RAC: 0

Message 93515 - Posted: 27 Mar 2016 | 17:09:58 UTC - in response to Message 93461.

Mike, Jim:

I did say in my request that this is something I'd like _if_ it was reasonably easy to do. I like Mike's analogy of the low hanging fruit - I've met that analogy in other situations but not with reference to user feedback.

What I'm hearing from each of you is that I don't realise how hard it would be to provide what you have asked. That is a good answer, as far as I am concerned, and I am happy to leave it there.

Thank you both for taking the time to explain, rather than just saying an unsupported "no".

R~~

Joined: 25 Aug 11
Posts: 61
ID: 109842
Credit: 110,654,752
RAC: 0

Message 96661 - Posted: 6 Jul 2016 | 10:30:07 UTC - in response to Message 93437.

Well how about 57 million in Prime with 1 prime found in SOB. Lots of factors found but that seem pretty worthless. You kinda start to lose interest after a while, at least I do.

gazzyk1ns

Joined: 2 Aug 11
Posts: 1329
ID: 107047
Credit: 361,466,164
RAC: 26,228

Message 97135 - Posted: 26 Jul 2016 | 2:05:10 UTC

But they aren't worthless, are they? If you find 20 factors then you've saved a week or so of LLRing and double checking those candidates, taking into account that whilst some might have been double-LLR'd very quickly and efficiently, others would have failed and got kicked around messily for ages.

Crun-chi
Volunteer tester

Joined: 25 Nov 09
Posts: 3059
ID: 50683
Credit: 63,361,547
RAC: 0

Message 97213 - Posted: 26 Jul 2016 | 19:57:17 UTC - in response to Message 96661.

Well how about 57 million in Prime with 1 prime found in SOB. Lots of factors found but that seem pretty worthless. You kinda start to lose interest after a while, at least I do.

Look that problem on the other side...
Let`s say that you need 3 hours per one task to complete it. Then someone give you 45000 tasks, and say: hey, here , in 45000 task is two primes. You take calculator and start 45000*3 hours per task = 135000 hours / 4 ( average CPU with 4 cores) =33750/24= 1406 days / 30 ( days) = 46 months...

And now, good guy came to you and say: but hey I have VERY VERY GOOD sieve and it only contains 10000 task for same number of prime...
Then you take calc : 10000*3 hours per task =30000 hours / 4 cpu cores = 7500 hours /24=312 days / 30 ( days per month) = 10 months

So tell me: if you have patience will you take 45000 tasks for two primes or you take 10000 tasks for same two primes?

As you can see, time difference is huge: even ordinary user with only 2 CPU (8 cores) will finish in only five months .

But if you wont to make that VERY VERY VERY good sieve file you must uses your resources as you do, find as you say worthless factors and remove factors as many as possible.

Believe me, many times I lost my patience because I made average sieve , and must process many more candidates that it is needed.

Now, I can go as far I can go.. but no one files on Internet (sieve files) are not sieved deep as this data from Primegrid. And for that data, all of you , who sieve share some credits.... :)
____________
92*10^1439761-1 NEAR-REPDIGIT PRIME :) :) :)
4 * 650^498101-1 CRUS PRIME
314187728^131072+1 GENERALIZED FERMAT
Proud member of team Aggie The Pew. Go Aggie!

Message boards : Extended Sierpinski Problem : Can I see my factors? How?