P.I.E.S. - Prime Internet Eisenstein Search

[Batalov]

I'll try to stay busy with extending OEIS A246119 for now; plain powers of 2. Hopefully, 2^17 will yield soon (I am now at a ~50% chance of finding one), then we'll see about 2^18.

Starting from 2^18 (N=19 in Cyclo and CycloSv), a few smaller popular factors (786433 (=3*2^18+1), 8650753 (=33*2^18+1), 10223617 (=39*2^18+1), 14942209 (=57*2^18+1)) can no longer divide candidates, and the least 'eliminator' will become 14155777 (=27*2^19+1), so the list of survivors immediately thickens from less than 0.3 to ~0.5. Those sets will produce more frequent primes at the useable range of b values.

[axn]

After some quick PARI tinkering, it looks like the math will hold. Except for powers of 3. For all numbers other than powers of 3, if b is a solution, so is -b, so we only have to examine half of the roots. But for p-o-3 (b^(2.3^n) - b^3^n + 1), if b is a solution, -b is a solution for the + side. That means, we'll have to check all the roots (twice the work), but will get the +side factors also for free.


Note (from SB): on the topic of naked p-o-3: this is also the only n where the simple factor 3 is also an eliminator.
Also, these powers-of-3 on the + side, apparently, were a longtime project for Lei Zhou, who had likely spent a lot of time testing them (with general FFT)

[henryzz]

I was getting the same as Batalov. Does it happen more often with smaller n or small p? I was getting it more often than him I think.

[Batalov]

I sieved from 0P to 1P and observed a minor "feature".

For some f values, the program tries to sieve out a lot of b=0 values (!). I even thought that it would get stuck but it didn't, and after a while proceeded further. Those "f | 0^...-0^...+1" messages should better be suppressed. This is minor.

[axn]

Originally Posted by Batalov

I sieved from 0P to 1P and observed a minor "feature".

For some f values, the program tries to sieve out a lot of b=0 values (!). I even thought that it would get stuck but it didn't, and after a while proceeded further. Those "f | 0^...-0^...+1" messages should better be suppressed. This is minor.

This really shouldn't happen. I don't think the calculation can generate 0's. I have seen it occurring when I hit Ctrl-C, but in normal operation, it really shouldn't. Is it repeatable? Do you have sample p-values where this happens (repeatably)?

[Batalov]

I will check if these are reproducible. It is a possibility that this is the card's fault.

Here are the values; I further found for the same f's not only 0's are produced but the other eliminated b's are bogus (this is after "uniq"; in the original file there are thousands of the "0" lines).

116428111873 | 113961^262144-113961^131072+1
116428111873 | 0^262144-0^131072+1
283238203393 | 202508 ^262144-202508^131072+1
283238203393 | 0^262144-0^131072+1
340398440449 | 15522 ^262144-15522^131072+1
340398440449 | 0^262144-0^131072+1
398033682433 | 630320 ^262144-630320^131072+1
398033682433 | 0^262144-0^131072+1
455436926977 | 893096 ^262144-893096^131072+1
455436926977 | 0^262144-0^131072+1

This is only observed in 0P to 1P. (The full command line was CycloSvCUDA-0_1-win32.exe 18 0 1 B9)
Maybe it was the bad card (this is a comp with a weak card, where I ran only odd ranges for tests) - I'll check.

On my trusted 570, I went as far as 240P -- and no bad factors were ever found.

[axn]

Originally Posted by Batalov

Maybe it was the bad card (this is a comp with a weak card, where I ran only odd ranges for tests) - I'll check.

Could be bad memory. FWIW, most of these factors should have valid output. A quick check with PARI produced the following:

fr(p,N) = my(k = (p-1)/N/3, b); forprime(r=5,1000, if( kronecker(r,p) != -1, next()); b=Mod(r,p)^k; if(b^(N/2) != -1, return(b)));

gen(p,N) = my( b, c, d ); b=fr(p,N); c=b^5; d=b*c; for(i=1, N/4, out( [b,-b,c,-c] ); b*=d; c*=d);

out( v ) = for(i=1, #v, if( lift(v[i]) <= 10^6 , print(v[i]) ) );

? gen(116428111873, 2^18);
Mod(905478, 116428111873)
Mod(456524, 116428111873)
Mod(630660, 116428111873)
Mod(736193, 116428111873)
Mod(685105, 116428111873)
? gen(283238203393, 2^18);
Mod(150259, 283238203393)
? gen(340398440449, 2^18);
Mod(383588, 340398440449)
Mod(139479, 340398440449)
? gen(398033682433, 2^18);
? gen(455436926977, 2^18);
Mod(523655, 455436926977)

[Batalov]

I've re run the range on my trusted card - different f's of the same property were identified. It may have to do with the number of processing units/blocks/threads.

I have run it twice (from scratch); the output on the same card was identical in this regard*. Here are values that produce "0"s and the number of the "0" lines (the f values are the same in two runs, and the number of these "0" root lines is exactly the same):

Serge@MOON ~/Desktop/Cyclo-sv
$ fgrep " 0^" f18_0P_1P.txt | uniq -c
   2862 455436926977 | 0^262144-0^131072+1
   2591 1161067757569 | 0^262144-0^131072+1
   1459 1399965351937 | 0^262144-0^131072+1
    711 1639993835521 | 0^262144-0^131072+1
    136 1880679776257 | 0^262144-0^131072+1

_______________
*the outputs have different starts! An arbitrary cutoff for very small values is used (maybe the buffer overflows with very small factors?)

[axn]

Originally Posted by Batalov

(maybe the buffer overflows with very small factors?)

Very much a possiblity. I'll have to relook at the buffer size. How about recompiling with a larger result buffer size and/or running with a smaller -B value?

EDIT:- Found a bug :-( A factor result occupies 2 words (a base b and an index into the factor array). That plus the first word which is a counter, means that we need 2*RESULT_BUFFER_SIZE+1 words. But it is only allocating RESULT_BUFFER_SIZE words. At higher ranges, we're nowhere near hitting these limits (per block) so we're fine. But at the really low limits, things can (and does) go pear shaped.

EDIT2:- But the fix needed is simple. change RESULT_BUFFER_SIZE to a really large value (like 10^6).

[Batalov]

Great!

I was about to suggest a palliative solution to treat 0P as e.g. 2T (currently it is maybe ~0.5T), and the artifacts would go away... but a clean solution is even better!

[axn]

Here is version 0.2. Upped the results buffer. Put some screen output suppression (only output the first 4 factors per batch). "Optimized" some data transfer.

Included executable is compiled using CUDA 6.5 with direct support for some more archs. May be faster on the newer GPUs. Compiled using VS 2012, so might need to download appropriate runtime.

Untested :-( Caveat executor !