Join PrimeGrid
Returning Participants
Community
Leader Boards
Results
Other
drummers-lowrise
|
Message boards :
Generalized Fermat Prime Search :
Subproject status?
| Author |
Message |
|---|
|
|
|
Does the GFP search have a subproject status like all of the others? If not, will it?
Are all of the testable n18s complete? How far into the n19s are we? What about the n22s?
____________
15547296^32768 + 1 is prime!
63 · 2^1356980 + 1 is prime!
63 · 2^1356980 + 1 divides xGF(1356973,11,4)! | |
|
 Michael Goetz Volunteer moderator
Project administrator
Send message
Joined: 21 Jan 10
Posts: 14037
ID: 53948
Credit: 476,993,571
RAC: 281,271
                               
|
Does the GFP search have a subproject status like all of the others? If not, will it?
Not yet, but I hope so.
Are all of the testable n18s complete? How far into the n19s are we? What about the n22s?
n=18: No, but we made amazing progress. On the PRPNet side, the leading edge is about 479K. On BOINC, we started at 500 and went very quickly to about 750K. GeneferCUDA should be able to keep processing those until almost b=1M, so there's quite a bit more there that can done.
At n=19, PRPNet's leading edge is around 103K. It was at 75K in November. On BOINC, we started at 110K and I did one a couple of days ago at 135K.
At n=22, we started at 12 and we're at least into the 500s now, at least as far as WUs that have been sent out. Since we have only been doing those a short while, and the WUs take so long, I'm sure very few of them have come back except for the first few which are about half the length of the current WUs.
____________
My lucky number is 75898524288+1 | |
|
|
|
|
In my view, this is the most exciting project at PrimeGrid. GPUs have already found a number of very large primes, using relatively little time. As long as GIMPS doesn't pop out another Mersenne, a world record GFP is almost inevitable. | |
|
Michael GoetzVolunteer moderator
Project administrator
Send message
Joined: 21 Jan 10
Posts: 14037
ID: 53948
Credit: 476,993,571
RAC: 281,271
|
In my view, this is the most exciting project at PrimeGrid. GPUs have already found a number of very large primes, using relatively little time. As long as GIMPS doesn't pop out another Mersenne, a world record GFP is almost inevitable.
Inevitable isn't exactly the word I'd use. I'm hopeful, but there's several unknowns.
To start with, nobody has yet to prove that, for any given N, there must be at least one prime number. It's possible that there are absolutely no prime numbers at N=4194304, no matter how high we search.
As N increases, generally, so does the lowest B value that yields a GFN prime. The largest N for which there is a known prime is the one in my signature. For the world record search, we're going up not one N, but 3 N's. How high will we need to search to find a prime? We won't know until we find it. That may take years -- or we may hit GeneferCUDA's limit before we find it.
It's not a certainty that there is a prime at N=4194304, nor is it a certainty that a prime would be within the range that we're able to search.
One thing, however, IS certain. We won't find a world record prime number if we don't search for it.
I definitely agree that this is the most exciting project at PrimeGrid. If we find this, it will be a very, very big event. Of course, we'll still have to do the primality proof since the Genefer algorithm is only a PRP test, and that will take a while.
____________
My lucky number is 75898524288+1 | |
|
|
|
|
I think it would be useful to construct a graph showing "N vs. lowest b-value yielding a prime". This would give us some clue as to what we could expect.
Sure, we may not find a prime before we hit b=400,000 at N=22, but there's always N=23 & N=24. Also, a discovery at N=21 or even N=20 would still be cause for excitement. Nevermind the #1 spot. How about we focus on knocking down Mersenne 39, then Mersenne 40, and so on?
Hell, I'd be happy with another discovery at N=19. After all, 75898 isn't a particularly large b value! hehe
One other thing that makes this project exciting is the rapid development of NVidia GPUs. The 600 series is on its way! | |
|
Michael GoetzVolunteer moderator
Project administrator
Send message
Joined: 21 Jan 10
Posts: 14037
ID: 53948
Credit: 476,993,571
RAC: 281,271
|
I think it would be useful to construct a graph showing "N vs. lowest b-value yielding a prime". This would give us some clue as to what we could expect.
I went and collated that information a couple of weeks ago. Here's the lowest b that yields a prime at each N:
n N Min prime b
1 2 2
2 4 2
3 8 2
4 16 2
5 32 30
6 64 102
7 128 120
8 256 278
9 512 46
10 1,024 824
11 2,048 150
12 4,096 1,534
13 8,192 30,406
14 16,384 67,234
15 32,768 70,906
16 65,536 48,594
17 131,072 62,722
18 262,144 24,518
19 524,288 75,898
Sure, we may not find a prime before we hit b=400,000 at N=22, but there's always N=23 & N=24.
The limit is closer to 500K than 400K, and that's probably going to be several years worth of searching. N=23 will require either GPUs with more memory, or a minor change to GeneferCUDA. N=24 May be problematic, but we're a long ways from there.
Also, a discovery at N=21 or even N=20 would still be cause for excitement. Nevermind the #1 spot. How about we focus on knocking down Mersenne 39, then Mersenne 40, and so on?
That would be very exciting, indeed. I'm all for starting up 20 and 21 on PRPNet.
Hell, I'd be happy with another discovery at N=19. After all, 75898 isn't a particularly large b value! hehe
It does seem like there's room for several more primes to be found at n=19.
One other thing that makes this project exciting is the rapid development of NVidia GPUs. The 600 series is on its way!
There's no reason why a similar app couldn't be written for ATI cards as well.
____________
My lucky number is 75898524288+1 | |
|
|
|
|
In terms of raw computing power, are the ATI cards better or worse than the NVidia cards? I have no idea. Obviously, the more the merrier... | |
|
Michael GoetzVolunteer moderator
Project administrator
Send message
Joined: 21 Jan 10
Posts: 14037
ID: 53948
Credit: 476,993,571
RAC: 281,271
|
In terms of raw computing power, are the ATI cards better or worse than the NVidia cards? I have no idea. Obviously, the more the merrier...
That depends on whose marketing department you ask, and exactly how you measure performance.
____________
My lucky number is 75898524288+1 | |
|
Michael GoetzVolunteer moderator
Project administrator
Send message
Joined: 21 Jan 10
Posts: 14037
ID: 53948
Credit: 476,993,571
RAC: 281,271
|
The limit is closer to 500K than 400K, and that's probably going to be several years worth of searching.
Thanks to some research from Jim B., that number can actually be quantified. If you assume you're using the very fastest GPU, there's about 2000 GPU-years of crunching to be done. Nearly 200 years worth of GPU crunching has been eliminated by sieving.
Assume an "average" GPU and you're probably doubling those numbers.
That's only crunching each WU once. It's not considering double checking.
I suspect it will take quite a while to exhaust the search range at n=22. With all the computational power available to us on the BOINC side of the project, we were blowing through the search range at n=18 very quickly. But most of the WUs at n=22 are about 200 times longer than the n=18 WUs.
____________
My lucky number is 75898524288+1 | |
|
|
|
There's no reason why a similar app couldn't be written for ATI cards as well.
That would indeed be good news, although I am well aware of the work involved for any enterprising individual who may wish to go down that road, complete the app, and make AMD users a happy Crowd :)
Regards
Zy | |
|
|
|
|
I did a simple analysis of the 19 "N vs. min prime b" numbers.
I divided each N by its smallest prime, so I have a list of 19 ratios of N:p.
The mean ratio is 1.011
The median ratio is 0.741
The minimum ratio is 0.073
The maximum ratio is 4.104
N=2^22=4194304
Based on the mean ratio, it seems like there's a 1:1 ratio of N:p, which means we can expect the first prime at N=22 to be around b=4,194,304.
That's not good news.
If N=22 yields a prime with at least the minimum ratio seen so far, it would be at least at b=307,200!
I guess "inevitable" was indeed a bad word choice!
"Possible, but unlikely" would be more appropriate.
For N=23 or higher, it's quite unlikely. Of course, this assumes that a simple ratio of N:p is an accurate relationship.
Even N=20 or N=21 may prove to be a challenge. A prime at one of those levels would give us more information to go on... | |
|
|
|
|
Does anyone have a better mathematical relationship between N and the smallest prime at that level?
Clearly, it's possible for the first prime to have a b value considerably less than or considerably greater than the N value.
16 65,536 48,594
17 131,072 62,722
18 262,144 24,518
19 524,288 75,898
Have we just been getting "lucky" with these last four N values? | |
|
Michael GoetzVolunteer moderator
Project administrator
Send message
Joined: 21 Jan 10
Posts: 14037
ID: 53948
Credit: 476,993,571
RAC: 281,271
|
|
You may be looking for patterns where no pattern exists.
____________
My lucky number is 75898524288+1 | |
|
|
|
|
Though technically true, I highly doubt that no pattern exists.
One could say the same thing about TRP or SOB, in terms of predicting the next prime, or how long those projects are going to take. One could say the same thing about the distribution of Mersenne primes...
I think there's a perfectly good reason that N=1 through 11 have relatively low b values: they're smaller numbers, and the GFNs themselves don't increase very much with increases in b.
At N=22, with b>1000, the GFNs have over 12 million digits. That's a lot of potential factors! | |
|
Message boards :
Generalized Fermat Prime Search :
Subproject status? |
