First megaprime in GFN16 (or GFN15) series

Would anyone find it interesting to locate the first megaprime for GFN16?

The first megaprime for GFN17 through GFN20 is known. Clearly, for lower exponents, a much higher b value (base) is needed to reach the mega level.

For GFN16, we need b > 10^(999999/65536) = 1814570322693369.9

For GFN15, we need b > 10^(999999/32768) = 3292665455999520712131951278258.6

and so on.

With so huge b values, you cannot use Genefer, but it is possible to do a PRP test (and after that a deterministic test) with OpenPFGW. It is not going to be the fastest way to find a megaprime, of course, but would it be interesting?

There is going to be a tremendous number of GFN16 primes (Yves Gallot's statistic says 310'000 if I am correct) with exactly 1'000'000 digits before we would (theoretically) arrive at 1'000'001 digits.

/JeppeSN

Addition: As a test case, if you use switch -q"1814570322693370^(2^16)+1" with OpenPFGW, you should get a result like:

1814570322693370^(2^16)+1 is composite: RES64: [AEFE572D827EB01D]

out of the PRP test, if my computer behaved.

I mostly wanted to see how long will this take, so I DC'd your result.

This discussion now has a home of its own!
____________
My lucky number is 75898⁵²⁴²⁸⁸+1

This discussion now has a home of its own!

Btw anyone got a link to OpenPFGW?
____________
My lucky numbers 1059094^1048576+1 and 224584605939537911+81292139*23#*n for n=0..26

This discussion now has a home of its own!

Thanks Mike. Any thoughts on this yourself?

Windows Task Manager showed only 12-13% CPU load.
Is this acceptable ?
Or should have I used some other tricky command line paramenter(s) ?

Windows Task Manager showed only 12-13% CPU load.
Is this acceptable ?
Or should have I used some other tricky command line paramenter(s) ?

Your cpu is 4c/8t. PFGW is a single-thread application. Fully utilizing one hyperthread would show 12.5% in task manager.

I agree. If we were to run this as a project, you should try running four candidate numbers (out of four different file folders, I think) at the same time, and see how that goes. /JeppeSN

I'm sieving this stuff. Please don't run anything big until it's done.

I set it up on range b_start=1814570322693370 to b_start+1,000,000, i.e. 500,000 candidates. This number was quickly reduced to 270,000, where sieving radio drops to 1 candidate per second. Well, it's still better then 4 hours with PFGW :)

I'll run this for a while but I wonder if could get below 250,000. Multiplying by 4 hours, it's still a huge amount of work.

Note: the sieving software is my own, CPU-only and slow, written when Jim and me bootstrapped "2G" manual sieving. Generic sieving software does not knows about special properties of factors of GFN numbers.

I'm sieving this stuff. Please don't run anything big until it's done.

I set it up on range b_start=1814570322693370 to b_start+1,000,000, i.e. 500,000 candidates. This number was quickly reduced to 270,000, where sieving radio drops to 1 candidate per second. Well, it's still better then 4 hours with PFGW :)

I'll run this for a while but I wonder if could get below 250,000. Multiplying by 4 hours, it's still a huge amount of work.

Note: the sieving software is my own, CPU-only and slow, written when Jim and me bootstrapped "2G" manual sieving. Generic sieving software does not knows about special properties of factors of GFN numbers.

Note: the sieving software is my own, CPU-only and slow, written when Jim and me bootstrapped "2G" manual sieving. Generic sieving software does not knows about special properties of factors of GFN numbers.

Thank you very much.

Odd factors of b^65536+1 always have the form 131072k+1. You are saying that your software uses that?

I try to do P-1 on those candidate but it looks like that b is to high :)

____________
92*10^^1585996-1 NEAR-REPDIGIT PRIME :) :) :)
4 * 650^⁴⁹⁸¹⁰¹-1 CRUS PRIME
2022202116^¹³¹⁰⁷²+1 GENERALIZED FERMAT
Proud member of team Aggie The Pew. Go Aggie!

