Octoproths

[Greenbank]

Good work Robert!

These files have been mirrored at:-

http://octoproth.greenbank.org/downloads/oc36.c
http://octoproth.greenbank.org/downloads/octo_3_6.exe

[R. Gerbicz]

Originally Posted by Greenbank

Good work Robert!

These files have been mirrored at:-

http://octoproth.greenbank.org/downloads/oc36.c
http://octoproth.greenbank.org/downloads/octo_3_6.exe

I don' know what you have uploaded, because the size of exe file is too smal. And oc36.txt isn't existing!
You can download those two files and after it upload them.

[EDIT by Greenbank] Thank you! I've fixed the links and uploaded the correct version of octo_3_6.exe.

[robert44444uk]

I think a useful goal would be to look at the mathematics behind why some n values produce so many octoproths, whilst others seem to produce less.

Regarding chains of 3- 4- etc, it is my bet that such chains do exist, but will prove very elusive. Where n is small, the population of k is also small because of the 2^n-k case. I think there is some modular maths that could be applied to perhaps narrow the choice of possible k. We should be looking in the n=30 to 60 range. Of course having the whole possible population of octos for those n vales is essential, as these are the only k that need to be checked!

Regards

Robert Smith

PS congratulations to everyone for making this a "project" and for their hard work in continuing to look for speed ups in software.

[axn]

Originally Posted by Greenbank

There are several goals, and people participating will be able to contribute to whichever one they want:

• Finding at least 1 Octoproth for each value of n
• Finding all Octoproths for an n (working on the OEIS sequence)
• Finding as many Octoproths as possible

Some additional goals:
- Kilobit Octo (I think out-of-reach for single individual but ideal for DC)
- Titanic Octo (Pushing it )
- Cleaning up all n's below a certain level. Currently it's cleaned up till n=45 (64 sounds tough, but feasible; 80 is too much) -- Hopefully the cleanup effort will yield some elusive dodecaproths.

In addition, there is always individual glory and bragging rights -- most Octo, biggest Octo, etc...

Also, somebody could probably try to come up with asymptotic density calculations for Octos and higer forms.

EDIT:- Ooh.. Almost forgot. Generalized Octos!!! With bases other than 2.

For odd base b, k should be even and vice-versa.

[R. Gerbicz]

Some time before I've uploaded octo_4_0.exe to my website. I couldn't post the c code because mersenneforum was unavailable. In that time I've tested for some large Range the new program ( before I've tested only for small ranges, for known solutions ) and I've observed that octo_4_0 has got bugs!!! Some solutions has been missed! So delete that file from your computer!

Greenbank if you'll get a results text from version 4.0 ( you can find that for each project in that text file ) then consider that it is very very possible that some solutions has been missed.

Ps. I've deleted that file from my webpage and there is a warning message about it!

[R. Gerbicz]

This new octo program is using now exactly the kmin,kmax range in the sieve, previous versions has oversieved to use a special sieve, now I've rewritten that part, so now there is no oversieve. Note that the speedup is between 0%-25% depending on your range, it isn't easy to give an average rate ( 25% is a theoretic value), and there is also smaller number of prp tests, because there is no redefinition of range.

See my attachment for c code or download the exe for windows from my webpage:http://www.robertgerbicz.tar.hu/octo_4_3.exe

[R. Gerbicz]

It is exactly the same as 4.3 version but it'll try to use one more prime in the sieve reduction step, this is value of x in the program. So the speed of this is exactly the same as the speed of 4.3 if it'll use the same x value, but it can be faster for one more prime. Try it for different ranges and different n values. Note that it can be slower than 4.3 !!!

Now magic_constant=10^5, see previous versions: it was started from 2*10^6

See the attachment for the c source or my webpage for the exe file for windows: http://www.robertgerbicz.tar.hu/octo_4_5.exe

Ps: It would be very good if somebody could test for known n values and known ranges the programs!

Note that version 4.0 has got a very serious bug!

[tcadigan]

