n weight

[b2uc]

Currently I'm looking at a relationship between k mod 30 and k mod 7 relating to found passed primes for Riesel Sieve. It's a little more complicated than that but it's my start. I wanted to see how that matched up against n weight. It seems as though for me it went smoothly. Atleast what I calculated as the ending digit for n was one of the few remaining choices. Below is a list of SoB k's and the bust out for ending digits of n. We know that k's ending in 1 and 9 are even n's and those ending in 1, 3 and 7 will have odd n's. The sieve takes care of this in the first few passes. The sieve also should have quickly taken out all k/n pairs that didn't produce a number that ended in 7 for SoB and ending in 3 for Riesel Sieve. I've yet to check for SoB but for Riesel Sieve every k/n pair produces a number that ends in 3...so we know that all our primes will end in 3...just as all Primes found for SoB will end in 7. This is for k's that are kmod 30= 1,17,19 and 23. Other kmod 30 values follow different rules and prime out much sooner. Take a look at the chart.


K #Ns 0 1 2 3 4 5 6 7 8 9
4847 71346 0 24044 0 20927 0 0 0 26375 0 0
5359 88505 25164 0 33079 0 0 0 30262 0 0 0
10223 82150 0 21760 0 0 0 17928 0 22307 0 20155
19249 29988 0 0 10467 0 0 0 8755 0 10766 0
21181 70322 17209 0 19162 0 17076 0 0 0 16875 0
22699 28842 7089 0 6999 0 7121 0 0 0 7633 0
24737 74099 0 27442 0 25892 0 0 0 20765 0 0
27653 41348 0 6534 0 8597 0 8351 0 8575 0 9291
28433 39941 0 0 0 12857 0 14459 0 12625 0 0
33661 69838 13542 0 15293 0 7297 0 17295 0 16411 0
55459 98383 11888 0 0 0 28608 0 29262 0 28625 0
67607 24938 0 19110 0 0 0 0 0 5827 0 0

These numbers were pulled from the Sob.txt file and are not current. I'll pull the lowresults.txt and the nodubewhatever.txt files from the Sob.txt later and then look at the numbers once again.

For Riesel Sieve I predicted, more like guessed since I don't have enough historical data to go on, each k for what n will end in to hit prime. It's just a guess since I can't prove that the ending digit for n has any predictability for finding a prime....yet. I'm still working on a few ideas. Viewing the above chart with the new one that I'll produce after pulling all factors from the Sob.txt should give me a better understanding of how the n's are being pulled. Historical data from the 5 previous k's would be a help. If we could derive a way to look at the ending digit for n and PRP test those values first, then maybe a shortcut could be found to skip nonprobable n values.

It is late for me and I'm sure I left out some stuff and maybe even sounded confused. I will pull the factors out tomorrow and relook at the data. This was mostly a post to display data for n's.

[b2uc]

Ok...after taking the weekend off I finally got around to pulling some factors out of the Sob.txt. Using the available data from the nodupes_something_something_whatever.txt...I yanked out the factors. I'm sure there are many more factors that have been found lately not available to me...but I did pull out close to 50,000 k/n pairs from the publically available 300K - 20mil SoB.dat. I had my programming bud rayman write up a little factor yanker and he also wrote the proggie for counting the n's by their last digit.

After yanking the factors and pulling a third of a meg off the file size I sent the new SoB.dat to ceselb to test run to see if it was any faster on the sieve while I played with numbers. He reported a 2kp/sec slowdown until he noticed that the 2nd line needed to be changed to an even starting bounds to get an even bitmap file in memory or something. Next run was about 2.5% faster. I suspect he will get in touch with Louie about this matter...Louie can go over the new dat with a fine tooth comb and make sure everything is there....then maybe release it to you guys if everything looks good. 2.5% is a nice little increase for a side project just looking at the numbers. So..here is part two of some data looking at the sieving out of n's.


K #Ns 0 1 2 3 4 5 6 7 8 9
4847 66559 0 22567 0 19421 0 0 0 24571 0 0
5359 82592 23520 0 30808 0 0 0 28264 0 0 0
10223 76764 0 20324 0 0 0 16762 0 20831 0 18847
19249 27840 0 0 9690 0 0 0 8120 0 10030 0
21181 65294 15957 0 17789 0 15875 0 0 0 15673 0
22699 26792 6561 0 6494 0 6612 0 0 0 7125 0
24737 68967 0 25577 0 24078 0 0 0 19312 0 0
27653 38321 0 6069 0 7966 0 7721 0 7958 0 8607
28433 37144 0 0 0 11989 0 13434 0 11721 0 0
33661 65016 12622 0 14237 0 6802 0 16071 0 15284 0
55459 91407 11054 0 0 0 26537 0 27244 0 26572 0
67607 23166 0 17753 0 0 0 0 0 5413 0 0