Current sieving depth: 1.06T, candidates left: 227000

You can see how slow this type of sieving (with high b) is: we've just passed 1T but our standard manual sieving tasks are measured in 'P's.

Can LLR be used in processing of those candidates?
____________
92*10^^1585996-1 NEAR-REPDIGIT PRIME :) :) :)
4 * 650^⁴⁹⁸¹⁰¹-1 CRUS PRIME
2022202116^¹³¹⁰⁷²+1 GENERALIZED FERMAT
Proud member of team Aggie The Pew. Go Aggie!

Current sieving depth: 1.06T, candidates left: 227000

You can see how slow this type of sieving (with high b) is: we've just passed 1T but our standard manual sieving tasks are measured in 'P's.

You removed 247'000 - 227'000 = 20'000 candidates since your previous post, then. That is nice.

It would be a huge effort to find the first prime. However, it should show up long before your candidates are exhausted, i.e. before bMin + 1'000'000.

Of course some of them may have a small factor. If you use -f0, it will not search for the small factors.

When you run the P-1 test, do you use -t switch? This will not try to factor the number itself, but it will use the fact that the number minus 1, i.e. 1814570322693370^(2^16), is easy to factor, and that can be used for a deterministic proof that the PRP (if it had been one) is in fact prime.

If you want to only search for factors, maybe -f -o is what you use.

/JeppeSN

Why forcing PFGW?
In any way , and for needs of this project LLR is faster : so dont use PFGW.

____________
92*10^^1585996-1 NEAR-REPDIGIT PRIME :) :) :)
4 * 650^⁴⁹⁸¹⁰¹-1 CRUS PRIME
2022202116^¹³¹⁰⁷²+1 GENERALIZED FERMAT
Proud member of team Aggie The Pew. Go Aggie!

Has anyone done like for like performance comparison of LLR vs PFGW?

I vaguely recall that FFT size is related to N, and if LLR is used, the FFT may be too small to effectively make use of multiple threads. This would need testing.

Has anyone done like for like performance comparison of LLR vs PFGW?

I vaguely recall that FFT size is related to N, and if LLR is used, the FFT may be too small to effectively make use of multiple threads. This would need testing.

Has anyone done like for like performance comparison of LLR vs PFGW?

336k FFT. By my estimates I think scaling to 2 threads might be ok, but not so great above that. For comparison, I only have one complete MEGA unit in history and that is 256k FFT.

When I said earlier that I thought FFT size was related to N, I now recall that was in relation to genefer. I don't know how PFGW/LLR would behave.

Note that this was running ONE instance of the program on a quad-core Haswell i5. On the single thread tests, if you were running four tests in parallel, you might see a decrease in performance due to memory usage. You would therefore want to run LLR to take advantage of multi-threading.

Note that this was running ONE instance of the program on a quad-core Haswell i5. On the single thread tests, if you were running four tests in parallel, you might see a decrease in performance due to memory usage. You would therefore want to run LLR to take advantage of multi-threading.

For most Intel CPUs, you'd want 2 cores worth of cache per task to not need to hit ram. Could you also do a -t2 for comparison?

LLR works well and even produced same residue as OpenPFGW (see first post):

Based on Michael's results, I'd estimates the units per day for that CPU as:
1x -t4 = 10.9
2x -t2 = 14.5
3x -t1 = 13.1 assuming 8MB cache CPU like i7, the i5 is only 6MB so will be worse than this (ram limited)
4x -t1 would be limited by ram speed

Assumes the clock is the same in all cases.

That's running the PRP test in PFGW, which is how I would recommend you use PFGW.

That's running the PRP test in PFGW, which is how I would recommend you use PFGW.

Why do you not recomment running the deterministic (N-1) test in PFGW?

