mersenneforum.org - View Single Post - The fastest way to a top-5000 prime?

lsoule · 2005-03-15, 19:53

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!

2005-03-15, 19:53	#1
lsoule Nov 2004 California 3250₈ Posts	The fastest way to a top-5000 prime? I’ve been searching for primes of the form k2^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 k2^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!