mersenneforum.org Octoproths
 Register FAQ Search Today's Posts Mark Forums Read

 2006-01-12, 16:23 #232 Greenbank     Jul 2005 2×193 Posts 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); Code:  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.
2006-01-12, 19:06   #233
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

13×109 Posts

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

Quote:
 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 ?

 2006-01-12, 20:16 #234 R. Gerbicz     "Robert Gerbicz" Oct 2005 Hungary 58916 Posts 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. Last fiddled with by R. Gerbicz on 2006-01-12 at 20:31
2006-01-12, 22:50   #235
Kosmaj

Nov 2003

E2616 Posts
R.Gerbicz

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.
Attached Files
 mocto.txt (698 Bytes, 90 views)

2006-01-12, 23:17   #236
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

13×109 Posts

Quote:
 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.

2006-01-13, 00:09   #237
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

13·109 Posts

Quote:
 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.

 2006-01-13, 06:40 #238 Kosmaj     Nov 2003 2×1,811 Posts 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.
 2006-01-13, 10:36 #239 Greenbank     Jul 2005 2×193 Posts 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.
 2006-01-13, 10:59 #240 Greenbank     Jul 2005 1100000102 Posts n=173,174,176,177,178,179 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.
 2006-01-13, 13:46 #241 Greenbank     Jul 2005 6028 Posts 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). Last fiddled with by Greenbank on 2006-01-13 at 14:21
2006-01-13, 14:11   #242
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

13×109 Posts

Quote:
 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.

Last fiddled with by R. Gerbicz on 2006-01-13 at 14:14

 Similar Threads Thread Thread Starter Forum Replies Last Post ValerieVonck Octoproth Search 100 2007-02-16 23:43 ValerieVonck Octoproth Search 0 2007-02-14 07:24 Greenbank Octoproth Search 15 2006-01-20 16:29 jasong Software 1 2005-05-10 20:08

All times are UTC. The time now is 01:05.

Fri Nov 27 01:05:03 UTC 2020 up 77 days, 22:16, 3 users, load averages: 1.17, 1.41, 1.40