Good news everyone. I found that hacked version of our manual sieving GPU app can work with huge b values. But it does something strange. It could only find factors above 1,8P. I did a minimal range of 1P-2P and it produced nothing first. I thought that my assumptions for this hack were wrong and moved to other things. But the app kept running. Later I've occasionally switched to this window and suddenly seen factors...

To be exact, the minimum factor it found was

1814652271329281 | 1814570323409552^65536+1

All factors are correct, I'm checking them. I don't know what's behind this and why it's not working at lower ranges. Although I've ported this app, most of math stuff in it is a black magic to me. I even cannot be sure that it's not missing some factors, there is no way to verify. Anyway, this will allow us to sieve much deeper and remove many thousands candidates.

The bad new is that it's still an open question how to sieve up to 1,8P; it's too slow on CPU but there are lot of candidates waiting to be removed from this range.

Good news everyone. I found that hacked version of our manual sieving GPU app can work with huge b values. But it does something strange. It could only find factors above 1,8P. I did a minimal range of 1P-2P and it produced nothing first. I thought that my assumptions for this hack were wrong and moved to other things. But the app kept running. Later I've occasionally switched to this window and suddenly seen factors...

To be exact, the minimum factor it found was

1814652271329281 | 1814570323409552^65536+1

All factors are correct, I'm checking them. I don't know what's behind this and why it's not working at lower ranges. Although I've ported this app, most of math stuff in it is a black magic to me. I even cannot be sure that it's not missing some factors, there is no way to verify. Anyway, this will allow us to sieve much deeper and remove many thousands candidates.

The bad new is that it's still an open question how to sieve up to 1,8P; it's too slow on CPU but there are lot of candidates waiting to be removed from this range.

Good news everyone. I found that hacked version of our manual sieving GPU app can work with huge b values. But it does something strange. It could only find factors above 1,8P. I did a minimal range of 1P-2P and it produced nothing first. I thought that my assumptions for this hack were wrong and moved to other things. But the app kept running. Later I've occasionally switched to this window and suddenly seen factors...

To be exact, the minimum factor it found was

1814652271329281 | 1814570323409552^65536+1

All factors are correct, I'm checking them. I don't know what's behind this and why it's not working at lower ranges. Although I've ported this app, most of math stuff in it is a black magic to me. I even cannot be sure that it's not missing some factors, there is no way to verify. Anyway, this will allow us to sieve much deeper and remove many thousands candidates.

The bad new is that it's still an open question how to sieve up to 1,8P; it's too slow on CPU but there are lot of candidates waiting to be removed from this range.

Jim said small sieving had to be done with specialized software back when we restarted 15/16 sieve to accomodate for the new OCL app, so I'm pretty sure that behaviour is expected, though I have no clue as to why.

Stream is this something we can help you with after TdP concludes?

I wonder how many peoples with significant computing power (e.g. >20 cores total) are interested in this project. Required computing power still look big, and I need to make some estimations about optimal sieving ratio.

Currently we have 190'800 candidates to test. This number is decreasing slowly thanks to GPU sieving at high area, but I'm still working on the problem of sieving in middle area between 0.008P (current CPU sieving progress) and 1.815P (start of GPU sieving). I finally wrote a GPU-assisted sieving program, it's working fine in test environment (software OpenCL) but crashes NVIDIA drivers/compiler... So I still have work to do, may be try other versions of drivers... or just find an AMD card :)

I wonder how many peoples with significant computing power (e.g. >20 cores total) are interested in this project. Required computing power still look big, and I need to make some estimations about optimal sieving ratio.

Currently we have 190'800 candidates to test. This number is decreasing slowly thanks to GPU sieving at high area, but I'm still working on the problem of sieving in middle area between 0.008P (current CPU sieving progress) and 1.815P (start of GPU sieving). I finally wrote a GPU-assisted sieving program, it's working fine in test environment (software OpenCL) but crashes NVIDIA drivers/compiler... So I still have work to do, may be try other versions of drivers... or just find an AMD card :)