Now what does all this mean? I don't know yet...but it's interesting to see the sieving down and the percentages of the decreases in size. Maybe a little more discussion on this matter from differing viewpoints can shed light on an unseen angle that we need to explore. I haven't had time to look over the differences in the data...if their is a mistake somewhere let me know...and I'll look into it.

[MikeH]

Next run was about 2.5% faster. I have a few comments here. The number of factors in the sob.dat file shouldn't affect the speed of the sieve. If it does, then we need mklasson to take a look why.

2.5% is quite small, and we see differences this big simply moving between ranges, so maybe this was part of the equation?

The gap analysis does depend upon the current level of duplicates that we get as a result of using a low sieved sob.dat. Any removal of candidates from the sob.dat file would probably result in some false holes, or in my having to relax the limits. Either way we reduce the effectiveness of a very useful tool.

Right now everyone is using one of three sob.dat files, and everything works fine. Throwing extra unknowns into the equation for unanalysed reasons really doesn't make sense.

(but please continue to look for patterns in the numbers.......this may well lead somewhere. :) )

[ceselb]

I did the test run with exactly the same range. I've mailed Louie about it, we'll se what he says.

Regarding patterns, have you seen my post in the sieve forum? There seems to be a pattern there, maybe that can be used to improve things.

[b2uc]

Originally posted by MikeH
I have a few comments here. The number of factors in the sob.dat file shouldn't affect the speed of the sieve. If it does, then we need mklasson to take a look why.

2.5% is quite small, and we see differences this big simply moving between ranges, so maybe this was part of the equation?

The gap analysis does depend upon the current level of duplicates that we get as a result of using a low sieved sob.dat. Any removal of candidates from the sob.dat file would probably result in some false holes, or in my having to relax the limits. Either way we reduce the effectiveness of a very useful tool.

Right now everyone is using one of three sob.dat files, and everything works fine. Throwing extra unknowns into the equation for unanalysed reasons really doesn't make sense.

(but please continue to look for patterns in the numbers.......this may well lead somewhere. :) )

Mike,

I forgot about the gap analysis program. Yes this would cause a problem there. The speed changes were run on the same machine for the same range. Really you can talk to Ceselb about that. I really wasn't looking into a speed change because it should not matter as long as the bitmap is the same size...HOWEVER....I noticed some serious...and I mean serious 15-25% slow down problems on RieselSieve when some of the n's that had small factors were not pulled. I had one k that did not get all it's factors pulled for n=7 to 900 million. There were a few in there that weren't reported I guess and never taken out. These factors...I'm assuming... were confusing the sieve somehow. This may be where a speed up occurs.

In human speak the the sieve is going thru...are you divisible by 11?...no...how about you?....no...how about you?..no...hey wait..weren't you divisible by 7? What you doing still here? I have no clue why this conversation would go on inside the sieve....because it shouldn't...however...once pulled I got a 25% boost on AMD's. That kind of across the board jump is hard to explain away. Later after I did research on ending n digit I found a few that were stranglers...these were LLR proth tested and found to have a reasonably small factor...in the billions. Just random factors that weren't pulled. After this there was a slight speed up.

To me 2.5% isn't quite small....to me every percentage counts...but that's mainly because I'm running much slower than SoB until we can sweet talk a few of you into helping us impliment your baby steps, giant steps speed ups in our sieve. The SoB.dat is already quite small with just 12k's. You don't have to worry about memory issues that I do with 99k's. I understand completely about the need to keep the number of available dats to a minimum. Changes in the sieve program are one thing...but changing the data is another.

On another point. If someone could send me an update of the factors so I can pull. I'm really interested in seeing how the n's are being sieved out....especially where the ending digits of n are so one sided. k=67607 where there are 17753 1's and just 5413 7's and no other numbers. That one is very interesting. If you sieve to 300T you may sieve out every n ending in 7 and that would almost prove a point. Hopefully patterns found in SoB will help the Riesel effort..and then maybe we can help other future efforts. Hopefully.

[Joe O]

For k*2^n+1 where k = 67607 you can eliminate all n that are not congruent to
27,
131,
171,
251,
387,
491,
531, or
611 MOD 720
This alone should give you a three to one ration of n congruent to 1 mod 10 over n congruent to 7 mod 10. Your numbers are close to this.

You can find all the possible values for n mod 720 for all 12 K attached to this post. (http://www.free-dc.org/forum/attachment.php?s=&postid=43051)