The fastest way to a top5000 prime?
I’ve been searching for primes of the form k*2^n1 with the 15k project for a while now and became interested in finding candidates, k, that would produce a top5000 prime the fastest. How long it takes to find a top5000 prime for a particular k value depends on many factors: how efficient sieving is, how long LLR takes for that particular k, and how often that k produces primes. To estimate this, I started with k’s formed by all combinations of the first 11 primes and k>1000. For each k, measure
• The number of candidates left after sieving n=010000 to 100M • The number of primes in the range n=010000 • The number of bits in k (the time for LLR is proportional to this) The result of this can be summed up in a couple of lists. First is the top20 list of the k’s that had the most primes in the range n=010000. All of the k’s here are divisible by 15k. [CODE]# Primes K 81 8331405 77 944876594805 76 7526103585 73 743411955 72 685084785 71 640049865 71 41237498445 69 1818438765 69 169215941895 69 152125131763605 68 49335 68 965426385 68 1272300315 67 285413005185 67 1212935295 67 553437885 67 51449055 67 377481716535 66 578931045 66 3009765[/CODE] Next is the top20 list for the k’s that are estimated to be fastest to find a top5000 prime with. The score is related to how long it should take to find a top5000 prime in the range of k*2^2000001. Thus, the smaller the better. All but 2 of the top 20 are divisible by 15. [CODE]Score K Primes already on top5000 list 2481891 8331405 None! 2545731 49335 184364, 199133, 242161 2552143 26565 198349, 217001 2744279 25935 None! 2819593 6555 None! 2850866 19635 189197 2955186 373065 None! 2990424 102765 None! 3013362 62985 None! 3062642 67773 None! 3085355 5865 None! 3098476 3009765 None! 3119285 7526103585 None! 3123287 743411955 None! 3180954 2330445 None! 3197466 19437 None! 3222459 465465 None! 3238416 2805 185593, 192628, 200027, 200212, 203574, 212227, 230666 3242361 685084785 None! 3244999 2667885 None![/CODE] I tried out the first K, 8331405, and found a top5000 prime within 24 hours! 
This one found 5 prime from n=183221k. Based on the estimates
above, I only expected one prime, but happily surprised: 8331405*2^2075551 8331405*2^2058851 8331405*2^1991271 8331405*2^1981221 8331405*2^1862511 
Your approach is interesting. AFAIK when selecting k's nobody tried to take into account the fact that LLR can process small k's much faster than larger ones. Possibly because the first version of LLR released in 2003 couldn't. Also when selecting, or better to say constructing k's (before checking the weight) it was customary (if I'm not mistaken) to select k so that for no n, k*2^n1 (or +1) is divisible by any small primes (smaller than a certain value) while 8331405*2^n1 is divisible by 11 and 13 for some values of n.
BTW, do you mind if I try k=25935 from 183,500 to about 210,000. And congrats on many primes already found for k=8331405. 
No problem taking 25935. The only other one I'm trying out is 6555.

OK, thanks!
BTW, some k have been searched before and following primes are recored on Top5000. k=25935: 46144, 47396, 117344, 121855, 139225, 152803, 173518 k=373065: 178284, 161917, 150532, 138979 and no other k from the list of 20 fastest marked as primeless. 
I just found out that k=25935 had been already tested by Thomas to 200k. It is listed on the [URL=http://www.15k.org/stats.htm]15k stats page[/URL] but mistakenly as k=29535.
This k is not so promising but I'll test the 200220k range. Then I'll switch to k=67773 from 183500 to about 210k. [Two minutes later] One of my LLR clients just found that 25935*2^2199951 is prime!! (66230 digits) :w00t: It was the very last candidate in the 200220k range (sieved to 30 bn) and since I started another LLR client to work in the reverse order it was found at once! 
The fastest way is probably a fixed N search.
At least thats what it used to be when i was searching for primes. I don't know about changes in sieving, but fixed N sieving used to be much faster. Besides, the size of the number doesn't grow (much) if you don't find a prime. Just my 2 cents 
Just for the sake of completeness, I've updated the table this time
searching for all primes with n>100k. My previous list just searched for primes currently on the top5000 list... [CODE] Score K Primes already on top5000 list with n>100k 2481891 8331405 186251, 198122, 199127, 200363, 205885, 207555, 220532, 222399, 264459, 269433, 274141 2545731 49335 184364, 199133, 242161 2552143 26565 109141, 112017, 113640, 114935, 124714, 135551, 141212, 145695, 151485, 164728, 179468, 181672, 198349, 217001 2744279 25935 117344, 121855, 139225, 152803, 173518, 219995 2819593 6555 211720, 235260, 236514 2850866 19635 125045, 156800, 189197 2955186 373065 138979, 150532, 161917, 178284 2990424 102765 None! 3013362 62985 None! 3062642 67773 None! 3085355 5865 None! 3098476 3009765 None! 3119285 7526103585 None! 3123287 743411955 None! 3180954 2330445 None! 3197466 19437 None! 3222459 465465 None! 3238416 2805 200212 3242361 685084785 None! 3244999 2667885 None! [/CODE] 
speed
[QUOTE]The fastest way is probably a fixed N search.
At least thats what it used to be when i was searching for primes. I don't know about changes in sieving, but fixed N sieving used to be much faster. Besides, the size of the number doesn't grow (much) if you don't find a prime. Just my 2 cents[/QUOTE] Yes, as far as I know fixed n sieving is much faster. :coffee: If you use RMA, Newpgen and LLR are automated, and return primes the quickest using this method. Download RMA from the yahoo primeform group, and then copy MSCOMCTL.ocx, and COMDLG32.ocx, from your windows\system32 folder. Place them into the same folder as Newpgen, and LLR . Then click "preferences", "other options", and make sure "RMA enabled", is not checked. TTn 
Thanks for the info smh and TTn. I'll take a look at fixedn sieving.
Now that I've tried out some of the k's in my table, I have another question. Some k's like 8331405 have 14 primes in the top5000 from n=198433k. Others I have searched n=187300k and found 0 top5000 primes. It looks like the # of primes found in 010k isn't always a good predictor of larger primes (unless the range happens to hit the arbitrarily large gaps between primes...). Any pointers here? thanks, Larry 
[QUOTE]I have another question.
Some k's like 8331405 have 14 primes in the top5000 from n=198433k. Others I have searched n=187300k and found 0 top5000 primes. It looks like the # of primes found in 010k isn't always a good predictor of larger primes (unless the range happens to hit the arbitrarily large gaps between primes...). Any pointers here?[/QUOTE] Yes, the # of primes, is not always a good predictor of larger candidates. Nash weight, or Proth weight is also not always a good predictor. I am including an new option in RMA, that hunts outwards(over under) from the predicted area until a prime is found. Then a new prediction is made based on past data (kn prime) and existing weights, and testing resumes from there. Although a simple idea, it is faily complex to implement, and will skip a small # primes. Although I should add that we are just making sand castles, as the tide comes in. 
bad luck...
I have tested k=5865 from N=200K to N=300K, on a few machines.
It took over one week with LLR.exe, I sieved to 77billions by newpgen.exe earlier. Only one prime found, 5865*2^2613511. I expected about 36... maybe just this number wasn't so lucky. :down: 
BTW, I tested k=25935 from n=183500 to n=220000 and found one prime for n=219995 (already included in the table above). I don't plan to test this k any further.
I also tested k=67773 from n=183500 to n=236000 and found no primes. I have sieved to n=250000 and will stop there. 
[QUOTE=lsoule]...
It looks like the # of primes found in 010k isn't always a good predictor of larger primes (unless the range happens to hit the arbitrarily large gaps between primes...). Any pointers here? thanks, Larry[/QUOTE] Hi A quick introduction: I am Chris. [url]http://primes.utm.edu/bios/page.php?id=738[/url] I have a limited mathmatical education and find maths very hard but very interesting. If you assume you are talking to an idiot you won't be far wrong! I have been testing the number of primes for various ks up to a few thousand for n up to 15000. Is there any link between the size and frequency of the large gaps between primes and the distribution of the factors of k? For example, will a k made from say 3*3*5*13*19*31 (Nicely grouped factors.) produce a 'smoother' distribution of primes (on average) than say 3*3*5*101*359 (Not so nice.) Also: Does including powers of numbers for the factors that make up k (eg. 3*5*5*5*19*19) affect the 'smoothness' of the distribution of the resulting primes. (Ignoring any reduced chances of finding a prime.) Regards Chris 
All times are UTC. The time now is 04:11. 
Powered by vBulletin® Version 3.8.11
Copyright ©2000  2021, Jelsoft Enterprises Ltd.