I wonder how many peoples with significant computing power (e.g. >20 cores total) are interested in this project. Required computing power still look big, and I need to make some estimations about optimal sieving ratio.

Currently we have 190'800 candidates to test. This number is decreasing slowly thanks to GPU sieving at high area, but I'm still working on the problem of sieving in middle area between 0.008P (current CPU sieving progress) and 1.815P (start of GPU sieving). I finally wrote a GPU-assisted sieving program, it's working fine in test environment (software OpenCL) but crashes NVIDIA drivers/compiler... So I still have work to do, may be try other versions of drivers... or just find an AMD card :)

Wouldn't it be easier to Run a couple P on the GPU and remove those candidates to then have less stuff to sieve on the middle area? If I understand correctly, it doesn't matter how many factors you have on the GPU side, but it does on the CPU, so maybe that's a way to cut the CPU portion of the sieve.

Maybe someone else can run it on their AMD card?

Most likely someone else has something more powerful, but I can try it on my mediocre Radeon HD 6950 (Cayman)

Maybe someone else can run it on their AMD card?

Most likely someone else has something more powerful, but I can try it on my mediocre Radeon HD 6950 (Cayman)

Radeon 580?
____________
92*10^^1585996-1 NEAR-REPDIGIT PRIME :) :) :)
4 * 650^⁴⁹⁸¹⁰¹-1 CRUS PRIME
2022202116^¹³¹⁰⁷²+1 GENERALIZED FERMAT
Proud member of team Aggie The Pew. Go Aggie!

I wonder how many peoples with significant computing power (e.g. >20 cores total) are interested in this project. Required computing power still look big, and I need to make some estimations about optimal sieving ratio.

Currently we have 190'800 candidates to test. This number is decreasing slowly thanks to GPU sieving at high area, but I'm still working on the problem of sieving in middle area between 0.008P (current CPU sieving progress) and 1.815P (start of GPU sieving). I finally wrote a GPU-assisted sieving program, it's working fine in test environment (software OpenCL) but crashes NVIDIA drivers/compiler... So I still have work to do, may be try other versions of drivers... or just find an AMD card :)

Status update.

My GPU sieving program is working, at last. I isolated the problem in NVIDIA compiler (it failed to unroll the loop of 16 iterations) and worked around it. Even almost non-optimized, it working with good speed of 0,25 P/Day, so I could sieve middle area (up to 1,8 P) is a reasonable time. CPU version of this program is also not bad, it's working much faster then my original software and gives nice additional boost of 0,008P * 6 cores (and I could add more cores, if necessary).

There are 168'000 candidates left. Time to start setting up the server.

stream, thank you for picking up my loose idea from the first post and realizing it, even when it is going to be a looong search (unless luck prevails). /JeppeSN

stream, thank you for picking up my loose idea from the first post and realizing it, even when it is going to be a looong search (unless luck prevails). /JeppeSN

168'000 candidates * 4 hours / 24 / 365 = 76,7 years on single core. I think it can be squeezed more, to 160'000. Give it 100 ideal cores and one pass will be done in 9 months. Not considering a luck and prediction about 3,89 primes in this range.

The GFN server currently have 543 hosts registered (each of them has many cores) but it's hard to predict how many of them will be used in this project.

stream, thank you for picking up my loose idea from the first post and realizing it, even when it is going to be a looong search (unless luck prevails). /JeppeSN

168'000 candidates * 4 hours / 24 / 365 = 76,7 years on single core. I think it can be squeezed more, to 160'000. Give it 100 ideal cores and one pass will be done in 9 months. Not considering a luck and prediction about 3,89 primes in this range.

The GFN server currently have 543 hosts registered (each of them has many cores) but it's hard to predict how many of them will be used in this project.

Stream is that based on ht on or off? 4 hours I mean

[quote]
Stream is that based on ht on or off? 4 hours I mean

