mersenneforum.org  

Go Back   mersenneforum.org > Other Stuff > Archived Projects > 15k Search

 
 
Thread Tools
Old 2005-03-15, 19:53   #1
lsoule
 
lsoule's Avatar
 
Nov 2004
California

23·3·71 Posts
Default The fastest way to a top-5000 prime?

I’ve been searching for primes of the form k*2^n-1 with the 15k project for a while now and became interested in finding candidates, k, that would produce a top-5000 prime the fastest. How long it takes to find a top-5000 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=0-10000 to 100M
• The number of primes in the range n=0-10000
• 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 top-20 list of the k’s that had the most primes in the range n=0-10000. 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
Next is the top-20 list for the k’s that are estimated to be fastest to find a top-5000 prime with. The score is related to how long it should take to find a top-5000 prime in the range of k*2^200000-1. Thus, the smaller the better. All but 2 of the top 20 are divisible by 15.

Code:
Score	K	Primes already on top-5000 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!
I tried out the first K, 8331405, and found a top-5000 prime within 24 hours!
lsoule is offline  
Old 2005-03-16, 14:50   #2
lsoule
 
lsoule's Avatar
 
Nov 2004
California

23×3×71 Posts
Default

This one found 5 prime from n=183-221k. Based on the estimates
above, I only expected one prime, but happily surprised:
8331405*2^207555-1
8331405*2^205885-1
8331405*2^199127-1
8331405*2^198122-1
8331405*2^186251-1

Last fiddled with by Kosmaj on 2005-03-16 at 22:44 Reason: Missing exp sign "^" added.
lsoule is offline  
Old 2005-03-17, 02:43   #3
Kosmaj
 
Kosmaj's Avatar
 
Nov 2003

362210 Posts
Default

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^n-1 (or +1) is divisible by any small primes (smaller than a certain value) while 8331405*2^n-1 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.
Kosmaj is offline  
Old 2005-03-17, 03:10   #4
lsoule
 
lsoule's Avatar
 
Nov 2004
California

170410 Posts
Default

No problem taking 25935. The only other one I'm trying out is 6555.
lsoule is offline  
Old 2005-03-17, 04:17   #5
Kosmaj
 
Kosmaj's Avatar
 
Nov 2003

2·1,811 Posts
Default

OK, thanks!

BTW, some k have been searched before and following primes are recored on Top-5000.
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.
Kosmaj is offline  
Old 2005-03-17, 07:37   #6
Kosmaj
 
Kosmaj's Avatar
 
Nov 2003

2×1,811 Posts
Default

I just found out that k=25935 had been already tested by Thomas to 200k. It is listed on the 15k stats page but mistakenly as k=29535.

This k is not so promising but I'll test the 200-220k 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^219995-1 is prime!! (66230 digits)

It was the very last candidate in the 200-220k range (sieved to 30 bn) and since I started another LLR client to work in the reverse order it was found at once!

Last fiddled with by Kosmaj on 2005-03-17 at 09:06
Kosmaj is offline  
Old 2005-03-17, 22:54   #7
smh
 
smh's Avatar
 
"Sander"
Oct 2002
52.345322,5.52471

29×41 Posts
Default

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
smh is offline  
Old 2005-04-02, 21:38   #8
lsoule
 
lsoule's Avatar
 
Nov 2004
California

170410 Posts
Default

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 top-5000 list...

Code:
Score	K	Primes already on top-5000 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!
lsoule is offline  
Old 2005-04-11, 03:07   #9
TTn
 

A7B16 Posts
Default 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
Yes, as far as I know fixed n sieving is much faster.
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

Last fiddled with by TTn on 2005-04-11 at 03:12
 
Old 2005-04-11, 17:06   #10
lsoule
 
lsoule's Avatar
 
Nov 2004
California

23·3·71 Posts
Default

Thanks for the info smh and TTn. I'll take a look at fixed-n 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 top-5000 from n=198-433k.
Others I have searched n=187-300k and found 0 top-5000 primes. It looks
like the # of primes found in 0-10k 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
lsoule is offline  
Old 2005-04-12, 04:19   #11
TTn
 

212078 Posts
Default

Quote:
I have another question.
Some k's like 8331405 have 14 primes in the top-5000 from n=198-433k.
Others I have searched n=187-300k and found 0 top-5000 primes. It looks
like the # of primes found in 0-10k isn't always a good predictor of larger primes (unless the range happens to hit the arbitrarily large gaps between primes...).
Any pointers here?
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.

Last fiddled with by TTn on 2005-04-12 at 04:20
 
 

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Choose your own K and work on finding a top-5000 prime! lsoule Riesel Prime Search 338 2020-05-25 00:27
The Fastest Path a1call Puzzles 23 2016-03-23 17:46
Fastest you've driven a car? Oddball Lounge 43 2011-03-14 00:26
Help test 210885 - Find a new top 5000 prime! SlashDude Riesel Prime Search 121 2008-01-03 08:47
Help test 2995125705 - Find a new top 5000 prime! SlashDude Riesel Prime Search 538 2007-05-08 01:42

All times are UTC. The time now is 23:22.

Tue Jun 2 23:22:41 UTC 2020 up 69 days, 20:55, 3 users, load averages: 1.53, 1.33, 1.50

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.