Octoproths

[Greenbank]

Enhancement to octo.c

Allow numbers to be specified in scientific format (although no decimals allowed).

Following code replaces the two lines:-

mpz_set_str(kmin_gmp,argv[2],10);
mpz_set_str(kmax_gmp,argv[3],10);

        if( strchr( argv[2], 'E' ) ) {
                unsigned int a,b;
                if( sscanf( argv[2], "%uE%u", &a, &b ) == 2 ) {
                        mpz_set_ui( kmin_gmp, 10 );
                        mpz_pow_ui( kmin_gmp, kmin_gmp, b );
                        mpz_mul_ui( kmin_gmp, kmin_gmp, a );
                } else {
                        printf( "Unable to get kmin value from '%s'\n", argv[2] );
                        return(0);
                }
        } else {
          mpz_set_str(kmin_gmp,argv[2],10);
        }
        if( strchr( argv[3], 'E' ) ) {
                unsigned int a,b;
                if( sscanf( argv[3], "%uE%u", &a, &b ) == 2 ) {
                        mpz_set_ui( kmax_gmp, 10 );
                        mpz_pow_ui( kmax_gmp, kmax_gmp, b );
                        mpz_mul_ui( kmax_gmp, kmax_gmp, a );
                } else {
                        printf( "Unable to get kmax value from '%s'\n", argv[3] );
                        return(0);
                }
        } else {
                mpz_set_str(kmax_gmp,argv[3],10);
        }

With this you can now do:-

./octo 179 1E14 2E14

instead of all of those zeros.

[R. Gerbicz]

Good work. But I prefer using T=10^12 ( and to modify to accept also t ).

Originally Posted by Greenbank

501 Greenbank (1) RESERVED

Do you know that finding a solution for n around 500 is 2^8=256 times harder than finding a solution for n around 250 ?

[R. Gerbicz]

If somebody want to test that k,n value is an octoproth ( not just the numbers are 3-prp numbers ). Then here it is a PARI program:

f(k,n)=a=[1,1,2,2,k,k,2*k,2*k];b=[k,-k,k,-k,1,-1,1,-1];test=1;for(i=1,8,if(isprime(a[i]*2^n+b[i]),,test=0;break));\
print1("This is");if(test==0,print1(" not"));print1(" an octoproth.")

Try it for example: f(2482746958136235,183) This will give you :
This is an octoproth.

How it looks like my new avatar?
ps.This octoproth has been found by Robert44444uk
You can also find on page2 an openpfgw program for this.

[Kosmaj]

I think you are right about timings of 4.3 and 4.5. On my Athlon-MP2000+ both 4.3 and 4.5 take the same time, 206 sec. to complete the [336, 100-111T] example. Most likely another process slowed down my 4.5 client on P-4. Will try again later.

But how can we know when to use 4.3 and when 4.5 so that we don't waste any time? Since the difference between the two versions is very small I still think that a command-line switch is a better way to handle them (instead having two executables).

BTW I wrote a script in bash to run octo for a range of exponents. It's in attached file mocto.txt. Rename it to octo and use it as
./mocto nmin nmax [kmin] kmax

kmin and kmax are in 10^12 so one can get rid of all zeros. If kmin is omitted then kmin=15. For example
./mocto 52 55 1
will test n=52, 53, 54, and 55 to 10^12. Likewise
./mocto 52 55 100 200
will test the same n's between 1E14 and 2E14. No changes to "octo" are needed. It now runs "octo45", change "exe" variable on line 10 to specify another executable.

[R. Gerbicz]

Originally Posted by Kosmaj

But how can we know when to use 4.3 and when 4.5 so that we don't waste any time? Since the difference between the two versions is very small I still think that a command-line switch is a better way to handle them (instead having two executables).

To give a quick check. I suggest that run the two versions up to 0.2% and write down the timings: Say for the same n value and Range you'll get:
version4.3 0.1% 40 sec.
0.2% 81 sec.
version4.5 0.1% 35 sec.
0.2% 69 sec.
Then version 4.5 is faster for this n value and range, and you've wasted only about 0.4% of the total sieving time, but using 4.5 instead of 4.3 You'll get a speedup by 14%

Note that the percentage is only an approx value, but if your Range is large, say 10^13, then it is a very good approximation.

Note that it is dependent on n and Range which program is faster, not only on Range! And it is very important that not run other programs or tasks on your computer when you test these two programs, otherwise you'll get false timings.

[R. Gerbicz]

Originally Posted by Kosmaj

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.