Did you mean mt (LLR multi-threading?) instead of ht (hyper-threading)? It'll be LLR project with properties very close to MEGA search, and ht is not useful here.

4 hours is a time from this post, it was a single instance of the program on one core. Of course every host is different so time will vary. But usual LLR limitations will apply, i.e. running multiple workunits in parallel will hit memory throughput limit. Like in other PG LLR projects, you have to find out what's best for your hosts - how many LLR threads to use and how many instances to run. For example, Mike did a nice job testing different thread count on his PC:

llr64 -d -q"1814570322693374^65536+1" : 5.5 hours llr64 -d -t2 -q"1814570322693374^65536+1" : 3.3 hours llr64 -d -t4 -q"1814570322693374^65536+1" : 2.2 hours

Unfortunately it's not clear how many instances of LLR were run with 1 and 2 threads, increased memory concurrency will decrease performance. Best configuration may be either 2 instances * 2 cores either 1 instance * 4 cores.

I think we can start project soon after end of PG challenge. The server is ready and tested, all it need is 3-4 more days of sieving.

I think we can start project soon after end of PG challenge. The server is ready and tested, all it need is 3-4 more days of sieving.

The server is ready and tested

on which server will these tasks be run?

I think we can start project soon after end of PG challenge. The server is ready and tested, all it need is 3-4 more days of sieving.

I think we can start project soon after end of PG challenge. The server is ready and tested, all it need is 3-4 more days of sieving.

Cool! I tested one on 6 threads, just over an hour ;)
On a Intel(R) Core(TM) i7-5930K CPU @ 3.50GHz 

I think we can start project soon after end of PG challenge. The server is ready and tested, all it need is 3-4 more days of sieving.

Stream could you give us 24 hours heads up before you go live, so we can prepare and finish up cpu tasks in progress.

A request if I may. Could this be added as default unselected? I randomly throw some small units through my systems and don't want to end up with a bunch of these by accident after it goes live but before I can review settings.

A request if I may. Could this be added as default unselected? I randomly throw some small units through my systems and don't want to end up with a bunch of these by accident after it goes live but before I can review settings.

It'll be default unselected but, you may get some occasionally if you have both "get other work if no selected work available" option turned on and only GFN-13 selected (since there are no GFN-13 CPU work, you'll get a mix of GFN-14 and MEGA16 CPU tasks). In this case you should turn this option off and select GFN-14 if you plan to crunch it.

What will the app_config.xml look like?

Something like this?

<app>
<name>MEGA16</name>
<fraction_done_exact/>
</app>
<app_version>
<app_name>MEGA16</app_name>
<cmdline>-t 4</cmdline>
<avg_ncpus>4</avg_ncpus>
</app_version>


____________
My lucky numbers 1059094^1048576+1 and 224584605939537911+81292139*23#*n for n=0..26

you can install the application on the server now. then users will be able to change personal settings before WUs appear

new application is already on the server (saw it in the /download/ folder), it is just not available in the settings

What will the app_config.xml look like?

Something like this?

<app>
<name>MEGA16</name>
<fraction_done_exact/>
</app>
<app_version>
<app_name>MEGA16</app_name>
<cmdline>-t 4</cmdline>
<avg_ncpus>4</avg_ncpus>
</app_version>

What will the app_config.xml look like?

Something like this?

<app>
<name>MEGA16</name>
<fraction_done_exact/>
</app>
...

2. The <app> block is superfluous in this trivial case. There are no other settings in it, so it can be removed completely (no block - no overrides).

1. Application name will be gfn16_mega
2. The <app> block is superfluous in this trivial case. There are no other settings in it, so it can be removed completely (no block - no overrides).

<app_config> <app_version> <app_name>gfn16_mega</app_name> <cmdline>-t 4</cmdline> <avg_ncpus>4</avg_ncpus> </app_version> <app_config>

This is a minimal file for 4 threads. It may be better to run 2 tasks * 2 threads on 4 true cores, but it's system-dependent.