View Single Post
Old 2016-02-17, 06:07   #13
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

22·227 Posts
Default

None of the following is a surprise, but I ran some experiments and thought the results were interesting enough to post.

tl;dr: Use k values that are {1,5,7,11,13,17,19,23,25,29} mod 30 for best results with k*n#/6 or /30. Other divisors may have different results.


I ran a simple experiment looking at k*n#/30 with:
- all k values from 1 to 1,000,000 including evens
- n from 173 to 337
- print every result with merit 15+.

then looked at the resulting k values mod 30.
13% each of all results were in class 5 and 25
6-8% each in classes 1, 7, 11, 13, 17, 19, 23, 29
3-4% in classes 3, 9, 21, 27
.9% in class 15
.5% or less in all evens, and 0,6,12,18 had no results at all

Based on the results for 5/25 and 15, k*n#/6 seems more productive, /2 or /10 less so. With /30, primes plus 1 plus multiples of 5 seem to work best. A downside of using multiples of 5 is that it overlaps with people that have done searches with the 6 divisor.

The same thing ran with divisor 210 yields:
12% each for 5, 25
4-6% each for 1, 3, 7. 9, 11, 13, 17, 19, 21, 23, 27, 29
3% for 15
1+% for 2, 4, 8, 14, 16, 22, 26, 28
< 1% for 0, 6, 10, 12, 18, 20, 24
Similar to /30 but multiples of 3 are even more common.

With divisor 6, k mod 30 shows:
~9.5% for 1, 5, 7, 11, 13, 17, 19, 23, 25, 29
~0.7% for 3, 9, 15, 21, 27
0.1% or less for evens

Using the 8 values 1,7,11,13,17,19,23 would find 89.6% of the results and run 88% faster. Adding in 5 and 25 gets 97.6% of the results and runs 50% faster (skipping 3, 9, 15, 21, 27). The speedup would likely be mitigated by prev_prime running quickly due to a small gap and then skipping further processing.

To test the mitigation, I timed k=1..2M, n=281#-313#, d=30, 10 threads:

best10 2049 results 799s 2.56 res/sec +36%
odds 2365 results 1258s 1.88 res/sec ----
all 2432 results 2314s 1.05 res/sec -56%


A look at the results from my recent k*n#/30 searches that have run all odds shows results that are similar but not quite the same (5 and 25 are less common instead of more common). Those searches are only showing results that have beat current merits so this may be influenced by previous searches using /6. They show 1,7,11,13,17,19,23,29 to be the best values by far. class 5 and 25 occur half as often, classes 3, 9, 21, and 27 occur 1/20th as often as the top values, and 15 only found one result of 2500. So the co-prime selection isn't a bad choice, but adding 5 and 25 wouldn't hurt. Either are more efficient than all-odds.

I looked at my month or so of results using k*n#/7410 and see similar classes. Doing the same experiment with that divisor shows it isn't as productive as (in order) /6, /30, /210, or /4818. /24090 is somewhat better as well. The classes mod 30 look very similar to the ones I gave for /210.

I tried looking at the results Antonio has done with /24090 but it's clear his script is using the set 1,7,11,13,17,19,23,29 so this doesn't tell us anything (probably looking at numbers co-prime to the divisor, the theory being that e.g. we would test /4818 separately hence we don't want multiples of 5). Running the experiment above with /24090 shows 5 and 25 to be 2x more common than the others -- so /4818 would be a good divisor for someone to test (indeed, I found a merit 31.6 gap during this experiment). 3 and 9 appear as often as the co-prime values, and the drop off on other classes isn't very sharp (15 isn't much worse than 23, and 2, 4, 8, 14, 22, and 28 are each over 1%). Using /4818 I get the familiar 1,5,7,11,13,17,19,23,25,29 list at the top, with multiples of 3 also getting ~2% each.

Just for info, I tried /12045 since that was brought up on the theory thread. It results in 10x fewer results than /6 or /30 or /25090 for the same number of trials so looks like a bad idea in general. The mod results say to avoid all multiples of 3 and 5 for that example, but keep the evens (leaving 16 of 30 classes).


Based on these, I think running all odds makes sense for /210, but changing to the 10-of-30 list is better for /30 and /6 and some other divisors.
danaj is offline   Reply With Quote