Join PrimeGrid
Returning Participants
Community
Leader Boards
Results
Other
drummers-lowrise
|
11)
Message boards :
Number crunching :
hey! a more efficient sieve for b*2^k+1
(Message 155223)
Posted 521 days ago by Ravi Fernando
I assume by "group order" you mean the order of 2 in the multiplicative group mod p. This will always be a divisor of p-1, and usually it will be (p-1)/d where d is small. So the first algorithm that comes to my mind is: 1. Factor p-1.
2. Initialize a "result" variable to equal p-1.
3. Loop through all distinct prime divisors q of p-1: a) Check whether 2^(result/q) is 1 mod p. If so, set result = result/q and repeat until either it fails or result is no longer divisible by q. 4. Return result. Disclaimer: I haven't read the source code of sr1sieve or any other sieving program, and I am virtually certain that it's smarter than anything I can come up with in 30 seconds.
|
12)
Message boards :
Number crunching :
World Water Day Challenge
(Message 155066)
Posted 540 days ago by Ravi Fernando
For the first time at least since I've been challenge coordinator, WE FOUND A MEGA PRIME DURING A CHALLENGE!
Are you sure about that? Your past posts have mentioned 2 SR5 primes, 4 DIV primes, 4 GFN-18 primes, 3 more DIV primes, and just recently, 21 GFN-17Mega primes. None of them quite on 321's order of magnitude though of course.
|
13)
Message boards :
Number crunching :
World Water Day Challenge
(Message 154874)
Posted 559 days ago by Ravi Fernando
Is there going to be a wet dress rehearsal?
No, but you can do a dry run now if you feel like it.
|
14)
Message boards :
General discussion :
Thought for the day
(Message 154805)
Posted 567 days ago by Ravi Fernando
Are there 15 hot girls within 3 miles looking to hook up with people on the ISS?
Only 15? A few months ago there were 274! (See also: xkcd.)
|
15)
Message boards :
General discussion :
Mega Prime Discovery Frequency
(Message 154337)
Posted 586 days ago by Ravi Fernando
As tng suggests, we find megaprimes so often now that an "ordinary" megaprime is no longer worth formally announcing. You can see a reverse-chronological list here, and a related forum thread here.
I guess tng was too modest to tell you that he has already discovered eleven(!!) megaprimes this month all by himself!
|
16)
Message boards :
Problems and Help :
How do I have only 97.50% first on PPS-Mega (LLR) tasks?
(Message 153933)
Posted 600 days ago by Ravi Fernando
(It is also odd that the first task had a very huge run time far in excess of the sent-return time but short cpu time. Maybe it is a DO reporting bug...)
The runtime and CPU time you're referring to (44444 and 4444 seconds respectively) are spoofed in this situation. My understanding is that the system always uses those (not very plausible) numbers when repairing a task like this.
|
17)
Message boards :
Number crunching :
Tour de Primes 2022
(Message 153505)
Posted 614 days ago by Ravi Fernando
It is hard to predict if the PPSE leading edge will drop off the Top 5000. Soon. Or ever.
I don't think it's that hard to predict. I think it will fall off the T5K in mid-late February, and I would be very surprised if it stays on forever.
Between this time last year and the end of TdP, PPSE grew by about 6300 digits, while about 320 larger primes (262 of them on PG) pushed it down; the net effect was falling 200 ranks. It is currently right around 4900th place at 498k digits. If 2022 were like 2021, it would reach about 504300 digits (climbing 150 ranks), but the T5K cutoff would climb to 506800 digits (70 ranks above it).
While in principle people could #SavePPSE for the duration of TdP by running it ~50% more (or by running GFN16 and other small projects less), I think its only real hope in the long run is for LLR2 to be enabled. (This won't happen during TdP, but might happen later.) Without LLR2, once it falls out of T5K, people will have less reason to run it, so its fall could be accelerated. Having said that, it should rise back up and possibly back into the T5K as it approaches and passes GFN16.
|
18)
Message boards :
Generalized Fermat Prime Search :
Guess the number of digits in the LAST GFN-17-LOW prime
(Message 153182)
Posted 626 days ago by Ravi Fernando
I wonder if we should close the bet soon?
I guess that's my cue to stop lurking. I'll go with 999848.
|
19)
Message boards :
General discussion :
Implementing an Algorithm?
(Message 153020)
Posted 634 days ago by Ravi Fernando
Is the test for primality under the assumption of the conjecture to be true computationally faster than a PRP test? If so, it could be an interesting way to generate large PRPs. The test for primality assuming the conjecture is a PRP test (basically a base-2 strong PRP test). I'm not the right person to ask, but I assume it's one of the faster PRP tests out there. And I certainly agree that prime searches should run the fastest available PRP test before verifying primes with a deterministic primality test (or in this case a more reliable PRP test)--large PRPs are so rare that the verification step takes a negligible fraction of the overall time.
Because 3^k + 2 increases exponentially, if n is a PRP then it is most likely prime. Why is that? Couldn't any number be written as 3^k + m and thus increase exponentially with increasing k?
Just to further explain Yves's comment: generally speaking, if n is a PRP then it is most likely prime, period. (PRP is short for...) Pseudoprimes are rare, and they become rarer as the numbers get larger. Accordingly, in a very dense sequence (such as the linear sequence 3^k + m with k fixed and m changing), you will likely find infinitely many pseudoprimes. But in a very sparse sequence (such as the exponential sequence 3^k + m with m fixed and k changing), you will likely find very few or no pseudoprimes: the chance of finding one drops too quickly as you go.
So if you pick a value of m and ask whether there exists a pseudoprime of the form 3^k + m, the answer will very often be no. But since base-2 strong pseudoprimes exist, the answer is yes for some values of m. Accordingly, you should not expect there to be an easy way to prove there are no pseudoprimes of the form 3^k + m for any particular m.
|
20)
Message boards :
Extended Sierpinski Problem :
k = 202705
(Message 152779)
Posted 644 days ago by Ravi Fernando
If I'm not wrong and also assuming a sieving percentage of 1%, about 23000 tests are required to produce a mega prime.
1% sounds a bit optimistic to me. My rule of thumb is that the number of tasks needed to find a prime is roughly #(digits)/30.
That would correspond to a sieving rate of about 1.4%?
Yeah, only a bit optimistic. And I guess I was a bit pessimistic.
Btw, I was looking at the stats and saw that the number of workunits per 1M range of k for Woodall numbers decreases steadily with increasing k. For example 1M < k < 2M there were 36000 workunits and for 18M < k < 19M there were only 28000. Cullen shows a similar trend, but way less pronounced.
Were the larger numbers sieved more deeply or is there another reason?
This thread has gotten way off topic already. If you want to talk about CW sieve density, you should make a new thread about it (or look at this old one).
|
Next 10 posts
|