OK
Probably I'll change it, the default magic_constant=400000 will be again, but it will be possible to give 3 or 4 input parameters!
./octo 152 1 2000000000000
for this the program will use magic_constant=400000
but for:
./octo 152 1 2000000000000 x
it will use magic_constant=100000 ( to use one more prime in the sieve reduction step if it is possible ).
You don't have to type the value of x, just type x. But this is only a suggestion from me. Probably we can use 10^5 as default.

[Kosmaj]

Found the new largest OctoProth
305676859408095 338 [700T]

Just a little bit larger than the previous one, its bi-twins have 117 digits and four other members 102-103 digits. All verified primes.

[Greenbank]

n=235 found after checking to 1000T.

$ ../oc45 235 2E14 1E15
You can also find the k n values in results_octo.txt file ( These are 3-probable primes )
n=235, kmin=200000000000000, kmax=1000000000000000, version=4.5
Starting the sieve...
Using the first 10 primes to reduce the size of the sieve array
848373024179325 235

The sieving is complete.
Number of Prp tests=31319279
Time=12287 sec.

[Greenbank]

None verified.

n=173, kmin=500000000000000, kmax=600000000000000, version=4.5
Starting the sieve...
Using the first 9 primes to reduce the size of the sieve array
508559499669585 173
The sieving is complete.
Number of Prp tests=1050080
Time=452 sec.

n=174, kmin=100000000000000, kmax=200000000000000, version=4.5
Starting the sieve...
Using the first 9 primes to reduce the size of the sieve array
139212669651825 174
194579287231035 174
The sieving is complete.
Number of Prp tests=2601355
Time=751 sec.

n=176, kmin=100000000000000, kmax=200000000000000, version=4.5
Starting the sieve...
Using the first 9 primes to reduce the size of the sieve array
169962726522435 176
The sieving is complete.
Number of Prp tests=1170593
Time=506 sec.

n=177, kmin=300000000000000, kmax=400000000000000, version=4.5
Starting the sieve...
Using the first 9 primes to reduce the size of the sieve array
381565889882205 177
The sieving is complete.
Number of Prp tests=2717033
Time=1036 sec.

n=178, kmin=200000000000000, kmax=300000000000000, version=4.5
Starting the sieve...
Using the first 9 primes to reduce the size of the sieve array
290888210820285 178
The sieving is complete.
Number of Prp tests=2679190
Time=951 sec.

n=179, kmin=500000000000000, kmax=600000000000000, version=4.5
Starting the sieve...
Using the first 9 primes to reduce the size of the sieve array
545337778251945 179
The sieving is complete.
Number of Prp tests=2843373
Time=875 sec.

[Greenbank]

OK, thanks to Robert Gerbicz's PARI program (which I've slightly adapted) I now have a nice script to validate the primality of the numbers we find.

Of course you need PARI installed and it isn't much different from Robert's original version.

The output looks like this:-

562223326335,235 PPPPCCCC
722744559915,235 PPPPCPCC
926010118305,235 PPPPCPCC
2441346583515,235 PPPPCCCC
305676859408095,338 PPPPPPPP

The first 4 were the ones found with axn1's Pascal program which let a few more pseudo-primes through than octo.exe. You'll notice they all passed the first 4 tests but failed 3 or 4 of the last 4.

The last one is Kosmaj's current record holding OP for n=338! 8 P's = OctoProth! (117 digits for the largest!)

Mean time I put my Quad G5 to good use and I've completed the search ranges for all n <=48 (and 49,50 and 51 are in progress).

I'll run all of the results_octo.txt files through the prime validation script and post the results.

I'll also make the entire lists of OPs for n<=48 (and soon to be n<=51) available for download (although it will be a reasonably big file).

[R. Gerbicz]

Originally Posted by Greenbank

Mean time I put my Quad G5 to good use and I've completed the search ranges for all n <=48 (and 49,50 and 51 are in progress).

For this I hope you use kmin=1 and kmax=2^n-1

But also note that in this case the second smallest number 2^(n+1)-k>2^n>10^5, but the smallest number is 2^n-k<10^5 if and only if 2^n-1>k>2^n-10^5 ( because here 2^n-1>k ). It is important because my sieve will delete this prime from the list, because it has got a small prime factor (<10^5). It means that my program miss all octoproth in [2^n-10^5,2^n-2] range and you have to check it by another program ( it isn't very hard because it means you have to check at most 8*10^5 numbers for prp testing ).

And yes it is very important that after you have gotten your text file then check by another program the results, that these are really prime numbers. I think for n>50 it isn't very impossible to get a composite 3-prp numbers.

On page2 there were some results up to n=43 or something like that, have you checked these results, by my octo program? It would be very good.

It isn't impossible to write a faster program for these small n values, because prp testing is also very fast for these small n values.