Octoproths

[smh]

Originally Posted by Greenbank

We're both right. ;-)

axn1's program still outputs those values, otherwise Templus would not know them to pass them through PFGW. octo 4.5 (and previous versions) does not even output these values as possible octoproths.

And yes, Templus forgot to add the last 4 cases to the ABC line.

axn's program never claimed those numbers to be octoproths. The program just 'sieved' the range without doing a single prp test. The whole input file (hundred thousends of numbers on a large range) had to be prp tested with another program, like (win)pfgw

[R. Gerbicz]

I would like to propose a "small project":
take my octo_4_5 program, only the sieving part from c to assembly ( in sieving part don't replace gmp instructions by assembly ), because prp checking is in Gmp and that is quite efficient. Note that I've never written assembly program. I think it isn't very hard, see my code there is only such an instructions like:
for, while, if, else , --, ++, -, +
There is only one modular multiplication per sieving prime. It's cost isn't large, but put this also to assembly, if you can do.

I think we can gain about 10%-20% speed up only, because most of the instructions is only addition and I've highly unrolled the for cycle also in a cache friendly way: see b[j]=0,b[j+A1]=0,b[j+A2]=0,b[j+A3]=0,b[j+A4]=0,b[j+A5]=0,b[j+A6]=0,b[j+A7]=0;

Ps. I don't see any further improvement in the sieving code, it is very optimized in c, put it to assembly.
This octo program is the fastest program that I've ever written in c.
Perhaps I'll rewrite some part of the prp checking code.

[R. Gerbicz]

Returning to octo program:
I've implemented the tricks, what I've used for dodeca program. On some very critical ranges it is faster by about 5% than previous version.
Now you can type: ( use big T )
octo_5_0 150 42T 647T
if you want to search n=150 from 42*10^12 to 647*10^12
Note that you can type also octo_5_0 150 42000000000000 647000000000000
and note if you type decimals that are not divisible by 10^12, then I redefine these: rounding down for kmin and rounding up for kmax, so these will be divisible by 10^12. So if you type:
octo_5_0 150 42760000000000 169120000000000
Then after redefinition you will get on the screen:
n=150, kmin=42T, kmax=170T, version=5.0, here T=10^12

It won't increase the time because it means that you'll search maximum a 2T larger interval, but this is very easy for octo program.

I hope this is clear for everybody, but you can ask.

You can download exe from: http://www.robertgerbicz.tar.hu/octo_5_0.exe

or see the attachment for the c code.

Ps. Thanks for Greenbank, I've mainly implemented his string program!

[Greenbank]

All Dodecaproth discussions moved to a new thread:-

http://www.mersenneforum.org/showthread.php?t=5358

This thread remains for further discussion on Octoproths.

[robert44444uk]

Can we move Robert G's latest executables to a new thread?

Regards

Robert Smith

[robert44444uk]

Sorry guys, should have checked "how to help" first. Ignore this and last post.

Regards

Robert Smith

[R. Gerbicz]

I've posted in the octoproth reservation thread that the smallest k value is about 2^n/f(n) Looking the tables in almost every cases the smallest k value is smaller than this prediction. It's a little overestimation, I'll think about it what would be a better estimation. The problem is that if k is small than all 8 eight numbers are also small, so they have got a higher probability that they are primes.

[R. Gerbicz]

Weight of n ( for octoproths ) ( PARI programs )

w(n)=T=128.0;forprime(p=3,10^4,l=listcreate(8);g=Mod(2,p)^n;h=1/g;\
a=[g,-g,h,-h,2*g,-2*g,h/2,-h/2];a=lift(a);for(i=1,8,listput(l,a[i],i));\
l=listsort(l,1);T*=(1-length(l)/p)/(1-1/p)^8);return(T)

Number of octoproths for a given n ( estimation ):

f(n)=round(w(n)*2^n/(n*log(2))^8*1/16)

Smallest octoproth's k value for a given n ( prediction ), so it is possible that the smallest k value is
much smaller or larger, this is only an "average" expected k value: ( new estimation! )

s(n)=d=0.0;c=w(n)/(n*log(2))^8;forstep(i=1.0/2^15,1.0,1.0/2^15,\
d+=c*(2^(i*n)-2^((i-1/2^15)*n))/(1+i)^4;if(d>1.0,return(round(2^(i*n)))));return

If n is about 200 then this is 6 times smaller than my previous estimation, this is very good for the octoproth project. If n is about 300 then this is about 8 times smaller! I hope that now this formula is much better than previous.

[Greenbank]

Nice work Robert.

When I get a chance I'll compute your estimations for all n < 500 (if PARI allows this, I know a previous version stopped working around n=140 due to precision limitations).

We can then see how these compare to the number of Octoproths found for the completed ranges.

I've also finished n=55 and I'm just running all of them through PARI to confirm they are all primes. When I have the final number I'll update it.

n=56 is 50% of the way through, only running on one CPU though so it will take another 1.5 days.

I doubt I'll go as far as n=57.

When I start throwing the data into mysql on my website I can also have a page showing lowest k per n, and the estimate that your formula produces. We can see how accurate it is then :-)

I know I'm constantly saying "when the website appears" but I am working on it, just taking longer than I expected plus I had to redesign lots of bits when the idea of Dodecaproths (and hexadeca-, icosa-, etc) came along.

[Greenbank]

n=55 results in "Number of Octoproths per n" thread.

Here are the other bits of results_octo.txt (without the 700,000 Octoproths!):

n=55, kmin=0T, kmax=10000T, version=5.0, here T=10^12
Starting the sieve...
Using the first 10 primes to reduce the size of the sieve array
The sieving is complete.
Number of Prp tests=1014929270
Time=132475 sec.

n=55, kmin=10000T, kmax=20000T, version=5.0, here T=10^12
Starting the sieve...
Using the first 10 primes to reduce the size of the sieve array
The sieving is complete.
Number of Prp tests=1012619035
Time=132608 sec.

n=55, kmin=20000T, kmax=30000T, version=5.0, here T=10^12
Starting the sieve...
Using the first 10 primes to reduce the size of the sieve array
The sieving is complete.
Number of Prp tests=1012427473
Time=136325 sec.

n=55, kmin=30000T, kmax=36030T, version=5.0, here T=10^12
Starting the sieve...
Using the first 10 primes to reduce the size of the sieve array
The sieving is complete.
Number of Prp tests=614381871
Time=81683 sec.


Total PRP tests: 3654357649
Total time taken: 483091 (5 days 14 hours 11 mins 31 secs).

[R. Gerbicz]

Originally Posted by Greenbank

When I get a chance I'll compute your estimations for all n < 500 (if PARI allows this, I know a previous version stopped working around n=140 due to precision limitations).

You can raise the precision limit by \p
See for example:
(13:52) gp > \p 100
realprecision = 105 significant digits (100 digits displayed)
(13:52) gp >
Don't choose very large precision, because it would slow down the whole computation.