n=171, kmin=1, kmax=10000000000, version=4.5
Starting the sieve...
Using the first 6 primes to reduce the size of the sieve array
The sieving is complete.
Number of Prp tests=156
Time=1 sec.
n=171, kmin=10000000000, kmax=1000000000000000, version=4.5
Starting the sieve...
Using the first 10 primes to reduce the size of the sieve array
99180515934675 171
855203637332835 171
42579432483105 171
111420166614855 171
The sieving is complete.
Number of Prp tests=15652022
Time=12084 sec.

[Kosmaj]

Thanks to axn for the feedback and to R.Gerbicz for quick action and many new versions. Four new versions in one day is a little bit too many for me but I never saw ver.4.0 so I tested three versions: 3.6, 4.3, and 4.5. using the same input parameters like before (n=336, k=100-111T). All compiled using -O2 and -march=pentium4. Here are the times:
3.6 ... 179 sec, 133206 PRP tests (the same time like my ver.3.5)
4.3 ... 165 sec, 125962 PRP tests
4.5 ... 171 sec, 125962 PRP tests (the same like 4.3)

So I'm now using 4.3. I noticed that the only difference between 4.3 and 4.5 is the size of magic_constant. Maybe 10^5 (now) is not the best value for my test case? Can you change the program so that the constant can be set from the command line. But you will also have to tell us how to use it.

Finally, a proposal for a simple new feature: Can you count the number of found OctoProths in one run, and print that at the end. With many numbers on the screen and in the results file it's easy to miss a precious Octo! It's also useful when testing correctness of the program (I use n=52-55 and k<1T). Now I have to count the number of Octos in the results file (90 for n=52, 12 for n=53 etc.)

Sorry, but today I didn't have time for other tests (-O1, -O3 and bench.c).

[R. Gerbicz]

Originally Posted by Kosmaj

4.3 ... 165 sec, 125962 PRP tests
4.5 ... 171 sec, 125962 PRP tests (the same like 4.3)

It is an impossible timing!!! Because for your input parameters the two versions use the same value of x=8, so the speed is exactly the same +- 1 sec. ( because I've changed only magic_constant and this is only used to determine the value of x). For me the timings were the same 263 sec.

If you reach another breakpoint ( because magic_constant is smaller ), then x is larger by one, so it is possible that you get an improvement ( this is depending on the Range and on n value ), but it is also possible that it'll be slower. I've gotten the two cases on my PC for different input parameters.

It isn't need to modify further magic_constant, because in 4.3 this is 4*10^5, if it would be larger then we get a smaller x value ( or the same ) but this is suboptimal. In version 4.5 this is 10^5, so you'll use the same x value or x+1, if it would be smaller then that isn't optimal, because we are sieving up to 10^5.

Also note that using bench.c isn't very practical in this case, because we are testing very special numbers, and for this mpz_powm instruction is faster by a factor of 2. So probably my program isn't very bad for n<512

[Greenbank]

Originally Posted by Kosmaj

so I tested three versions: 3.6, 4.3, and 4.5. using the same input parameters like before (n=336, k=100-111T). All compiled using -O2 and -march=pentium4. Here are the times:
3.6 ... 179 sec, 133206 PRP tests (the same time like my ver.3.5)
4.3 ... 165 sec, 125962 PRP tests
4.5 ... 171 sec, 125962 PRP tests (the same like 4.3)

Hah! BTW, Good work Robert!

$ gcc -m64 -mpowerpc64 -O2 -fomit-frame-pointer oc45.c -o oc45 -lgmp
$ ./oc45 336 100000000000000 111000000000000
You can also find the k n values in results_octo.txt file ( These are 3-probable primes )
   n=336, kmin=100000000000000, kmax=111000000000000, version=4.5
Starting the sieve...
Using the first 8 primes to reduce the size of the sieve array

The sieving is complete.
Number of Prp tests=125962
Time=82 sec.

Mmmm. Quad 2.5GHz PowerMac G5. Mmmm.